Transformada ràpida de Fourier: diferència entre les revisions
Contingut suprimit Contingut afegit
Robot estandarditza i catalanitza referències, catalanitza dates i fa altres canvis menors |
Correcció d'enllaços |
||
Línia 30:
=== Algorisme de Cooley-Tukey ===
[[Fitxer:Cooley-tukey-general.png|miniatura|Fig.2 Algorisme Cooley–Tukey]]
Existeixen diferents algorismes per calcular la FFT, però el més conegut i utilitzat és el de [[Algorisme de Cooley–Tukey|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.<ref>{{Ref-web|url= http://sip.cua.edu/res/docs/courses/ee515/chapter08/ch8-2.pdf|títol=Cooley–Tukey algorithm| consulta=1/03/2017|llengua=anglès| editor=sip.cua.edu|data=}}</ref>
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 els imparells). Cada un dels coeficients de sortida de la FFT,de les mostres imparelles es multipliquen per <math>W_N^K=e^{-i\frac{2\pi }{N}k}</math>, on ''k'' és la posició del vector de sortida, i se sumen a les mostres parelles. Les 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 resultat és:
Línia 36:
:<math>X[1]=x[0]-x[1]</math>.
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 "
=== Altres algorismes <ref>{{Ref-web|url= http://www.dspguide.com/ch12/2.htm|títol=How the FFT works| consulta=2017-03-01|llengua=anglès| editor=www.dspguide.com|data=}}</ref> ===
| |||