Viquipèdia

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

Exploració interactiva de l'historial
← Edició anteriorEdició següent →
Contingut suprimit Contingut afegit
VisualWikitext
m LanguageTool: correcció d'errors ortogràfics i gramaticals
Línia 8:
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ó ==
Línia 19:
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 freqü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 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.
Línia 28:
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 elels imparells). Cada un dels coeficients de sortida de la FFT,de les mostres imparellsimparelles es multipliquen per <math>W_N^K=e^{-i\frac{2\pi }{N}k}</math>, on ''k'' esés la posició del vector de sortida, i esse sumen a les mostres parellsparelles. També, lesLes 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 seu resultat és:
:<math>X[0]=x[0]+x[1]</math>
:<math>X[1]=x[0]-x[1]</math>.
Línia 40:
 
* >> X = fft(x,N)
Si la longitud de 'x' és menor que N, el vector s'omple amb zeros. Si esés majormé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 quualqual es vol fer la IFFT. (També, com abans >> x = ifft(X,N))
 
*>> X = fftshift(X)
Línia 56:
-Basat en l'aproximació per factorització polinomial.
* '''[[FFT de Rader]]'''
-Es basa ena expressar la DFT com una convolució cíclica. N ha de ésserser, 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).
Obtingut de «https://ca.wikipedia.org/wiki/Transformada_ràpida_de_Fourier»