Transformada ràpida de Fourier: diferència entre les revisions

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(n2n²) 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, en una transformada de 1024 mostres. Fent la DFT es necessitarien aproximadament <math>10^6</math> operacions i fent la FFT, en canvi, unes 5000.

Per poder aplicar la transformada ràpida de Fourier, és necessiten dues condicions indispensables: que la senyal discreta a transformar sigui periòdica i que el nombre de mostres sigui de l'ordre de <math>2^n</math>, amb n essent un nombre enter positiu. Com més gran sigui n, millor serà la transformada. Generalment, n sol ser igual a10a 10.

L'evaluacióavaluació directa d'aquesta fórmula requereix O(''n''²) operacions aritmètiques. Mitjançant un algoritme FFT es pot obtenir el mateix resultat amb tan sols O(''n'' log ''n'') operacions. En general, aquests algoritmes depenen de la factorització de ''n'' però, al contrari del que freqüèntmentfreqüentment es creu, existeixen FFTs per a qualsevol ''n'', inclús amb ''n'' primer.

La idea que permet aquesta optimització és la descomposició de de la transformada en altres de més simples que es tornen a descomposardescompondre, i així fins 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.

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 de N\2-1 etapes(per un costat els coeficients parells i per l'altre el imparells). Cada un dels coeficients de sortida de la FFT,de les mostres imparells es multipliquen per <math>W_N^K=e^{-i\frac{2\pi }{N}k}</math>, on ''k'' es la posició del vector de sortida, i es sumen a les mostres parells. També, les FFT de N/2 és pot resoldre de la següent manera. realitzant aquesta operació de manera recursiva fins a obtenir una FFT de grandariagrandària 2. El seu resultat és:

Fa la FFT del vector x. 'X' és un vector de nombres complexes 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 altre opció de la FFT és especificar el nombre de punts amb el quualqual es vol fer la FFT.

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