Szybka transformacja Fouriera
Spis treści
1. Nieefektywność obliczeniowa DFT
2. Usprawnienia zaproponowane przez Cooley a i Tuckey a
3. Porównanie efektywności DFT i FFT
1
Cechy charakterystyczne procedury
obliczeniowej DFT
Obliczenia DFT można zapisać w postaci macierzowej
%5ń(0) s(0)
Ą# ń# Ą# ń#Ą# ń#
ó# Ą#ó# Ą#
%5ń(1)Ą# ó# ! ! ę! s(1)
ó# Ą# ó# Ą#ó# Ą#
ó# Ą# ó# Ą#ó# Ą#
%5ń(2) ! ! ę! ! ! ę! s(2)
ó# Ą# ó# Ą#ó# Ą#
ę! ! !
ó#%5ń(3)Ą# ó# Ą#ó#s(3)Ą#
=
ó#%5ń(4)Ą# ó# ! ! ! !Ą#ó#s(4)Ą#
ó# Ą# ó# Ą#ó# Ą#
! ! ę!
ó#%5ń(5)Ą# ó# Ą#ó#s(5)Ą#
ó#%5ń(6)Ą# ó# ę! ! ! ę! ! ! Ą#ó#s(6)Ą#
ó# Ą# ó# Ą#ó# Ą#
ę! ! !
ó# Ą#ó#
Ś# Ł# Ś#
Ł#%5ń(7)Ą# ó# Ś#Ł#s(7)Ą#
gdzie
1 j
= - 1 j = - 1 + j = 1 + j
= -
-
2 2
2 2 2 2 2 2
2
Przykład dublowania obliczeń
Obliczenia DFT można zapisać w postaci macierzowej
%5ń(0) s(0)
Ą# ń# Ą# ń#Ą# ń#
ó# Ą#ó# Ą#
%5ń(1)Ą# ó# ! ! ę! s(1)
ó# Ą# ó# Ą#ó# Ą#
ó# Ą# ó# Ą#ó# Ą#
%5ń(2) ! ! ę! ! ! ę! s(2)
ó# Ą# ó# Ą#ó# Ą#
ę! ! !
ó#%5ń(3)Ą# ó# Ą#ó#s(3)Ą#
=
ó#%5ń(4)Ą# ó# ! ! ! !Ą#ó#s(4)Ą#
ó# Ą# ó# Ą#ó# Ą#
! ! ę!
ó#%5ń(5)Ą# ó# Ą#ó#s(5)Ą#
ó#%5ń(6)Ą# ó# ę! ! ! ę! ! ! Ą#ó#s(6)Ą#
ó# Ą# ó# Ą#ó# Ą#
ę! ! !
ó# Ą#ó#
Ś# Ł# Ś#
Ł#%5ń(7)Ą# ó# Ś#Ł#s(7)Ą#
Wynika stąd
%5ń(0) = s(0) + s(2) + s(4) + s(6) + (s(1) + s(3) + s(5) + s(7))
%5ń(4) = s(0) + s(2) + s(4) + s(6) -(s(1) + s(3) + s(5) + s(7))
3
Nakład obliczeniowy dla dyskretnej
transformacji Fouriera
Dyskretne widmo jest obliczane przy pomocy wzoru
2Ą
N -1
- j
kn
N
gdzie
%5ń(k) = wN = e
"s(n)w
N
n=0
2
2N mnożeń bo: jest N składników sumy (ze względu na n), jest N
równań (ze względu na k) i są to mnożenia liczb rzeczywistych przez
zespolone.
4
Cooley i Tuckey 1965 rok
Dla poprawy efektywności, przeprowadzmy obliczenia osobno dla próbek
o numerach parzystych i osobno o numerach nieparzystych. Otrzymamy
N 2-1 N 2-1
N -1
kn 2 (
%5ń(k) = s(2n)wNnk +
"s(n)w = ""s(2n +1)wN2n+1)k
N
n=0 n=0 n=0
N 2-1 N 2-1
kn k kn
= s(2n)wN / 2 + wN
""s(2n +1)wN / 2
n=0 n=0
k
%5ń(k) = %5ńp(k) + wN %5ńn(k)
k "{0,1,..., N / 2 -1}
dla
2Ą 4Ą
- j - j
N N
gdzie wN = e wN / 2 = e
natomiast
A co z wartościami dla k "{N / 2,K, N -1}?
5
Okresowość widm dyskretnych
k
Otrzymaliśmy %5ń(k) = %5ńp(k) + wN %5ńn(k)
Widma zarówno dla próbek o numerach parzystych jak i nieparzystych
są funkcjami okresowymi, tzn.
%5ńp (k) = %5ńp (k - N / 2)
%5ńn (k) = %5ńn (k - N / 2)
Dodatkowo zauważmy, że
2Ą 2Ą 2Ą
- j k - j k - j (k -N 2) Im(wk )
k jĄ k
N N N
wN = e = -e e = -e = -wN-N 2
k
wN = -1
Jeśli na przykład k = 4 i N = 8, to
k
Re(wk )
wN-N 2 = 1
6
Wzór wynikający z okresowości
funkcji dyskretnych
Z warunków
%5ńp (k) = %5ńp (k - N / 2)
k k
wN = -wN-N 2
oraz
%5ńn (k) = %5ńn (k - N / 2)
wynika, że
k
%5ń(k) = %5ńp(k) + wN %5ńn(k)
jest równoważne
k
ż#
dla k = 0,1,...,N / 2 -1
#%5ń (k) + wN %5ńn(k)
p
%5ń(k) =
#%5ń (k - N / 2) - wN-N / 2%5ńn (k - N / 2) dla k = N / 2,...,N -1.
k
#
p
#
7
Efektywność algorytmu
Ilość mnożeń w otrzymanym wzorze
k
ż#
dla k = 0,1,...,N / 2 -1
#%5ń (k) + wN %5ńn(k)
p
%5ń(k) =
#%5ń (k - N / 2) - wN-N / 2%5ńn(k - N / 2) dla k = N / 2,...,N -1.
k
#
p
#
2
wynosi
N + 2N
bo zarówno jak i %5ńn (k) dla k = 0, 1, ..., N/2-1 wymaga 2(N/2)2
%5ń (k)
p
k
mnożeń i dodatkowo trzeba wykonać 4(N/2) mnożeń dla
wN %5ńn (k)
(mnożenie liczb zespolonych!).
Przedstawiony algorytm jest bardziej efektywny jeśli spełniona jest
nierówność
2 2
2N > N + 2N
czyli musi być N > 2, a przecież tak jest zawsze!
8
Szybka transformacja Fouriera
ang. Fast Fourier Transform - FFT
Dla zwiększenia efektywności obliczeń, przedstawiony schemat można zastosować
do obliczenia widm dla próbek parzystych i nieparzystych, a również i dalej.
Wymaga to dzielenia ilości próbek przez 2. Cooley i Tuckey przyjęli N = 2M.
Stosując M - krotnie podział na próbki o numerach parzystych i nieparzystych, na
końcu otrzymujemy dla N = 2
%5ń(0) = s(0) + s(1)
%5ń(1) = s(0) - s(1)
s(0) %5ń(0)
%5ń(1)
s(1)
-
9
Operacje motylkowe
przebieg 1 przebieg 2 przebieg 3
s(0)
%5ń(0)
0
WN
s(1)
%5ń(4)
-1
grupa 0
0
WN
s(2)
%5ń(2)
-1
0 2
WN WN
s(3)
%5ń(6)
grupa 0 grupa 1
-1 -1
0
s(4) WN
%5ń(1)
-1
0 1
s(5)
WN WN
%5ń(5)
-1 -1
grupa 2
0
s(6)
2
WN
%5ń(3)
WN
-1 -1
s(7)
0 2 3
%5ń(7)
WN WN WN
-1 -1 -1
grupa 0 grupa 1 grupa 3
10
Efektywność operacji motylkowych
Ilość próbek
N = 2M.
M = lg2 N
Poziomów jest a na każdym z nich N/2 operacji motylkowych.
Czyli ostatecznie mnożeń (na ogół liczb zespolonych) jest .
N
4M = 2N log2 N
2
Reasumując, ilość mnożeń w dyskretnej transformacji Fouriera jest proporcjonalna
do drugiej potęgi ilości próbek a w szybkiej transformacji Fouriera proporcjonalna
do iloczynu ilości próbek i logarytmu z ilości próbek.
DFT ~ N2
FFT ~ N log2 N
11
Porównanie efektywności DFT i FFT
Ilość mnożeń DFT i FFT dla N próbek
N
4 8 16 32 64 128
32 128 512 2048 8192 32768
2
2N
16 48 128 320 768 1792
2N lg2 N
x 10
1.8
2
2N
1.4
1
0.6
2N log2 N
0.2
12
0 20 40 60 80 100
Wyszukiwarka
Podobne podstrony:
Zdania porównawczePORÓWNANIE TECHNOLOGI ŁĄCZENIA MASZYN METODĄ KLEJENIA METODAMonitory studyjne porównanie 15Co daje nauce prawoznawstwo porownawczeAnaliza porównawcza rodzajów, przyczyn i okoliczności zgonów na podstawie badań sekcyjnych (2)Porównanie światopoglądu czterech epok2004 11 Porównanie serwerów relacyjnych baz danych Open Source [Bazy Danych]Antoszewski Demokracje europy środkowo wschodniej w perspektywie porównawczejPORÓWNANIE MITOZY I MEJOZY2014 vol 09 UE i FR PORÓWNANIE SKUTECZNOŚCI PROWADZENIA POLITYKI BEZPIECZEŃSTWA ENERGETYCZNEGO [NARudyard Kipling „Księga dżungli” porównajporównanie uwaga dowolna i mimowolnaPorównanie mapy Merkatora ze światem współczesnymPorównanie, Kipke GeraetePorównanie BWP 2002więcej podobnych podstron