7.1.6. A gyors Fourier transzformáció (FFT)
Az FFT eljárás algoritmusát Cooley és Tukey dolgozták ki, majd 1965-ben publikálták. Ez az eljárás mondhatni forradalmasította a digitális jelfeldolgozást, mivel az addigi módszer rendkívül számításigényes volt, s így természetesen sok időt is vett igénybe.
Egy nyolc alappontú transzformáció lépései a következők:
- nyolc alappont,
- ezekből négy darab két alappontos transzformált előállítása,
- ezekből két darab négy alappontos transzformált előállítása,
- ezekből a nyolc alappontos transzformált, vagyis a végeredmény előállítása.
A 0-dik alappont a transzformációban részt vevő két alappont összege, míg az N/2-dik az előbbi két alappont különbsége, és így tovább. (Lásd F.19.)
F.19.
7.1.7. Az FFT algoritmus általános megfogalmazása és megvalósítása
Az algoritmust N alappontra adjuk meg, amely kettő hatványa. A transzformálandó függvény fi elemei komplex értékűek lehetnek. Az FFT algoritmus alapgondolata, hogy az N alappontú transzformáltat N/2 alappontú résztranszformáltból kell előállítani, utóbbiakat N/4 alappontra támaszkodó résztranszformáltakból, stb. Fogadjuk el a résztranszformált definíciójának a következőt:
(7.34)
Ahol r a résztranszformált elemeinek futó indexe, a felülre írt indexek pedig:
- q: a rész-transzformált alappont sorozata az fq alapponton kezdődik,
- p: a rész-transzformált alappont sorozata fi egymástól p-re lévő elemeiből áll (p mindig kettő hatványa).
F.20. alapján:
(7.35)
Mivel fi-nek N eleme van, a rész-transzformált N/p alappontra támaszkodik, ezért a transzformált ugyanennyi elemből áll:
(7.36)
Állítások:
Ha p=N, N darab rész-transzformáltunk van, amelyek egyenként megegyeznek az fi transzformálandó minta-sorozat egymás utáni elemeivel. Igazolás a (7.36) alapján Dr futó indexe csak r=0 lehet. (7.34) kifejezésben ezért az exponenciális tényező értéke 1. Maga a szumma az egyetlen k=0 értékre terjed ki. Ezzel:
(7.37)
Ha p=1, egy darab transzformáltunk van, ami azonos a kiszámítandó diszkrét Fourier transzformálttal. Igazolás: ha p=1, (7.35) szerint q csak 0 értékű lehet. Ezt felhasználva a (7.34) képletben, az alábbi egyenletre jutunk:
(7.38)
Ami megegyezik a diszkrét Fourier transzformált definíciójával.
A p=2P eset rész-transzformáltjainak birtokában a p=P eset összes rész-transzformáltja kiszámítható az alábbi rekurzív formula segítségével:
(7.39)
Igazolását nem vezetjük le.
A fenti három állítás alapján megadható az FFT algoritmus:
- Az első állítás alapján a kiinduló fi adatsor egyben a p=N eset rész-transzformáltjainak sora.
- A harmadik állítás log2N-szeri egymást követő ismétlésével megkapjuk a p=N/2, p=N/4, stb., végül a p=1-hez tartozó rész-transzformáltakat.
- A második állítás szerint utóbbi azonos a keresett transzformálttal.
