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

La '''transformada ràpida de Fourier''' (o '''FFT''', de l'[[anglès]] '''fastFast 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 [[IDFT|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, aen una transformada de 1024 mostres. Fent la DFT es necessitarien aproximadament <math>10^6</math> operacions i fent la FFT, en canvi, unes 5000.

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 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 etapes. 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.

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 esés que la longitud 'x' sigui un nombre primer. Una altre opció de la FFT esés especificar el nombre de punts amb el quequual es vol fer la FFT.

Si la longitud de 'x' és menor que N, el vector s'omple amb zeros. Si es mayormajor, el vector es truncadotrunca.

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