Hangkártyák programozása retro 18.

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:

1. nyolc alappont,
2. ezekből négy darab két alappontos transzformált előállítása,
3. ezekből két darab négy alappontos transzformált előállítása,
4. 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 f_i 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 f_q alapponton kezdődik,
• p: a rész-transzformált alappont sorozata f_i egymástól p-re lévő elemeiből áll (p mindig kettő hatványa).

F.20. alapján:

(7.35)

Mivel f_i-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 f_i transzformálandó minta-sorozat egymás utáni elemeivel. Igazolás a (7.36) alapján D_r 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:

1. Az első állítás alapján a kiinduló f_i adatsor egyben a p=N eset rész-transzformáltjainak sora.
2. A harmadik állítás log₂N-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.
3. A második állítás szerint utóbbi azonos a keresett transzformálttal.

Hírdetés