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 = n₁n₂ en termes de n₁ DFTs de mida n₂, recursivament, per reduir el temps computacional a O(n log n).

Procediment

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. 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.

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

$X_{k}=\sum _{n=0}^{N-1}x_{n}\cdot e^{-2\pi ikn/N}$

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

$W_{N}^{k}=e^{-2\pi ik/N}$

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 Butterfly

Els diagrames Butterfly (o diagrames papallona) mostren per cada element de la matriu on se 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:

$A_{0}=a_{0}+W_{2}^{0}a_{1}$

$A_{1}=a_{0}+W_{2}^{1}a_{1}$

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

$A_{1}=a_{0}-W_{2}^{0}a_{1}$

Diagrama Butterfly de Cooley-Tukey per matrius amb dos elements

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

Diagrama Butterfly de Cooley-Tukey per matrius amb dos elements