4.5 A gyors Fourier transzformáció
A diszkrét Fourier transzformációt illetve annak inverzét definíció szerint megvalósító algoritmusokkal bármilyen jel spektruma meghatározható. Azonban az eljárásnak van egy hátránya: az, hogy rendkívül számításigényes. Ennek oka, hogy mind a k mind az n indexek értékeit az eljárás során 0-ról N-re kell növelni az eredmény kiszámításához. Ez N2 számítási műveletet igényel. Az egyenleteket megvizsgálva látjuk, hogy azok szorzásokból és összeadásokból állnak. Azonban tudjuk, hogy a jelenlegi számítógépeken az összeadás ideje elhanyagolható a szorzásokhoz képest. Így egy N=1000 pontos diszkrét Fourier transzformáció végrehajtása 106 műveletet igényel. Matematikailag azt mondjuk, hogy a DFT O(N2) (ejtsd: ordo N2) műveletet igényel.
A diszkrét Fourier
transzformáció számítási igényét Cooley és Tukey 1965-ben publikált
algoritmusukkal jelentősen csökkentették. Algoritmusuk az „oszd meg és
uralkodj" elv alapján működik. Mivel az eredeti DFT N2 szorzást
igényel, ezért, ha az adatokat szétválasztjuk két egyforma részre, akkor az
egyes részek önmagukban szorzást igényelnek. A teljes transzformáció pedig nyilván
műveletet. Így, ha a
két transzformáció eredményei összekombinálhatóak, akkor ezzel a metódussal
számítási időt lehet megtakarítani. Felvetődik a kérdés, hogy a fenti ötletet
hogyan lehet a gyakorlatban megvalósítani.
Vezessük be a
következő jelölést: . Ezzel a DFT a következő alakban írható fel:
k=0,1,2,...,N-1
Csoportosítsuk úgy a fenti egyenletet, hogy külön összegezzük a páros, illetve páratlan indexű tagokat. Ekkor a fenti egyenlet így írható:

Másképpen:

Azonban:

Így:

Vagyis az
eredeti DFT felírható páros és páratlan indexű tagok diszkrét Fourier
transzformáltjainak összegeként. Igaz a páratlan indexű tagúak transzformáltját
még be kell szorozni -val. Induláskor
érdemes N-et 2 egészkitevőjű hatványának választani, mert ekkor a fenti eljárás
tovább folytatható egészen addig, amíg az alsó határhoz a 2 pontos DFT-hez nem
érünk.
Példaként vegyünk egy 8 számból álló sorozatot (N=8).
Ezt bontsuk fel két csoportra:
Újra bontsuk két-két csoportra:
Így összesen négy darab 2 pontos DFT-t kell kiszámolni.
A DFT kiszámolásának ezt az algoritmusát gyors Fourier transzformációnak nevezzük, angolul Fast Fourier Transformation (FFT).
Az algoritmus működésére tekintsünk egy egyszerű példát, ahol a hossz, N=4. Ekkor a transzformáció a következő lesz:

De:

Így a z FFT a következő lesz:

Minden egyes k-ra végig kiszámolva az algoritmus a következő:

A számolásnál figyelembe vettük, hogy

és

Az FFT legfőbb előnye a DFT-vel szemben, hogy a transzformáció végrehajtásához lényegesen kevesebb műveletszám kell. A DFT-nél a műveletszám N2, míg az FFT fenti megvalósításánál ez az érték Nlog2N. Egy 1024 pontos DFT esetén a műveletszám 1048576 addig az FFT-nél ez 10240, azaz a sebesség növekedés ebben az esetben durván százszoros.