Algorisme de Cooley–Tukey

L'algorisme de Cooley–Tukey és l'algorisme de transformada ràpida de Fourier (FFT) més freqüent. Per tal d'aplicar la FFT, re-expressa la transformada discreta de Fourier (DFT) d'un compost arbitrari n = n1n2 en termes de n1 DFTs de mida n2, recursivament, per reduir el temps computacional a O(n log n).[1][2]

ProcedimentModifica

El problema d'utilitzar el mètode de DFT és que requereix una matriu de multiplicacions i sumes molt llarga sobre tots els elements, cosa que implica operacions molt complexes i que requereixen molt de temps computacional.[3] L'algorisme de Cooley–Tukey calcula la DFT directament amb menys sumes i sense matrius de multiplicacions. Per fer-ho, es divideix la matriu a la qual volem aplicar el FFT en dues parts, una pels elements amb índex parell i l'altra pels elements amb índex senar. Posteriorment es continua dividint la matriu recursivament utilitzant el mateix criteri, fins que s'obté una sèrie de matrius de mida suficientment petita per aplicar el mètode DFT.[1]

Dit d'una altra manera, per poder aplicar la FFT és necessari utilitzar la DFT, aplicant la següent fórmula:[4]

 

Ara bé, apliquem la fórmula a una sèrie de matrius amb valors FFT   obtingudes per subdivisió recursiva de la matriu original:

 

La base de l'algorisme són els diagrames Butterfly, aplicats a cadascuna de les matrius simples obtingudes per tal de reconstruir el símil al FFT de la matriu original.

Diagrames ButterflyModifica

Els diagrames Butterfly (o diagrames papallona) mostren per cada element de la matriu on es situen abans, durant i després de cada FFT.

Donada una matriu de dos valors a[0] i a[1] volem saber on quedaràn situats a la matriu posteriorment a la FFT, aquesta estructura creuada és la que s'anomena papallona:

 

 

Ara bé, la segona meitat dels valors W és sempre el negatiu de la primera meitat, per tant podem definir A1 de la següent manera:

 

Això permet estalviar molt d'espai d'emmagatzematge i reduir el temps computacional requerit.[2] Si necessitem combinar més elements, apliquem aquest mètode simple de papallona esglaonadament.

ReferènciesModifica

  1. 1,0 1,1 Cooley, James W.; Tukey, John W. «An algorithm for the machine calculation of complex Fourier series». Math. Comput., 19, 90, 1965, pàg. 297–301. DOI: 10.2307/2003354. JSTOR: 2003354.
  2. 2,0 2,1 Frigo, M.; Johnson, S. G. «The Design and Implementation of FFTW3». Proceedings of the IEEE, 93, 2, 2005, pàg. 216–231. DOI: 10.1109/JPROC.2004.840301.
  3. Cooley, James W.; Lewis, Peter A. W.; Welch, Peter D. «Historical notes on the fast Fourier transform». IEEE Transactions on Audio and Electroacoustics, 15, 2, 1967, pàg. 76–79. DOI: 10.1109/tau.1967.1161903.
  4. Danielson, G. C., and C. Lanczos, "Some improvements in practical Fourier analysis and their application to X-ray scattering from liquids," J. Franklin Inst. 233, 365–380 and 435–452 (1942).