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

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

Vélemény, hozzászólás?

Adatok megadása vagy bejelentkezés valamelyik ikonnal:

WordPress.com Logo

Hozzászólhat a WordPress.com felhasználói fiók használatával. Kilépés / Módosítás )

Twitter kép

Hozzászólhat a Twitter felhasználói fiók használatával. Kilépés / Módosítás )

Facebook kép

Hozzászólhat a Facebook felhasználói fiók használatával. Kilépés / Módosítás )

Google+ kép

Hozzászólhat a Google+ felhasználói fiók használatával. Kilépés / Módosítás )

Kapcsolódás: %s