Transformada Ràpida de Fourier
De Viquipèdia
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).
Es calcula de forma computacional a través d'un determinat algorisme. En termes d'eficiència, la DFT té un cost temporal de O(n2) i la FFT de O(nlog n). En transformades de poques mostres gairebé no s'aprecia la diferència. On sí que es pot apreciar és, per exemple, a una transformada de 1024 mostres. Fent la DFT es necessitarien aproximadament 106 operacions i fent la FFT, en canvi, unes 5000.
D'aquí 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.
Les principals aplicacions de la FFT es troben en el tractament digital de senyals, filtrat digital i resolució d'equacions diferencials, d'entre altres aplicacions.
[edita] Algorisme 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 número màxim d'etapes de N\2-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 número de mostres (N) que es pot agafar ha de ser potència de 2.
[edita] Altres algorismes
- FFT del factor primer(també anomenat algorisme de Good-Thomas).
-Semblant al de Cooley-Tukey però amb N essent un número primer.
- FFT de Bruun
-Basat en l'aproximació per factorització polinomial.
- FFT de Rader
-Es basa en expressar la DFT com una convolució cíclica. N ha de ésser, també, un número primer.
- FFT de Bluestein
-Aquest algorisme expressa la DFT com una convolució lineal, on N pot ésser qualsevol número. Aquest algorisme pot utilitzar-se per a més transformades que es basin en la TZ (transformada Z).
