1
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
2
Cechy charakterystyczne procedury
obliczeniowej DFT
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
↓
←
↑
→
↓
←
↑
→
↓
←
↑
→
↑
←
↓
→
←
→
←
→
←
→
←
→
↓
←
↑
→
↑
←
↓
→
↑
←
↓
→
↑
←
↓
→
→
→
→
→
→
→
→
→
=
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
)
7
(
)
6
(
)
5
(
)
4
(
)
3
(
)
2
(
)
1
(
)
0
(
)
7
(
ˆ
)
6
(
ˆ
)
5
(
ˆ
)
4
(
ˆ
)
3
(
ˆ
)
2
(
ˆ
)
1
(
ˆ
)
0
(
ˆ
s
s
s
s
s
s
s
s
s
s
s
s
s
s
s
s
Obliczenia DFT można zapisać w postaci macierzowej
2
2
1
j
−
=
Ì
2
2
1
j
−
−
=
Ë
2
2
1
j
+
−
=
É
2
2
1
j
+
=
Ê
gdzie
3
Przykład dublowania obliczeń
Wynika stąd
(
)
)
7
(
)
5
(
)
3
(
)
1
(
)
6
(
)
4
(
)
2
(
)
0
(
)
0
(
ˆ
s
s
s
s
s
s
s
s
s
+
+
+
+
+
+
+
=
(
)
)
7
(
)
5
(
)
3
(
)
1
(
)
6
(
)
4
(
)
2
(
)
0
(
)
4
(
ˆ
s
s
s
s
s
s
s
s
s
+
+
+
−
+
+
+
=
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
↓
←
↑
→
↓
←
↑
→
↓
←
↑
→
↑
←
↓
→
←
→
←
→
←
→
←
→
↓
←
↑
→
↑
←
↓
→
↑
←
↓
→
↑
←
↓
→
→
→
→
→
→
→
→
→
=
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
)
7
(
)
6
(
)
5
(
)
4
(
)
3
(
)
2
(
)
1
(
)
0
(
)
7
(
ˆ
)
6
(
ˆ
)
5
(
ˆ
)
4
(
ˆ
)
3
(
ˆ
)
2
(
ˆ
)
1
(
ˆ
)
0
(
ˆ
s
s
s
s
s
s
s
s
s
s
s
s
s
s
s
s
Obliczenia DFT można zapisać w postaci macierzowej
4
Nakład obliczeniowy dla dyskretnej
transformacji Fouriera
∑
−
=
=
1
0
)
(
)
(
ˆ
N
n
kn
N
w
n
s
k
s
N
j
N
e
w
π
2
−
=
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.
2
2N
Dyskretne widmo jest obliczane przy pomocy wzoru
gdzie
5
Cooley i Tuckey 1965 rok
∑
∑
∑
−
=
−
=
+
−
=
+
+
=
=
1
2
0
1
2
0
)
1
2
(
2
1
0
)
1
2
(
)
2
(
)
(
)
(
ˆ
N
n
N
n
k
n
N
nk
N
N
n
kn
N
w
n
s
w
n
s
w
n
s
k
s
N
j
N
e
w
π
2
−
=
N
j
N
e
w
π
4
2
/
−
=
∑
∑
−
=
−
=
+
+
=
1
2
0
1
2
0
2
/
2
/
)
1
2
(
)
2
(
N
n
N
n
kn
N
k
N
kn
N
w
n
s
w
w
n
s
)
(
ˆ
)
(
ˆ
)
(
ˆ
k
s
w
k
s
k
s
n
k
N
p
+
=
{
}
1
2
/
,...,
1
,
0
−
∈
N
k
dla
A co z wartościami dla
{
}
?
1
,
,
2
/
−
∈
N
N
k
K
Dla poprawy efektywności, przeprowadźmy obliczenia osobno dla próbek
o numerach parzystych i osobno o numerach nieparzystych. Otrzymamy
gdzie
natomiast
6
Okresowość widm dyskretnych
(
)
2
2
2
2
2
N
k
N
N
k
N
j
j
k
N
j
k
N
j
k
N
w
e
e
e
e
w
−
−
−
−
−
−
=
−
=
−
=
=
π
π
π
π
)
2
/
(
ˆ
)
(
ˆ
)
2
/
(
ˆ
)
(
ˆ
N
k
s
k
s
N
k
s
k
s
n
n
p
p
−
=
−
=
( )
k
w
Re
( )
k
w
Im
Jeśli na przykład k = 4 i N = 8, to
)
(
ˆ
)
(
ˆ
)
(
ˆ
k
s
w
k
s
k
s
n
k
N
p
+
=
Widma zarówno dla próbek o numerach parzystych jak i nieparzystych
są funkcjami okresowymi, tzn.
Dodatkowo zauważmy, że
1
−
=
k
N
w
1
2
=
−N
k
N
w
Otrzymaliśmy
7
Wzór wynikający z okresowości
funkcji dyskretnych
⎪⎩
⎪
⎨
⎧
−
=
−
−
−
−
=
+
=
−
.
1
,...,
2
/
dla
)
2
/
(
ˆ
)
2
/
(
ˆ
1
2
/
,...,
1
,
0
dla
)
(
ˆ
)
(
ˆ
)
(
ˆ
2
/
N
N
k
N
k
s
w
N
k
s
N
k
k
s
w
k
s
k
s
n
N
k
N
p
n
k
N
p
)
(
ˆ
)
(
ˆ
)
(
ˆ
k
s
w
k
s
k
s
n
k
N
p
+
=
Z warunków
)
2
/
(
ˆ
)
(
ˆ
)
2
/
(
ˆ
)
(
ˆ
N
k
s
k
s
N
k
s
k
s
n
n
p
p
−
=
−
=
2
N
k
N
k
N
w
w
−
−
=
oraz
wynika, że
jest równoważne
8
Efektywność algorytmu
N
N
2
2
+
bo zarówno
jak i
dla k = 0, 1, ..., N/2-1 wymaga 2(N/2)
2
mnożeń i dodatkowo trzeba wykonać 4(N/2) mnożeń dla
(mnożenie liczb zespolonych!).
)
(
ˆ k
s
p
)
(
ˆ k
s
n
)
(
ˆ k
s
w
n
k
N
Ilość mnożeń w otrzymanym wzorze
⎪⎩
⎪
⎨
⎧
−
=
−
−
−
−
=
+
=
−
.
1
,...,
2
/
dla
)
2
/
(
ˆ
)
2
/
(
ˆ
1
2
/
,...,
1
,
0
dla
)
(
ˆ
)
(
ˆ
)
(
ˆ
2
/
N
N
k
N
k
s
w
N
k
s
N
k
k
s
w
k
s
k
s
n
N
k
N
p
n
k
N
p
N
N
N
2
2
2
2
+
>
Przedstawiony algorytm jest bardziej efektywny jeśli spełniona jest
nierówność
wynosi
czyli musi być N > 2, a przecież tak jest zawsze!
9
Szybka transformacja Fouriera
)
1
(
)
0
(
)
1
(
ˆ
)
1
(
)
0
(
)
0
(
ˆ
s
s
s
s
s
s
−
=
+
=
)
0
(
s
)
1
(
s
)
0
(
ˆs
)
1
(
ˆs
−
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
Stosując M - krotnie podział na próbki o numerach parzystych i nieparzystych, na
końcu otrzymujemy dla N = 2
.
2
M
N
=
ang. Fast Fourier Transform - FFT
10
Operacje motylkowe
s(0)
s(1)
s(2)
s(3)
s(4)
s(5)
s(6)
s(7)
ŝ
(0)
ŝ
(4)
ŝ
(2)
ŝ
(6)
ŝ
(1)
ŝ
(5)
ŝ
(3)
ŝ
(7)
grupa 0
grupa 0
grupa 0
grupa 1
grupa 2
przebieg 1
przebieg 2
przebieg 3
0
N
W
0
N
W
0
N
W
0
N
W
0
N
W
0
N
W
0
N
W
2
N
W
2
N
W
1
N
W
2
N
W
3
N
W
1
grupa 1
grupa 3
−
1
−
1
−
1
−
1
−
1
−
1
−
1
−
1
−
1
−
1
−
1
−
11
Efektywność operacji motylkowych
Poziomów jest
a na każdym z nich N/2 operacji motylkowych.
Czyli ostatecznie mnożeń (na ogół liczb zespolonych) jest
.
N
M
2
lg
=
N
N
N
M
2
log
2
2
4
=
2
N
~
DFT
N
N
FFT
2
log
~
.
2
M
N
=
Ilość próbek
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.
12
Porównanie efektywności DFT i FFT
Ilość mnożeń DFT i FFT dla N próbek
0
20
40
60
80
100
0.2
0.6
1
1.4
1.8
x 10
2
2N
N
N
2
lg
2
N
4
8
16
32
64
128
32
128
512
2048 8192 32768
16
48
128
320
768
1792
2
2N
N
N
2
log
2
Document Outline
- Szybka transformacja Fouriera
- Cechy charakterystyczne procedury obliczeniowej DFT
- Przykład dublowania obliczeń
- Nakład obliczeniowy dla dyskretnej transformacji Fouriera
- Cooley i Tuckey 1965 rok
- Okresowość widm dyskretnych
- Wzór wynikający z okresowości funkcji dyskretnych
- Efektywność algorytmu
- Szybka transformacja Fouriera
- Operacje motylkowe
- Efektywność operacji motylkowych
- Porównanie efektywności DFT i FFT
Wyszukiwarka
Podobne podstrony:
PORÓWNYWANIE TECHNOLOGII
Metodyka harcerska i starszoharcerska porównanie
Porównanie dwóch regionalnych strategii innowacji
19 Teorie porównanie
KOLOKWIUM 2 zadanie wg Adamczewskiego na porownawczą 97
1F CWICZENIE zadanie wg Adamczewskiego na porownawczą 97id 18959 ppt
Porównanie USB FireWire
Dowody za obiektywno¶ci± ewolucji z zakresu morfologii porównawczej 1 cz
Co daje nauce prawoznawstwo porownawcze
informacje porownanie skal twardosci
zwierzęta porównania pomoc
Porownanie 3820 a 561
pedagogika porównawcza zwiastun
sk wyklad10, PSC (Porownawcze Studia Cywilizacji - kulturoznawstwo), Socjologia kultury
więcej podobnych podstron