Transformada ràpida de Fourier

La transformada ràpida de Fourier (o FFT, de l'anglès Fast Fourier transform), no és més que una forma molt ràpida i eficient de calcular la transformada discreta de Fourier (DFT) d'un senyal discret i la seva inversa, la transformada inversa discreta de Fourier (IDFT).

Suma de dos senyals sinusoidals de 300 i 600 Hz (imatge superior) i resultat de la FFT (imatge inferior).

Es calcula de forma computacional a través d'un determinat algorisme. En termes d'eficiència, la DFT té un cost temporal d'O(n²) i la FFT d'O(nlog n). En transformades de poques mostres gairebé no s'aprecia la diferència. On sí que es pot apreciar és, per exemple, en una transformada de 1024 mostres. Fent la DFT es necessitarien aproximadament $10^{6}$ operacions i fent la FFT, en canvi, unes 5000. Per poder aplicar la transformada ràpida de Fourier, es necessiten dues condicions indispensables: que el senyal discret a transformar sigui periòdic i que el nombre de mostres sigui de l'ordre de $2^{n}$, amb n essent un nombre enter positiu. Com més gran sigui n, millor serà la transformada. Generalment, n sol ser igual a 10.

D'aquí ve la seva importància pel desenvolupament de les telecomunicacions. Operacions que abans de la FFT podien desestimar-se per la seva complexitat, van començar-se a fer utilitzant aquesta nova transformada ràpida de Fourier.

La transformada ràpida de Fourier és d'importància fonamental en l'anàlisi matemàtica i ha estat objecte de nombrosos estudis. L'aparició d'un algorisme eficaç per a aquesta operació va ser una pedra angular en la història de la informàtica.

Les principals aplicacions de la transformada ràpida de Fourier són múltiples. És la base de moltes operacions fonamentals que es troben en el tractament digital del senyal, on té una àmplia utilització. També és important en el filtratge digital i la resolució d'equacions diferencials, entre d'altres aplicacions. A més, proporciona un mitjà convenient per millorar el rendiment dels algorismes per a un conjunt de problemes aritmètics comuns.

Definició

Siguin x₀, ...., x_n-1 nombres complexos. La transformada discreta de Fourier (DFT) es defineix com

Càlcul gràfic

$f_{j}=\sum _{k=0}^{n-1}x_{k}e^{-{2\pi i \over n}jk}\qquad j=0,\dots ,n-1.$

L'avaluació directa d'aquesta fórmula requereix O(n²) operacions aritmètiques. Mitjançant un algorisme FFT es pot obtenir el mateix resultat amb tan sols O(n log n) operacions. En general, aquests algorismes depenen de la factorització de n però, al contrari del que sovint es creu, existeixen FFTs per a qualsevol n, fins i tot amb n primer.

La idea que permet aquesta optimització és la descomposició de la transformada en altres de més simples que es tornen a descompondre, i així fins a arribar a transformades de 2 elements on k pot prendre valors 0 i 1. Un cop resoltes les transformades més simples, s'han d'agrupar en altres de nivell superior que s'han de resoldre de nou i així successivament fins a arribar al nivell més alt. Al final d'aquest procés, els resultats obtinguts han de reordenar-se.

Ja que la transformada discreta de Fourier inversa és anàloga a la transformada discreta de Fourier, amb diferent signe a l'exponent i un factor 1/n, qualsevol algorisme FFT pot ser fàcilment adaptat per al càlcul de la transformada inversa. En general, tenim que:

$x[n]=IDFT\{X[k]\}={\frac {1}{N}}\left(DFT\left\{X^{*}[k]\right\}\right)^{*}$

Algorismes de càlcul de FFT

Algorisme de Cooley-Tukey

Algorisme de Cooley–Tukey

Existeixen diferents algorismes per calcular la FFT, però el més conegut i utilitzat és el de Cooley-Tukey. Aquest va ser popularitzat l'any 1965 gràcies a una publicació de J. W. Cooley i J. W. Tukey. Aquest algorisme té diferents formes. A continuació s'explica, breument, la més senzilla d'elles: la DIT (Decimation-in-time). És també la més explicada als llibres de text, però, paradoxalment, la menys usada en grans aplicacions.

La base d'aquest algorisme és fer subdivisions de la DFT. Es treballa en diferents etapes i a cada etapa es va dividint en grups de 2. Es poden fer un nombre màxim de N\2-1 etapes(per un costat els coeficients parells i per l'altre els imparells). Cada un dels coeficients de sortida de la FFT,de les mostres imparelles es multipliquen per $W_{N}^{K}=e^{-i{\frac {2\pi }{N}}k}$, on k és la posició del vector de sortida, i se sumen a les mostres parelles. Les FFT de N/2 es pot resoldre també de la següent manera: realitzant aquesta operació de manera recursiva fins a obtenir una FFT de grandària 2. El resultat és:

$X[0]=x[0]+x[1]$

$X[1]=x[0]-x[1]$.

Per exemple, es disposa d'un senyal de N=8 mostres. Es poden fer fins a 3 etapes. A la primera etapa es té una DFT de N mostres. A la següent etapa 2 DFTs de N/2 mostres cada una. I l'última etapa tindrà 4 DFTs de N/4 mostres cada una. Finalment s'han de combinar totes les etapes. Es fa a través d'una operació anomenada "butterfly", o papallona del català. Utilitzant aquest algorisme, també anomenat radix-2 s'observa que el nombre de mostres (N) que es pot agafar ha de ser potència de 2.

Altres algorismes

• FFT del factor primer(també anomenat algorisme de Good-Thomas).

-Semblant al de Cooley-Tukey però amb N essent un nombre primer.

• FFT de Bruun

-Basat en l'aproximació per factorització polinomial.

• FFT de Rader

-Es basa a expressar la DFT com una convolució cíclica. N ha de ser, també, un nombre primer.

• FFT de Bluestein

-Aquest algorisme expressa la DFT com una convolució lineal, on N pot ésser qualsevol nombre. Aquest algorisme pot utilitzar-se per a més transformades que es basin en la TZ (transformada Z).

FFT amb Matlab

• >> X = fft(x)

Fa la FFT del vector x. 'X' és un vector de nombres complexos ordenats des de k=0...N-1. Es recomana que la longitud del vector 'x' sigui una potència de 2. El que no es recomana és que la longitud 'x' sigui un nombre primer. Una altra opció de la FFT és especificar el nombre de punts amb el qual es vol fer la FFT.

• >> X = fft(x,N)

Si la longitud de 'x' és menor que N, el vector s'omple amb zeros. Si és més gran, el vector es trunca.

• >> x = ifft(X)

Fa la FFT inversa del vector X. També es pot especificar el nombre de punts N amb el qual es vol fer la IFFT. (També, com abans >> x = ifft(X,N))

• >> X = fftshift(X)

Reordena el vector X en ordre creixent de freqüència. Si “X” és el vector resultant de fer una FFT, utilitzant aquesta funció reordenem els punts en funció de la freqüència.

Altres generalitzacions

Una O(N^5/2 log N) la generalització d'harmònics esfèrics en l'esfera S² amb ganglis N² va ser descrit per Mohlenkamp (1999), juntament amb un algorisme de conjectura (però no està provat) que O(N² log² N la complexitat; Mohlenkamp també proporciona una implementació de la biblioteca libftsh. Un algorisme d'harmònics esfèrics, amb O(N² log N) la complexitat és descrita per Rokhlin i Tygert (2006).

Diversos grups han publicat també "FFT" algorismes per a les dades no equiespaiats, tal com va ser revisat en Potts et al. (2001). Aquests algorismes de no ser estrictament calcular la DFT (que només està definit per a les dades equiespaiats), sinó més aviat una aproximació dels mateixos (un no-uniforme de Fourier discret transforma, o NDFT, que és sovint només es calcula aproximadament).

Aplicacions

• Tractament d'imatge (JPEG) i àudio (MP3)
• Reducció de soroll en senyals, com el soroll blanc
• Anàlisi en freqüència de qualsevol senyal discret
• Anàlisi de materials i estadística
• Síntesi mitjançant la transformada inversa IFFT

Vegeu també

• Sèries de Fourier
• Transformada discreta de Fourier
• Transformada discreta

Bibliografia

• D. Kouznetsov, J.V. Moloney, E.M. Wright. Efficiency of pump in the double-clad fiber amplifiers (2002) JOSA B. 18 (6). Cap 1. Fiber with circular symmetry. p.743-749; Cap 2. Broken circular symmetry p.1259-1263; Cap 3. Calculation of modes p.1304-1309.
• P. Kano, D. Kouznetsov, J.V. Moloney, M. Brio. Slab delivery of incoherent pump light to double-clad fiber amplifiers: Numerical simulations. IEEE Journal of Quantum Electronics, 2004, v.40, No.9, p.1301-1305.
• D. Kouznetsov, H. Oberst. Scattering of waves at ridged mirrors. Phys. Rev. A, v.72, PMID: 013617 (2005)
• Sziklas, E.A., Siegman, A.E. Diffraction calculations using fast Fourier transform methods. Proceedings of the IEEE, 1974, Volume: 62, Issue: 3, p. 410 - 412.
• Mode calculations in unstable resonators with flowing saturable gain. 2: Fast Fourier transform method. Applied Optics, Vol. 14, Issue 8, p. 1874-1889 (1975) doi:10.1364/AO.14.001874

Enllaços externs

• Mathworks Tech Support: FFT (japonès)