Transformada ràpida de Fourier: diferència entre les revisions
Contingut suprimit Contingut afegit
m neteja i estandardització de codi |
m Manteniment de plantilles |
||
Línia 1:
[[Fitxer:FFT Example.jpg|miniatura|FFT de la suma de 2 senyal sinusoidals de 300 i 600 Hz (imatge superior) Resultat de la FFT (imatge inferior)]]
La '''transformada ràpida de Fourier''' (o '''FFT''', de l'[[anglès]] '''Fast 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).<ref>{{Ref-web|url= https://betterexplained.com/articles/an-interactive-guide-to-the-fourier-transform/|títol=An Interactive Guide To The Fourier Transform – BetterExplained| consulta=2017-03-01|llengua=anglès| editor=betterexplained.com
Es calcula de forma computacional a través d'un determinat [[algorisme]]. En termes d'eficiència, la DFT té un cost temporal d'O(n²) i la FFT d'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, es necessiten dues condicions indispensables: que el senyal discret a transformar sigui periòdic 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 a 10.
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.<ref>{{Ref-web|url= http://www.earlevel.com/main/2002/08/31/a-gentle-introduction-to-the-fft/|títol=A gentle introduction to the FFT {{!}} EarLevel Engineering| consulta=2017-03-01|llengua=anglès| editor=www.earlevel.com
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.<ref>{{Ref-publicació|cognom=|nom=www.askamathematician.com|article=Q: What is a Fourier transform? What is it used for?|publicació=Ask a Mathematician / Ask a Physicist|llengua=anglès|url= http://www.askamathematician.com/2012/09/q-what-is-a-fourier-transform-what-is-it-used-for/|data=2012-09-25|pàgines=}}</ref>
Línia 12:
== Definició ==
Siguin ''x''<sub>0</sub>, ...., ''x''<sub>''n''-1</sub> [[nombre complex|nombres complexos]]. La transformada discreta de Fourier (DFT) es defineix com <ref>{{Ref-web|url= http://hyperphysics.phy-astr.gsu.edu/hbase/Math/fft.html|títol=Fast Fourier Transforms| consulta=2017-03-01|llengua=anglès| editor=hyperphysics.phy-astr.gsu.edu
:[[Fitxer:DIT-FFT-butterfly.png|miniatura|Càlcul gràfic]]<math> f_j = \sum_{k=0}^{n-1} x_k e^{-{2\pi i \over n} jk }
Línia 29:
=== Algorisme de Cooley-Tukey ===
[[Fitxer:Cooley-tukey-general.png|miniatura|Algorisme de 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
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 37:
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 nombre de mostres (N) que es pot agafar ha de ser potència de 2.
=== 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
* '''[[FFT del factor primer]]'''''(també anomenat algorisme de Good-Thomas).''
-Semblant al de Cooley-Tukey però amb N essent un nombre primer.
Línia 48:
== FFT amb Matlab ==
* >> X = fft(x) <ref>{{Ref-web|url= https://es.mathworks.com/help/matlab/ref/fft.html|títol=Fast Fourier transform - MATLAB fft| consulta=2017-03-01|llengua=anglès| editor=es.mathworks.com
Fa la FFT del vector x. 'X' és un vector de nombres complexos 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 altra opció de la FFT és especificar el nombre de punts amb el qual es vol fer la FFT.
| |||