Szybka transformacja Fouriera

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

(…)

…) + 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
N −1
kn
ˆ
s ( k ) = ∑ s ( n) wN
n =0
gdzie
wN = e
−j
2π
N
2N 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.
4
Cooley i Tuckey 1965 rok
Dla poprawy efektywności…
…
1
WN
−1
grupa 0
−1
grupa 0
grupa 2
−1
−1
−1
3
WN
grupa 1
−1
grupa 3
ŝ(0)
ŝ(4)
ŝ(2)
ŝ(6)
ŝ(1)
ŝ(5)
ŝ(3)
ŝ(7)
−1
10
Efektywność operacji motylkowych
Ilość próbek N = 2 M .
Poziomów jest M = lg 2 N a na każdym z nich N/2 operacji motylkowych.
Czyli ostatecznie mnożeń (na ogół liczb zespolonych) jest
.
4M
N
= 2 N log 2 N
2
Reasumując, ilość mnożeń w dyskretnej transformacji Fouriera jest proporcjonalna…
… 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
ˆ
⎡ s (0) ⎤ ⎡→ → → → → → → →⎤⎡ s (0) ⎤
⎥⎢ s (1) ⎥
⎢ s (1) ⎥ ⎢→
ˆ
↓
←
↑
⎥
⎥⎢
⎥ ⎢
⎢
⎢ s (2)⎥ ⎢→ ↓ ← ↑ → ↓ ← ↑ ⎥⎢ s (2)⎥
ˆ…
... zobacz całą notatkę