A gyors Fourier-transzformáció (FFT) Egy analóg jel spektrumát az esetek döntő többségében számítástechnikai eszközökkel határozzuk meg. A jelet mintavételezzük és elvégezzük a mintasorozat diszkrét Fouriertranszformációját. A transzformációhoz nagyszámú komplex szorzás és komplex összeadás elvégzésére van szükség. Egy 8 mintából álló sorozat esetén a transzformált kiszámítása az alábbi: 7
X(k) = F {x [ k ]} = ∑ x(n) ⋅ e− jk 2 πn /8 , k = 0,..., 7
(5.41)
n =0
Vezessük be a k2π/8 = K (k = 0,...,7) jelölést és írjuk fel az összeget:
X(k) = x(0) ⋅ e− jK0 + x(1) ⋅ e− jK1 + x(2) ⋅ e− jK2 + x(3) ⋅ e− jK3 + + x(4) ⋅ e− jK 4 + +x(5) ⋅ e− jK5 + x(6) ⋅ e− jK6 + x(7) ⋅ e− jK7 k = 0,..., 7
(5.42)
Az összegnek nyolc összetevője van. Mindegyik tag tartalmaz egy szorzást. A szorzások exponenciális tagja mindig komplex, a minta értéke pedig valós vagy komplex. (A DSP-ben mindig valós mintákkal dolgozunk.) A nyolc szorzatot még össze is kell adni, és ezeket a műveleteket el kell végezni a k mindegyik értéke esetén. Ezzel minden mintához nyolc harmonikus összetevőt rendeltünk. A fenti műveletsort nevezik 8 pontos diszkrét Fouriertranszformációnak. Műveletigénye 82 =64 komplex szorzás és 8x7 =56 komplex összeadás. Általánosítva az N pontos DFT műveletigénye N2 komplex szorzás és N(N-1) komplex összeadás. Egy 1024 pontos DFT esetén ez kb. egymillió komplex szorzást és egymillió komplex összeadást jelent. Egyértelmű követelmény, hogy ezt a számot valamilyen módon csökkenteni kell. Ha figyelembe vesszük, hogy a számítások meglehetős számú belső redundanciát tartalmaznak erre van is lehetőségünk. Például ha k = 1 és n = 2, akkor e− jk 2 πn /8 = e− jπ / 2 . Ugyanez a helyzet k =2 és n = 1 estén is. A DFT műveletigényének csökkentésére az első algoritmust 1965-ben dolgozták ki (Cooley és Tukey). A módszer lényege az időbeli decimálás (Decimation In Time, DIT). Az algoritmust gyors Fourier-transzformációnak (Fast Fourier Transform) hívják és röviden csak FFT-nek szokás nevezni. 1024 pont esetén az FFT és a DFT műveletigényének aránya 1:204.8, N pontra általánosítva a számítási műveletekben N 2 − ( N 2) log 2 N megtakarítás érhető el. Az N pontos DFT az alábbi összefüggéssel számítható: N −1
X1 ( k ) = ∑ x n e − j2 πnk / N
k = 0,..., N − 1
,
(5.43)
n=0
Ha bevezetjük az alábbi jelölést:
WN = e − j2π/ N ,
(5.44)
akkor az egyenlőségünk a következőképpen alakul: N −1
X1 ( k ) = ∑ x n WNkn n=0
,
k = 0,..., N − 1
(5.45)
Ezen a ponton érdemes felírni néhány további, WN -re vonatkozó összefüggést:
WN2 = (e− j2 π / N ) = e− j2 π 2 / N = e− j2 π /(N 2) = WN / 2 2
(5.46)
WN(k + N 2) = WNk WNN 2 = WNk e− j(2 π / N)( N / 2) = WNk e− jπ = −WNk (5.47) Az eddigieket összegezve:
WN = e− j2 π / N
(a )
WN2 = WN / 2
( b)
(k + N / 2) N
W
(5.48)
= −W (c) k N
A fenti egyenletek által képviselt számítási redundanciák felhasználásával az eredeti mintasorozatunk két részre osztható, egyik a páros sorszámú, míg a másik a páratlan sorszámú mintákat tartalmazza. Mindegyik sorozatnak ugyanolyan hosszúnak kell lennie és páros darabszámú adatot (mintát) kell tartalmaznia. Ha a kiindulási mintasorozatunk netán páratlan számú mintából állt, ki kell egészíteni egy nulla értékű mintával. De mivel a DFT-t szinte mindig 2n darabszámú mintán végezzük el, a két követelmény automatikusan teljesül. A két részre osztás lehetővé teszi, hogy az X1(k) eredeti N pontos DFT-je helyett felírhassuk az X11(k) és X12(k) N/2 pontos DFT-ket. Ezt a folyamatot azután tovább ismételhetjük mindaddig, amíg N/2 darab 2 pontos DFT-ig nem jutunk. A két pontos DFT-k kimeneti adatait megfelelően négyes csoportokba kombinálva N/4 darab 4 pontos DFT-t kapunk, de ezek eredményét már nem kell számítani (megvannak), és így tovább mindaddig, amíg a végső N pontos DFT végeredményét, az X1(k)-t meg nem kapjuk. Minden egyes lépésben találunk egy olyan közös tényezőt, ami a WN valamelyik hatványa, így a kiszámítása csak egyszer szükséges, ismételt előfordulásakor már nem. Ezzel tehát az (5.45) átírható az alábbi módon: N 2−1
∑x
X1(k) =
N 2−1 2n
2nk N
W
+
n =0
N / 2−1
∑x
2n +1
WN(2n +1)k =
n =0
Páros sorszámú min ták
=
∑x
2n
2nk N
W
Páratlan sorszámú min ták N / 2−1
+W
k N
n =0
∑x
2n +1
WN2nk
2n +1
WNnk2
(5.49)
n =0
k = 0, …, N −1 Felhasználva az (5.48 a) összefüggést (5.49) így alakul: N 2−1
X(k) =
∑x
N 2−1 2n
nk N 2
W
+W
n =0
k N
∑x n =0
,
(5.50)
k = 0, …, N −1 ami még így is írható:
X1 (k ) = X11 ( k ) + WNk X12 ( k ) , k = 1, … , N −1 Foglaljuk össze az eddigieket egy táblázatban 8 pontos DFT esetén:
(5.51)
Számítsuk ki a 6. sorban szereplő kifejezések értékét:
X 21 (k ) = x 0 + WNk 4 x 4
k = 0, …, N 4, vagyis k = 0,1
(5.52)
Tehát
X 21 (0) = x 0 + x 4 Míg
X 21 (1) = x 0 + WN 4 x 4 = x 0 + W2 x 4 = x 0 + e− j2 π 2 x 4 = = x 0 + e − jπ x 4 = x 0 − x 4 Hasonlóképpen:
X 22 (0) = x 2 + x 6
X 22 (1) = x 2 − x 6
X 23 (0) = x1 + x 5
X 23 (1) = x1 − x 5
X 24 (0) = x 3 + x 7
X 24 (1) = x 3 − x 7
amiből azt láthatjuk, hogy a k = 0 és a k = 1 esetben kiszámítható értékek csak egy előjellel térnek el egymástól. Gondolatmenetünket alkalmazhatjuk X21(k) (k = 0, 1, 2, 3) esetén is:
X11 ( k ) = X 21 ( k ) + WNk 2 X 22 (k )
(5.53)
X11 (0) = X 21 (0) + WN0 2 X 22 (0) = X 21 (0) + X 22 (0)
(5.54)
így
X11 (1) = X 21 (1) + WN1 2 X 22 (1) = X 21 (1) + e− jπ 2 X 22 (1) = = X 21 (1) − jX 22 (1)
(5.55)
X11 ( 2) = X 21 (2) + WN2 2 X 22 ( 2) = X 21 (1) + e− j(2 π 8)2⋅2 X 22 ( 2) = = X 21 ( 2) + e− jπ X 22 ( 2) = X 21 (2) − X 22 ( 2)
(5.56)
Most
X 21 ( 2) = x 0 + WN2 4 x 4 = x 0 + W22 x 4 = x 0 + x 4 = X 21 (0) és
X 22 ( 2) = x 2 + WN2 4 x 6 = x 2 + x 6 = X 22 (0) ezzel (5.56):
X11 (2) = X 21 (0) − X 22 (0)
(5.57)
X11 (3) = X 21 (3) + WN3 2 X 22 (3)
(5.58)
Most
X 21 (3) = x 0 + WN3 4 x 22 X 4 = x 0 + e− j(2 π 2)⋅3 x 4 = = x 0 + e− j3π x 4 = x 0 − x 4 = X 21 (1) és
X 22 (3) = x 2 − x 6 = X 21 (1) ezzel (5.58) így írható:
X11 (3) = X 21 (1) + e− j(2 π 4)⋅3 X 22 (1) = X 21 (1) + e− j3π 2 X 22 (1) =
= X 21 (1) + jX 22 (1)
(5.59)
Összefoglalva:
X11 (0) = X 21 (0) + X 22 (0) = X 21 (0) + W80 X 22 (0) (a ) X11 (2) = X 21 (0) − X 22 (0) = X 21 (0) − W80 X 22 (0)
( b)
X11 (1) = X 21 (1) − jX 22 (1) = X 21 (1) + W80 X 22 (1)
(c)
X11 (3) = X 21 (1) + jX 22 (1) = X 21 (1) − W80 X 22 (1)
(d)
A számítás menetét összefoglalhatjuk a következő oldalon látható ún. lepkeábrán.
(5.60)
Az FFT műveleti nyeresége az alábbi táblázatban található:
