Transformada ràpida de Fourier: diferència entre les revisions
Contingut suprimit Contingut afegit
Cap resum de modificació |
Cap resum de modificació |
||
Línia 10:
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 [[filtrat 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''<sub>0</sub>, ...., ''x''<sub>''n''-1</sub> [[nombre complex|nombres complexes]]. La transformada discreta de Fourier (DFT) es defineix com
:<math> f_j = \sum_{k=0}^{n-1} x_k e^{-{2\pi i \over n} jk }
\qquad
j = 0,\dots,n-1. </math>
L'evaluació 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üèntment 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 descomposar, 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.
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:
:<math>x[n] = IDFT\{X[k]\}=\frac{1}{N}\left(DFT\left\{X^*[k]\right\}\right)^*</math>
== Algorisme Cooley-Tukey ==
| |||