Sygnały i Systemy
Sygnały i Systemy
Wykład 11
Szybka Transformata Fouriera - FFT
Grzegorz Masłowski
Politechnika Rzeszowska
Zakład Podstaw Elektrotechniki i Informatyki
Sem. zimowy 2002/2003
Co to jest FFT ?
W 1965 r. został opublikowany przez Cooleya i Tuckeya algorytm
zwany potocznie pod nazwą szybkiego przekształcenia Fouriera FFT
(Fast Fourier Transform).
Ogólnie można powiedzieć, że FFT robi to samo co DFT tylko dużo
bardziej efektywnie, tzn. wymaga znacznie krótszego czasu obliczeń
komputerowych do wyznaczenia widma sygnału dyskretnego.
Do dnia dzisiejszego wdrożono wiele różnych wersji FFT, które
implementowane sÄ… w standardowych programach komputerowych
(MathCAD, Mathematica, PSpice, Matlab, ATP-EMTP, CDEGS i
wiele innych) w celu wyznaczenia częstotliwościowej zawartości ciągu
z dziedziny czasu.
2
Związek pomiędzy DFT i FFT ?
Aby wyznaczyć N-punktową DFT należy wykonać N 2 działań,
ponieważ dla każdego prążka w widmie należy wykonać N mnożeń
(a ilość prążków równa się N).
Przed wprowadzeniem algorytmu FFT obliczenia dla np. 1000
punktowej DFT można było dokonać tylko w niektórych ośrodkach
badawczych i uniwersyteckich centrach komputerowych. Obecnie
1024 punktową FFT można obliczyć w ciągu niespełna ułamka
sekundy na komputerze domowym.
3
Związek pomiędzy DFT i FFT ?
Liczba mnożeń zespolonych dla N punktowej FFT wynosi:
N
Å" log2 N
2
N = 10
N = 100
Liczba działań
Liczba działań
DFT
DFT
FFT
FFT
4
Algorytm FFT ?
Wszystkie dostępne algorytmy FFT wykorzystują możliwości
zmniejszenia długiego algorytmu DFT przez jego podział na krótsze i
prostsze obliczenia DFT.
Dla ułatwienia dalszych rozważań wygodnie jest zapisać wzór na DFT
N -1
- j 2Ä„ nm / N
F [m ] =
"f [n ]e
n =0
N -1
nm
na postaci:
F[m] = f [n]Å"WN
"
n=0
- j2Ä„ / N
gdzie W = e jest pomocniczym współczynnikiem,
N
zwanym również współczynnikiem skrętu.
5
Algorytm FFT ?
Aby dojść do algorytmu FFT na początku należy podzielić ciąg
f [n ]
na 2 części, zawierające odpowiednio elementy parzyste i nieparzyste
ciÄ…gu:
(N / 2)-1 (N / 2)-1
2nm (2n +1)m
F [m ] = f [2n ]Å"W + f [2n +1]Å"W
""
N
N
n =0 n =0
(2n +1)m 2nm m
W =W W
N N
N
(N / 2)-1 (N / 2)-1
2nm m 2nm
F [m ] = f [2n ]Å"W +W f [2n +1]Å"W
""
N N N
n =0 n =0
6
Algorytm FFT ?
Kwadrat współczynnika skrętu przy N punktowej DFT jest równy
współczynnikowi skrętu dla N/2 punktowej DFT:
2 - j 2Å"2Ä„ / N - j 2Ä„ /( N / 2)
W = e = e =W
N
N / 2
Czyli ostatnie równanie można zapisać jako:
(N / 2)-1 (N / 2)-1
nm m nm
F [m ] = f [2n ]Å"W +W f [2n +1]Å"W
""
N / 2 N N / 2
n =0 n =0
Już na tym etapie można zauważyć uproszczenie procedury, gdyż
nm
obydwa człony DFT zawierają ten sam składnik W przez co
N / 2
zmniejsza się liczba wymaganych działań.
7
Algorytm FFT ?
Dodatkowe przyspieszenie obliczeń uzyskamy zauważając, że
wyrażenia dla m > N / 2 są bardzo łatwe do obliczeń, ze względu na
symetriÄ™ DFT.
Na przykład dla m + N / 2 otrzymuje się:
(N / 2)-1 (N / 2)-1
n (m +N / 2) (m +N / 2) n (m +N / 2)
F [m + N / 2] = f [2n ]Å"W +W f [2n +1]Å"W
""
N / 2 N N / 2
n =0 n =0
Przy czym
- j 2Ä„ nN / 2
n (m +N / 2) nm nN / 2 nm nm
N / 2
W =W Å"W =W Å"e =W Å"1
N / 2 N / 2 N / 2 N / 2
N / 2
- j 2Ä„ N / 2
(m +N / 2) m N / 2 m nm
N
W =W Å"W =W Å"e =W Å"(-1)
N N N N / 2
N
8
Algorytm FFT ?
m + N / 2
Zatem dla mamy równanie:
(N / 2)-1 (N / 2)-1
nm m nm
F [m + N / 2] = f [2n ]Å"W -W f [2n +1]Å"W
""
N / 2 N N / 2
n =0 n =0
m
Natomiast dla mamy bardzo podobne równanie:
(N / 2)-1 (N / 2)-1
nm m nm
F [m ] = f [2n ]Å"W +W f [2n +1]Å"W
""
N / 2 N N / 2
n =0 n =0
Czyli wystarczy obliczyć wyrażenie wyłącznie dla m zmieniającego się
od 0 do (N/2)-1, a następnie wykorzystać te obliczenia do
wyznaczania pozostałych wartości DFT.
9
Algorytm FFT ?
Wygodnie jest zapisać uzyskane wyniki w postaci:
m
F[m + N / 2] = A[m]-WN B[m]
oraz
m
F[m + N / 2] = A[m]+WN B[m]
10
Przykład
Wyznaczyć 4-punktową DFT za pomocą dwóch 2-punktowych DFT
3 1 1
F[m] = f [n] W4mn = f [2n]W2mn +W4m f [2n +1] W2mn
" " "
n=0 n=0 n=0
lub
F[m] = (f [0]+ f [2]Å"W2m)+W4m(f [1]+ f [3]Å"W2m)
lub
F[m] = (f [0]+ f [2]Å"W42m)+W4m(f [1]+ f [3]Å"W42m)
11
Przykład
Konkretne wartości DFT wynoszą:
0 0 0
F [0] = (f [0]+ f [2]Å"W )+W (f [1]+ f [3]Å"W )
4 4 4
2 1 2
F [1] = (f [0]+ f [2]Å"W )+W (f [1]+ f [3]Å"W )
4 4 4
4 2 4
F [2] = (f [0]+ f [2]Å"W )+W (f [1]+ f [3]Å"W )
4 4 4
6 3 6
F [3] = (f [0]+ f [2]Å"W )+W (f [1]+ f [3]Å"W )
4 4 4
12
Przykład
Uwzględniając, że
2Ä„ 2Ä„
- j Å"4 - j Å"6
4 0 6 2
4 4
W =W = e = 1 oraz W =W = e = -1
4 4 4 4
otrzymuje siÄ™:
0 0 0
F [0] = (f [0]+ f [2]Å"W )+W (f [1]+ f [3]Å"W )
4 4 4
2 1 2
F [1] = (f [0]+ f [2]Å"W )+W (f [1]+ f [3]Å"W )
4 4 4
0 2 0
F [2] = (f [0]+ f [2]Å"W )+W (f [1]+ f [3]Å"W )
4 4 4
2 3 2
F [3] = (f [0]+ f [2]Å"W )+W (f [1]+ f [3]Å"W )
4 4 4
13
Przykład
Przedstawiony algorytm wyznaczania 4-punktowej DFT na podstawie
2-punktowej DFT często obrazuje się za pomocą grafu przepływu
majÄ…cego strukturÄ™ motylkowÄ….
14
Przykład
Wyznaczyć 8-punktową DFT, korzystając z wyprowadzonego
algorytmu.
4 punktowa DFT
3
nm
W
"f [2n ]
4
n =0
4 punktowa DFT
3
nm
W
"f [2n +1]
4
n =0
15
Wnioski do przykładu
Postępując analogicznie możemy podzielić dwie 4-punktowe DFT na
cztery 2-punktowe DFT i to byłby ostatni krok, gdyż na tym etapie
dzielenie pierwotnej 8-punktowej DFT byłoby zakończone.
Teraz już jest zrozumiałe dlaczego FFT wymaga, by liczba próbek
sygnału dyskretnego była równa:
23 = 8; 24 = 16; 25 = 32; 26 = 64; 27 = 128; 28 = 256;
29 = 512; 210 = 1024; 211 = 2048; 212 = 4096; 213 = 8192; itd.
2k
gdzie k jest liczbą naturalną i zależy od tego jak gęsto chcemy
próbkować sygnał analogowy.
16
Przykład FFT (N=8)
17