9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 1/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH
1
Przekształcenie Fouriera sygnału dyskretnego
• podstawą analizy częstotliwościowej dyskretnych sygnałów zdeterminowanych jest
szereg Fouriera oraz proste i odwrotne przekształcenie Fouriera; ze względu na
dyskretny charakter dziedziny czasu pojęcia te są definiowane nieco inaczej niż dla
ciągłej dziedziny czasu
• proste przekształcenie Fouriera sygnału dyskretnego
niech sygnał dyskretny
( ) ( )
s
s
nT
x
t
x
=
, będący efektem próbkowania sygnału
analogowego
( )
t
x
z okresem
s
T
, jest sygnałem energii, tzn., że
( )
∞
<
=
∑
∞
−∞
=
n
s
x
nT
x
E
2
funkcja widmowa sygnału
( )
t
x
s
(transformata Fouriera w zwykłym sensie)
( )
( )
∫
∞
∞
−
ω
−
=
ω
dt
e
t
x
X
t
j
s
s
1
opracowano na podstawie [1-3], wersja z dnia 02.10.2014
materiał nie jest pełnym i ścisłym pod względem formalnym opracowaniem poszczególnych tematów, stanowi
jedynie szkielet, wokół którego budowany jest wykład
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 2/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
z właściwości próbkowania dystrybucji sza wynika
( ) ( )
( ) (
)
∑
∞
−∞
=
−
δ
=
=
n
s
s
s
s
s
nT
t
nT
x
T
t
T
t
x
t
x
III
1
zatem
( )
( ) (
)
( ) (
)
∑
∫
∫ ∑
∞
−∞
=
∞
∞
−
ω
−
∞
∞
−
ω
−
∞
−∞
=
−
δ
=
=
−
δ
=
ω
n
t
j
s
s
t
j
n
s
s
s
dt
e
nT
t
nT
x
dt
e
nT
t
nT
x
X
korzystając z właściwości filtracji dystrybucji delta
( ) (
)
( )
0
0
t
x
dt
t
t
t
x
=
−
δ
∫
∞
∞
−
możemy napisać
( )
( )
( )
s
s
T
j
n
nT
j
s
s
e
X
e
nT
x
X
ω
∞
−∞
=
ω
−
=
=
ω
∑
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 3/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
wyrażenie
( )
( )
{
}
( )
∑
∞
−∞
=
ω
−
ω
=
=
n
nT
j
s
s
T
j
s
s
e
nT
x
nT
x
e
X
F
stanowi proste przekształcenie Fouriera sygnału dyskretnego
( )
s
nT
x
(widmo sygnału
dyskretnego), sygnałowi dyskretnemu
( )
s
nT
x
zostaje przyporządkowana zespolona
funkcja
( )
s
T
j
e
X
ω
zmiennej rzeczywistej
ω
widmo amplitudowe i widmo fazowe sygnału dyskretnego
( ) ( )
s
s
T
j
T
j
e
A
e
X
ω
ω
=
- widmo amplitudowe sygnału
( )
s
nT
x
( ) ( )
s
s
T
j
T
j
e
e
X
ω
ω
ϕ
=
arg
- widmo fazowe sygnału
( )
s
nT
x
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 4/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
• ponieważ
(
)
(
)
( )
(
)
( )
(
)
( )
( )
( )
s
s
s
s
s
s
s
s
s
T
j
n
nT
j
s
n
kn
j
nT
j
s
n
nT
T
k
j
s
n
nT
k
j
s
T
k
j
e
X
e
nT
x
e
e
nT
x
e
nT
x
e
nT
x
e
X
ω
∞
−∞
=
ω
−
∞
−∞
=
π
−
ω
−
∞
−∞
=
π
+
ω
−
∞
−∞
=
ω
+
ω
−
ω
+
ω
=
=
=
=
=
=
∑
∑
∑
∑
2
2
zatem funkcja
( )
( )
ω
≡
ω
X
e
X
s
T
j
jest funkcją okresową zmiennej
ω
z okresem
s
ω
• odwrotne przekształcenie Fouriera sygnałów dyskretnych - poszukiwane wartości
sygnału w dyskretnej dziedzinie czasu stanowią współczynniki rozwinięcia widma
okresowego
( )
s
T
j
e
X
ω
w wykładniczy szereg
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 5/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
• para transformat Fouriera dla sygnału dyskretnego przyjmie zatem postać
( )
( )
∑
∞
−∞
=
ω
−
ω
=
n
nT
j
s
T
j
s
s
e
nT
x
e
X
( )
( )
∫
ω
ω
−
ω
−
ω
ω
ω
=
2
2
1
s
s
s
s
d
e
e
X
nT
x
jnT
T
j
s
s
• normując czas do okresu próbkowania (
n
T
nT
s
s
=
/
) oraz pulsację do częstotliwości
próbkowania
Ω
=
ω
=
ω
s
s
T
f
/
, widmo sygnału dyskretnego w unormowanej
dziedzinie czasu i częstotliwości przyjmie postać
( )
( )
∑
∞
−∞
=
Ω
−
Ω
=
n
jn
j
e
n
x
e
X
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 6/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
• ponieważ
(
)
(
)
( )
(
)
( )
( )
( )
Ω
∞
−∞
=
Ω
−
∞
−∞
=
π
−
Ω
−
∞
−∞
=
π
+
Ω
−
π
+
Ω
=
=
=
=
=
∑
∑
∑
j
n
n
j
s
n
kn
j
n
j
s
n
n
k
j
s
k
j
e
X
e
nT
x
e
e
nT
x
e
nT
x
e
X
2
2
2
zatem funkcja
( )
Ω
j
e
X
oraz widmo amplitudowe
( )
Ω
j
e
A
i widmo fazowe
( )
Ω
ϕ
j
e
są
funkcjami okresowymi zmiennej
Ω
z okresem
π
2
, dlatego ich wykresy sporządzamy
w przedziale
π
π,
-
lub
π
2
,
0
dla dyskretnych sygnałów rzeczywistych ich widma amplitudowe są funkcją parzystą,
widma fazowe funkcją nieparzystą, zatem ich wykresy wystarczy sporządzić
w zakresie
π
,
0
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 7/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
• po unormowaniu para transformat Fouriera dla sygnału dyskretnego przyjmie zatem
postać
( )
( )
∑
∞
−∞
=
Ω
−
Ω
=
n
n
j
j
e
n
x
e
X
( )
( )
∫
π
π
−
Ω
−
Ω
Ω
π
=
d
e
e
X
n
x
n
j
j
2
1
• widmo nieokresowego sygnału analogowego jest określone w nieograniczonym
przedziale częstotliwości
(
)
∞
∞
− ,
widmo nieokresowego sygnału dyskretnego jest
okresowe (określone jednoznacznie w przedziale o długości
s
ω
lub
π
2
)
• widmo sygnału analogowego jest definiowane przez operację całkowania, widmo
sygnału dyskretnego definiowane przez operację sumowania
• sygnały dyskretne o ograniczonej mocy nie mają widm w sensie powyższych definicji,
dla tej klasy sygnałów wprowadza się pojęcia widma w sensie granicznym
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 8/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
przykład
widmo amplitudowe dyskretnego impulsu prostokątnego
dla porównania widmo amplitudowe ciągłego impulsu prostokątnego
1
0
ω
|X(ω)|
2π
−2π
4π
6π
8π
−4π
−6π
−8π
1
0
1
t
x(t)
5
4π
5
2π
5
−2π
5
−4π
0
5
Ω
A( )
jΩ
e
π
2π
−π
−2π
5
2π
5
4π
4
3
2
1
0
1
n
x(n)
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 9/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
Wybrane właściwości przekształcenia Fouriera sygnałów dyskretnych
• dane są pary transformat
( )
( )
Ω
↔
j
e
X
n
x
oraz
( )
( )
Ω
↔
j
e
Y
n
y
właściwości
twierdzenie o liniowości
( )
( )
( ) ( )
Ω
Ω
+
↔
+
j
j
e
bY
e
aX
n
by
n
ax
twierdzenie o przesunięciu w dziedzinie czasu
(
)
( )
0
0
n
j
j
e
e
X
n
n
x
Ω
−
Ω
↔
−
twierdzenie o przesunięciu w dziedzinie częstotliwości (o modulacji)
( )
(
)
(
)
0
0
Ω
−
Ω
Ω
−
↔
j
jn
e
X
e
n
x
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 10/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
twierdzenie o odwracaniu w dziedzinie czasu
( )
( )
Ω
−
↔
−
j
e
X
n
x
twierdzenie o splocie w dziedzinie czasu
( ) ( )
( ) ( )
Ω
Ω
↔
∗
j
j
e
Y
e
X
n
y
n
x
twierdzenie o splocie w dziedzinie częstotliwości
( ) ( )
( ) ( )
Ω
Ω
∗
π
↔
j
j
e
Y
e
X
n
y
n
x
2
1
twierdzenie o energii (Parsevala)
( )
( )
∫
∑
π
π
−
Ω
∞
−∞
=
Ω
π
=
d
e
X
n
x
j
n
2
2
2
1
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 11/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
Dyskretne przekształcenie Fouriera
• ze względu na złożoność spotykanych w praktyce sygnałów współczesna analiza
widmowa sygnałów dyskretnych dokonywana jest metodami numerycznymi
• w praktyce sygnał analogowy
( )
t
x
podlega obserwacji w skończonym przedziale
czasu
T
,
0
, w celu poddania go analizie widmowej zostaje spróbkowany ze stałym
okresem próbkowania
s
T
, co daje w skończonym przedziale obserwacji skończoną
liczbę próbek
s
T
T
N =
; próbki w unormowanej dziedzinie czasu przyjmują numery
od
0
do
1
−
N
• niech sygnał dyskretny
( )
n
x
o skończonym unormowanym czasie trwania
N
określony jest ciągiem próbek
( )
{
}
1
...,
,
1
,
0
,
−
=
N
n
n
x
; posiada on widmo
(przekształcenie Fouriera sygnału dyskretnego) określone w unormowanej dziedzinie
pulsacji wyrażeniem
( )
( )
∑
−
=
Ω
−
Ω
=
1
0
N
n
n
j
j
e
n
x
e
X
widmo to jest funkcją okresową zmiennej
Ω
o okresie
π
2
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 12/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
• numeryczne metody wyznaczania tego widma polegają na wyznaczeniu wartości
( )
k
j
e
X
Ω
w skończonej liczbie równoodległych punktów
π
π
∈
Ω
,
-
k
• liczbę punktów dobiera się w taki sposób aby na podstawie zbioru próbek widma
( )
{
}
k
j
e
X
Ω
można było jednoznacznie odtworzyć ciąg próbek sygnału w dziedzinie
czasu
( )
{
}
1
...,
,
1
,
0
,
−
=
N
n
n
x
; zapewnia to możliwość określenia wzajemnie
jednoznacznego związku pomiędzy sygnałem a dyskretną reprezentacją jego widma;
najmniejsza liczność zbioru
( )
{
}
k
j
e
X
Ω
wynosi zatem
N
, gdyż wtedy otrzymujemy
N
równań z
N
niewiadomymi, zatem
1
...,
,
1
,
0
,
2
−
=
π
=
Ω
N
k
N
k
k
• dyskretna transformata Fouriera (
DTF
, ang.
DFT
- Discrete Fourier Transform),
nazywana również widmem dyskretnym sygnału
( )
n
x
, określona jest wyrażeniem
( )
( )
∑
−
=
π
−
π
Ω
=
=
1
0
2
2
N
n
kn
N
j
k
N
j
j
e
n
x
e
X
e
x
k
sygnałowi dyskretnemu
( )
n
x
przyporządkowana zostaje zespolona funkcja
(
)
N
k
j
e
X
π
2
zmiennej
k
w skrócie oznaczamy ją
( )
( )
[
]
n
x
F
k
X
D
=
i nazywamy
N
-punktową
DTF
(o wymiarze
N
)
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 13/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
• funkcje
( )
( )
k
X
k
A
=
- nazywamy dyskretnym widmem amplitudowym sygnału
( )
n
x
( )
( )
k
X
k
arg
=
ϕ
- nazywamy dyskretnym widmem fazowym sygnału
( )
n
x
• ponieważ
(
)
( )
(
)
( )
( )
( )
k
X
e
n
x
e
e
n
x
e
n
x
N
l
k
X
N
n
kn
N
j
N
n
n
l
j
kn
N
j
N
n
n
N
l
k
N
j
=
=
=
=
=
+
∑
∑
∑
−
=
π
−
−
=
π
−
π
−
−
=
+
π
−
1
0
2
1
0
2
2
1
0
2
zatem funkcja
( )
k
X
oraz dyskretne widmo amplitudowe
( )
k
A
i dyskretne widmo
fazowe
( )
k
ϕ
są funkcjami okresowymi zmiennej
k
z okresem
N
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 14/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
• dla wygody wprowadza się oznaczenie
N
j
N
e
W
π
−
=
2
• wykorzystując wielkość
N
W
N
-punktowa
DTF
przyjmie postać
( )
( )
∑
−
=
=
1
0
N
n
kn
N
W
n
x
k
X
• odwrotna dyskretna transformata Fouriera pozwala wyznaczyć ciąg próbek sygnału
( )
{
}
1
...,
,
1
,
0
,
−
=
N
n
n
x
w oparciu o
N
-punktową
DTF
( )
k
X
• odwrotna dyskretna transformata Fouriera (
ODTF
, ang.
IDFT
- Inverse
Discrete Fourier Transform) określona jest wyrażeniem
( )
( )
( )
∑
∑
−
=
−
−
=
π
=
=
1
0
1
0
2
1
1
N
k
nk
N
N
k
N
nk
j
W
k
X
N
e
k
X
N
n
x
widmu dyskretnemu
( )
1
...,
,
0
,
−
=
N
k
k
X
przyporządkowany zostaje sygnał
dyskretny
( )
1
...,
,
0
,
−
=
N
n
n
x
,
ODTF
jest również okresowa o okresie
N
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 15/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
• para dyskretnych transformat Fouriera
( )
( )
1
...,
,
1
,
0
,
1
0
−
=
=
∑
−
=
N
k
W
n
x
k
X
N
n
kn
N
( )
( )
1
...,
,
1
,
0
,
1
1
0
−
=
=
∑
−
=
−
N
n
W
k
X
N
n
x
N
k
nk
N
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 16/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
przykład
dyskretne widmo amplitudowe dyskretnego impulsu prostokątnego (
1
,
5
=
= U
N
)
dyskretne widmo amplitudowe dyskretnego impulsu prostokątnego jw. uzupełnionego
pięcioma próbkami zerowymi
0
5
k
A(k)
1 2 3 4 5 6 7 8 9
4
3
2
1
0
1
n
x(n)
0
5
k
A(k)
1
2
3
4
4
3
2
1
0
1
n
x(n)
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 17/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
Wybrane właściwości dyskretnego przekształcenia Fouriera
• dane są pary
N
punktowych dyskretnych transformat Fouriera
( )
( )
k
X
n
x
↔
oraz
( )
( )
k
Y
n
y
↔
właściwości
twierdzenie o okresowości
(
) ( )
n
n
x
N
n
x
dowolnego
dla
=
+
(
)
( )
k
k
X
N
k
X
dowolnego
dla
=
+
twierdzenie o liniowości
( )
( )
( )
( )
k
bY
k
aX
n
by
n
ax
+
↔
+
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 18/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
twierdzenie o przesunięciu (kołowym) w dziedzinie czasu
(
)
( )
0
2
0
mod
kn
N
j
N
e
k
X
n
n
x
π
−
↔
−
twierdzenie o przesunięciu (kołowym) w dziedzinie częstotliwości
( )
(
)
0
mod
2
0
k
k
X
e
n
x
N
n
k
N
j
−
↔
π
twierdzenie o operacji sprzęgania w dziedzinie czasu
( )
( )
k
X
n
x
N
−
↔
*
mod
*
twierdzenie o operacji sprzęgania w dziedzinie częstotliwości
( )
( )
k
X
n
x
N
*
*
mod
↔
−
twierdzenie o splocie (kołowym) w dziedzinie czasu
( )
( )
( ) ( )
k
X
k
X
n
y
n
x
↔
⊗
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 19/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
twierdzenie o splocie (kołowym) w dziedzinie czasu
( ) ( )
( )
( )
k
X
k
X
N
n
y
n
x
⊗
↔
1
twierdzenie Parsevala o energii
( ) ( )
( ) ( )
∑
∑
−
=
−
=
=
1
0
*
1
0
*
1
N
k
N
n
k
Y
k
X
N
n
y
n
x
wartość w punkcie
0
=
k
próbka
( )
0
X
widma jest równa sumie próbek sygnału w przedziale
1
...,
,
1
,
0
−
=
N
n
, dla sygnału
( )
n
x
rzeczywistego,
( )
0
X
jest rzeczywiste
( )
( )
∑
−
=
=
1
0
0
N
n
n
x
X
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 20/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
Wyznaczanie splotu liniowego (operacja filtracji) przy pomocy
DTF
• wykorzystując właściwość
DTF
( )
( )
( ) ( )
k
H
k
X
n
h
n
x
↔
⊗
możemy napisać
( )
( )
( )
( )
[
]
( )
[
]
{
}
,
n
h
DTF
n
x
DTF
ODTF
n
h
n
x
n
y
=
⊗
=
pamiętając, że powyższa właściwość dotyczy splotu kołowego, dla ciągów
( )
n
x
i
( )
n
h
o długościach odpowiednio
1
N
i
2
N
dla wyznaczenia splotu liniowego rozmiar
transformaty powinien być nie mniejszy niż
1
2
1
−
+ N
N
• wykorzystując efektywne algorytmy
STF
dla przykładowych
1024
2
1
=
= N
N
uzyskujemy około 30 krotne zmniejszenie liczby operacji w porównaniu z bezpośrednim
wyznaczaniem sumy splotowej
• graficzna postać algorytmu
y(n)
h (n)
x
(n)
STF
STF
OSTF
H (k)
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 21/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
Szybkie przekształcenie Fouriera
•
dyskretna transformata Fouriera odgrywa ważną rolę w zagadnieniach analizy, projektowania
i realizacji cyfrowych algorytmów i układów przetwarzania sygnałów; wadą tego przekształcenia
jest jednak duża liczba operacji matematycznych niezbędnych do jej obliczenia
do wyznaczenia pojedynczej próbki widma na podstawie
N
-punktowej
DTF
określonej
wyrażeniem
( )
( )
1
...,
,
1
,
0
,
1
0
−
=
=
∑
−
=
N
k
W
n
x
k
X
N
n
kn
N
niezbędne jest wykonanie
N
operacji mnożenia oraz
1
−
N
operacji dodawania,
zatem do wyznaczenia wszystkich
N
próbek widma należy wykonać łącznie
2
N
operacji
mnożenia oraz
(
)
1
−
N
N
operacji dodawania
ponieważ w ogólnym przypadku mamy do czynienia z sygnałem zespolonym, dla którego
operacja mnożenia wymaga 4 operacji mnożenia rzeczywistego oraz dwóch operacji
dodawania, a operacja dodawania dwóch operacji dodawania rzeczywistego, łączna ilość
rzeczywistych operacji arytmetycznych wynosi
(
)
N
N
2
8
2
−
dla dużych wartości
N
łączna liczba operacji arytmetycznych, a tym samym czas obliczeń,
może osiągnąć znaczne wartości
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 22/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
Szybkie przekształcenie Fouriera (cd)
• w latach sześćdziesiątych XX wieku zaproponowano algorytmy „szybkiego”
wyznaczania
DTF
, określanych nazwą
STF
- Szybka Transformata Fouriera
(ang.
FFT
- Fast Fourier Transform)
ich istotą było wyznaczenie
DTF
z pełną dokładnością (pomijając skończoną
precyzję operacji arytmetycznych technicznych środków obliczeniowych), przy
znacznie mniejszym zapotrzebowaniu na moc obliczeniową, co stanowiło milowy
krok w rozwoju teorii i techniki cyfrowego przetwarzania sygnałów
• istota szybkich algorytmów
STF
sprowadza się do wykorzystania dwóch właściwości
czynnika rotującego
N
W
1. symetria
k
N
N
k
N
W
W
−
=
+
2
2. okresowość
k
N
N
k
N
W
W
=
+
• aby osiągnąć istotny wzrost efektywności obliczeń rozmiar transformaty
N
powinien
być iloczynem dwóch lub więcej liczb całkowitych, jednak największą efektywność
uzyskuje się dla przypadku gdy
N
jest całkowitą potęgą liczby 2
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 23/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
Szybkie przekształcenie Fouriera (cd)
• dwie podstawowe klasy algorytmów
STF
to
1. algorytmy z podziałem czasowym (ang. decimation-in-time), w których podczas
wykonywania obliczeń ciąg
( )
{
}
n
x
jest stopniowo dzielony na coraz krótsze podciągi
2. algorytmy z podziałem częstotliwościowym (ang. decimation-in-frequency), w których
podczas wykonywania obliczeń ciąg
( )
{
}
k
X
jest stopniowo dzielony na coraz
krótsze podciągi
• najprostszą (i najbardziej rozpowszechnioną) wersją szybkiego przekształcenia
Fouriera są tzw. algorytmy o podstawie 2 (ang. radix-2) przystosowane do
przetwarzania ciągów próbek o długościach będących naturalną potęgą liczby 2;
algorytmy te są algorytmami najbardziej efektywnymi, gdyż liczba 2 jest bowiem
najmniejszą liczbą pierwszą, a zatem liczba
ν
= 2
N
,
ν
- liczba naturalna, jest
iloczynem największej liczby czynników
• podstawową zasadą, na której opierają się algorytmy
STF
, jest zastępowanie
obliczeń
DTF
ciągu o długości
N
obliczaniem
DTF
odpowiednio krótszych ciągów
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 24/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
Szybkie przekształcenie Fouriera (cd)
• istota algorytmu
STF
zostanie przedstawiona na przykładzie algorytmu z podziałem
czasowym
- niech sygnał
( )
t
x
po operacji próbkowania zostanie przedstawiony ciągiem
N
próbek
( )
{
}
1
...,
,
1
,
0
,
−
=
N
n
n
x
, przy czym
ν
= 2
N
,
ν
- liczba naturalna
- oznaczmy połowę liczby tych próbek
2
N
o numerach parzystych przez
( )
r
y
( )
{
}
( ) ( ) ( )
(
)
{
}
( )
{
}
r
x
N
x
x
x
x
r
y
2
2
...,
,
4
,
2
,
0
=
−
=
,
1
2
...,
,
2
,
1
,
0
−
=
N
r
- oznaczmy drugą połowę liczby próbek
2
N
o numerach nieparzystych przez
( )
r
z
( )
{ }
( ) ( ) ( )
(
)
{
}
(
)
{
}
1
2
1
...,
,
5
,
3
,
1
+
=
−
=
r
x
N
x
x
x
x
r
z
1
2
...,
,
2
,
1
,
0
−
=
N
r
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 25/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
Szybkie przekształcenie Fouriera (cd)
- można wykazać, że dyskretna transformata Fouriera ciągu
( )
n
x
jest kombinacją
dyskretnych transformat Fouriera ciągów
( )
r
y
oraz
( )
r
z
( )
( )
( )
k
Z
W
k
Y
k
X
k
N
+
=
,
1
2
...,
,
1
,
0
−
=
N
k
(
)
( )
( )
k
Z
W
k
Y
N
k
X
k
N
−
=
+
2
,
1
2
...,
,
1
,
0
−
=
N
k
gdzie:
( )
( )
1
2
...,
,
1
,
0
,
1
2
0
2
−
=
=
∑
−
=
N
k
W
r
y
k
Y
N
r
kr
N
( )
( )
1
2
...,
,
1
,
0
,
1
2
0
2
−
=
=
∑
−
=
N
k
W
r
z
k
Z
N
r
kr
N
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 26/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
Szybkie przekształcenie Fouriera (cd)
z powyższych wyrażeń wynika, że dla obliczenia ciągu
2
N
próbek transformaty
( )
k
Y
niezbędne jest wykonanie
(
)
2
2
N
operacji mnożenia zespolonego oraz
(
)
1
2
2
−
N
N
operacji zespolonego dodawania; tyle samo operacji wymaga
obliczenie
2
N
próbek transformaty
( )
k
Z
; oprócz tego wymagane jest wykonanie
dodatkowych
2
N
operacji mnożenia zespolonego
( )
k
Z
W
k
N
oraz
2
N
operacji
zespolonego dodawania i
2
N
operacji zespolonego odejmowania;
ostatecznie do wyznaczenia
N
próbek transformaty
( )
k
X
niezbędne jest
wykonanie
(
)
2
2
2
2
2
2
2
N
N
N
N
+
=
+
operacji mnożenia zespolonego oraz
(
)
[
]
(
)
2
2
2
1
2
2
2
2
N
N
N
N
=
+
−
operacji dodawania zespolonego; zatem
tylko pierwszy etap podziału ciągu danych wejściowych na dwa podciągi
( )
n
y
i
( )
n
z
daje około dwukrotną oszczędność liczby operacji mnożenia zespolonego
i dwukrotną oszczędność liczby operacji dodawania zespolonego (dla dużych
N
)
w porównaniu z algorytmem
DTF
(
patrz slajd 21
)
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 27/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
Szybkie przekształcenie Fouriera (cd)
- powyższy schemat obliczeń
DTF
ciągu o długości
8
=
N
przedstawia graf
- jeśli
2
N
jest parzyste, co ma miejsce jeśli
N
jest potęgą liczby 2, to wyznaczanie
każdej
2
N
-punktowej
DTF
może być, poprzez kolejny podział ciągów
( )
n
y
oraz
( )
n
z
na podciągi o próbkach parzystych i nieparzystych, w sposób przedstawiony
wyżej zastąpione wyznaczeniem dwóch transformat
4
N
-punktowych, prowadząc
do kolejnych oszczędności obliczeniowych
-1
-1
-1
-1
x(0)
N/2 - punktowa
DTF
x(1)
x(2)
x(3)
x(4)
x(5)
x(6)
x(7)
y(1)
N/2 - punktowa
DTF
Y(0)
Y(1)
Y(2)
Y(3)
Z(0)
Z(1)
Z(2)
Z(3)
y(0)
y(2)
y(3)
z(0)
z(1)
z(2)
z(3)
W
N
3
W
N
2
W
N
1
W
N
0
X(0)
X(1)
X(2)
X(3)
X(4)
X(5)
X(6)
X(7)
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 28/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
Szybkie przekształcenie Fouriera (cd)
operację podziału na podciągi prowadzi się aż do uzyskania ciągów dwuelementowych, co
prowadzi do potrzeby wyznaczania
DTF
o długości 2; dla powyższego przykładu, dla
którego
8
=
N
, 2-punktowe
DTF
dla próbek
( )
0
x
oraz
( )
4
x
przedstawia poniższy graf
wykonywane na tym etapie operacje arytmetyczne sprowadzają się do prostego dodawania i
odejmowania wyrazów ciągu wejściowego
2-punktowe
DTF
nazywa się obliczeniem motylkowym
- zatem drogą kolejnego podziału ciągu próbek w dziedzinie czasu, wyznaczanie
N
-punktowej
DTF
dla
ν
= 2
N
zostało sprowadzone wyłącznie do obliczania transformat
dwupunktowych i mnożenia ciągów wejściowych tych transformat przez czynniki wykładnicze
r
N
W
, gdzie
r
zależy od etapu obliczeń; powstaje w ten sposób regularna struktura obliczeń
składająca się z
N
2
log
=
ν
etapów obliczeń o podobnej budowie, zawierających na
każdym etapie
2
N
obliczeń motylkowych
x(0)
W
8
0
=1
x(4)
-1
x(0) + x(4)
x(0) - x(4)
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 29/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
Szybkie przekształcenie Fouriera (cd)
• ostateczna liczba operacji mnożenia i dodawania zespolonego dla
N
punktowej
STF
wynosi odpowiednio
N
N
O
M
STF
2
log
2
=
N
N
O
A
STF
2
log
=
co daje łączną liczbę operacji zespolonych
N
N
O
STF
2
log
2
3
=
• dla porównania liczba operacji mnożenia i dodawania zespolonego oraz łącznie dla
N
punktowej
DTF
wynosi odpowiednio
2
N
O
M
DTF
=
oraz
(
)
)
1
−
=
N
N
O
A
DTF
N
N
O
DTF
−
=
2
2
przykład
dla
1024
=
N
liczba operacji arytmetycznych -
DTF
:
128
096
2
1024
1024
2
2
=
−
⋅
=
DTF
O
liczba operacji arytmetycznych -
STF
:
360
15
1024
log
1024
5
.
1
2
=
⋅
=
STF
O
5
,
136
360
15
128
096
2
=
=
S
D
O
O
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 30/39
ANALIZA WIDMOWA SYGNAŁÓW DYSKRETNYCH (cd)
Szybkie przekształcenie Fouriera (cd)
- dla przypadku
8
=
N
algorytm obliczeń przedstawia następujący graf
-1
-1
-1
x(1)
x(0)
x(2)
x(3)
x(4)
x(5)
x(6)
x(7)
x(4)
x(0)
x(2)
x(6)
x(1)
x(5)
x(3)
x(7)
x(2)
x(0)
x(4)
x(6)
x(1)
x(3)
x(5)
x(7)
W
8
0
-1
W
8
0
-1
W
8
0
-1
W
8
0
-1
-1
W
8
2
W
8
0
-1
-1
W
8
2
W
8
0
etap 1
etap 2
-1
-1
W
8
3
W
8
2
etap 3
W
8
1
W
8
0
X(0)
X(1)
X(2)
X(3)
X(4)
X(5)
X(6)
X(7)
y(n)
z(n)
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 31/39
Dodatek 1
Algorytm STF (FFT) z podziałem czasowym
• istota algorytmu
STF
zostanie przedstawiona na przykładzie algorytmu z podziałem
czasowym
- niech sygnał
( )
t
x
po operacji próbkowania zostanie przedstawiony ciągiem
N
próbek
( )
{
}
1
...,
,
1
,
0
,
−
=
N
n
n
x
, przy czym
ν
= 2
N
,
ν
- liczba naturalna
- oznaczmy połowę liczby tych próbek
2
N
o numerach parzystych przez
( )
r
y
( )
{
}
( ) ( ) ( )
(
)
{
}
( )
{
}
r
x
N
x
x
x
x
r
y
2
2
...,
,
4
,
2
,
0
=
−
=
,
1
2
...,
,
2
,
1
,
0
−
=
N
r
- oznaczmy drugą połowę liczby próbek
2
N
o numerach nieparzystych przez
( )
r
z
( )
{ }
( ) ( ) ( )
(
)
{
}
(
)
{
}
1
2
1
...,
,
5
,
3
,
1
+
=
−
=
r
x
N
x
x
x
x
r
z
1
2
...,
,
2
,
1
,
0
−
=
N
r
-
DTF
ciągu
( )
{
}
1
...,
,
1
,
0
,
−
=
N
n
n
x
określa wyrażenie
( )
( )
( )
1
...,
,
1
,
0
,
1
0
1
0
2
−
=
=
=
∑
∑
−
=
−
=
π
−
N
k
W
n
x
e
n
x
k
X
N
n
kn
N
N
n
kn
N
j
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 32/39
Algorytm STF (FFT) z podziałem czasowym (cd)
-
DTF
ciągów
( )
{
}
1
2
...,
,
2
,
1
,
0
,
−
=
N
r
r
y
oraz
( )
{ }
1
2
...,
,
2
,
1
,
0
,
−
=
N
r
r
z
określają odpowiednio wyrażenia
( )
( )
( )
1
...,
,
1
,
0
,
1
2
0
2
1
2
0
2
2
−
=
=
=
∑
∑
−
=
−
=
π
−
N
k
W
r
y
e
r
y
k
Y
N
r
kr
N
N
r
kr
N
j
( )
( )
( )
1
...,
,
1
,
0
,
1
2
0
2
1
2
0
2
2
−
=
=
=
∑
∑
−
=
−
=
π
−
N
k
W
r
z
e
r
z
k
Z
N
r
kr
N
N
r
kr
N
j
- ponieważ
(
)
kr
N
j
r
j
kr
N
j
r
N
N
j
kr
N
j
r
N
k
N
j
e
e
e
e
e
e
2
2
2
2
2
2
2
2
2
2
2
2
2
π
−
π
−
π
−
π
−
π
−
+
π
−
=
=
=
zatem ciągi
( )
k
Y
oraz
( )
k
Z
są okresowe względem
k
z okresem
2
N
, tzn.:
( )
+
=
2
N
k
Y
k
Y
( )
+
=
2
N
k
Z
k
Z
oraz
2
2
2
2
N
j
N
j
e
e
π
−
π
−
=
czyli
2
2
N
N
W
W =
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 33/39
Algorytm STF (FFT) z podziałem czasowym (cd)
- ostatecznie
( )
( )
1
2
...,
,
1
,
0
,
1
2
0
2
−
=
=
∑
−
=
N
k
W
r
y
k
Y
N
r
kr
N
( )
( )
1
2
...,
,
1
,
0
,
1
2
0
2
−
=
=
∑
−
=
N
k
W
r
z
k
Z
N
r
kr
N
- transformata
( )
k
X
może być przedstawiona jako suma
( )
( )
( )
( )
(
)
(
)
∑
∑
∑
∑
−
=
+
π
−
−
=
π
−
π
−
π
−
+
+
=
=
+
=
1
2
0
1
2
2
1
2
0
2
2
e
nieparzyst
2
parzyste
2
1
2
2
N
r
r
k
N
j
N
r
r
k
N
j
n
kn
N
j
n
kn
N
j
e
r
x
e
r
x
e
n
x
e
n
x
k
X
,
1
...,
,
1
,
0
−
=
N
k
- czyli (wykorzystując, że
2
2
N
N
W
W =
)
( )
( )
( )
∑
∑
−
=
−
=
+
=
1
2
0
2
1
2
0
2
N
r
kr
N
k
N
N
r
kr
N
W
r
z
W
W
r
y
k
X
,
1
...,
,
1
,
0
−
=
N
k
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 34/39
Algorytm STF (FFT) z podziałem czasowym (cd)
- ostatecznie
( )
( )
( )
k
Z
W
k
Y
k
X
k
N
+
=
,
1
...,
,
1
,
0
−
=
N
k
ponadto uwzględniając, że
k
N
N
N
j
k
N
N
N
k
N
N
k
N
W
e
W
W
W
W
−
=
=
=
π
−
+
2
2
2
2
możemy napisać
( )
( )
( )
k
Z
W
k
Y
k
X
k
N
+
=
,
1
2
...,
,
1
,
0
−
=
N
k
( )
( )
( )
k
Z
W
k
Y
k
X
k
N
−
=
,
1
...,
,
2
−
=
N
N
k
lub inaczej
( )
( )
( )
k
Z
W
k
Y
k
X
k
N
+
=
,
1
2
...,
,
1
,
0
−
=
N
k
(
)
( )
( )
k
Z
W
k
Y
N
k
X
k
N
−
=
+
2
,
1
2
...,
,
1
,
0
−
=
N
k
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 35/39
Dodatek 2
Szacowanie złożoności obliczeniowej algorytmów filtracji (dla ciągów
N
N
N
=
=
2
1
)
• bezpośrednie wyznaczanie sumy splotowej
algorytm z pominięciem iloczynów zerowych przyjmuje postać
( )
( ) (
)
( ) (
)
−
≤
≤
−
<
≤
−
=
∑
∑
−
+
−
=
=
2
2
0
1
1
0
N
n
N
k
n
h
k
x
N
n
k
n
h
k
x
n
y
n
N
n
k
n
k
dla
dla
można wykazać, że do wyznaczenia
1
2
−
N
próbek splotu należy wykonać
2
N
operacji
mnożenia oraz
(
)
2
1
−
N
operacji dodawania ( w ogólnym przypadku zespolonych) co
daje łączną liczbę operacji algorytmu splotowego
(
)
(
)
1
1
2
1
2
2
+
−
=
−
+
=
+
=
N
N
N
N
O
O
O
convA
convM
conv
• algorytm z wykorzystaniem
DTF
rozmiar
DTF
powinien być równy co najmniej
N
N
2
' =
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 36/39
Szacowanie złożoności obliczeniowej algorytmów filtracji (cd)
- do wyznaczenia
'
N
punktowej transformaty
DTF
(transformatę Fouriera odpowiedzi
impulsowej filtru wykonujemy w czasie nierzeczywistym, zatem nie wliczamy jej do
złożoności obliczeniowej)
( )
2
2
2
4
2
'
N
N
N
O
M
DTF
=
=
=
(
)
(
)
N
N
N
N
N
N
O
A
DTF
2
4
1
2
2
1
'
'
2
−
=
−
=
−
=
N
N
N
N
N
O
O
O
A
DTF
M
DTF
DTF
2
8
2
4
4
2
2
2
−
=
−
+
=
+
=
- do wyznaczenia
'
N
punktowego iloczynu w dziedzinie częstotliwości
N
N
O
M
2
' =
=
- do wyznaczenia
'
N
punktowej
ODTF
(dodatkowe
'
N
mnożeń przez
'
1 N
)
2
2
8
2
2
8
'
N
N
N
N
N
O
O
DTF
ODTF
=
+
−
=
+
=
- łącznie
2
2
2
16
8
2
2
8
N
N
N
N
N
O
O
O
O
ODTF
M
DTF
D
=
+
+
−
=
+
+
=
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 37/39
Szacowanie złożoności obliczeniowej algorytmów filtracji (cd)
• algorytm z wykorzystaniem
STF
rozmiar
STF
powinien być równy co najmniej
N
N
2
' =
- do wyznaczenia
'
N
punktowej
STF
(bez
[ ]
n
h
STF (
)
N
N
N
N
O
M
STF
2
log
'
log
2
'
2
2
=
=
N
N
N
N
O
A
STF
2
log
2
'
log
'
2
2
=
=
N
N
N
N
N
N
O
O
O
A
STF
M
STF
STF
2
log
3
2
log
2
2
log
2
2
2
=
+
=
+
=
- do wyznaczenia
'
N
punktowego iloczynu w dziedzinie częstotliwości
N
N
O
M
2
' =
=
- do wyznaczenia
'
N
punktowej
OSTF
(dodatkowe
'
N
mnożeń przez
'
1 N
)
N
N
N
N
O
O
STF
OSTF
2
2
log
3
'
2
+
=
+
=
- łącznie
2
2
2
2
2
log
3
2
2
log
3
N
N
N
N
N
N
O
O
O
O
OSTF
M
STF
S
+
+
+
=
+
+
=
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 38/39
Szacowanie złożoności obliczeniowej algorytmów filtracji (cd)
- ostatecznie
(
)
4
2
log
6
2
+
=
N
N
O
S
• przykład 1
1024
=
N
(
)
105
095
2
1
1024
1024
2
=
−
⋅
=
conv
O
216
777
16
1024
16
2
=
⋅
=
D
O
2
.
29
≅
S
conv
O
O
(
)
680
71
4
1024
2
log
6
1024
2
=
+
⋅
=
S
O
• przykład 2
2048
=
N
(
)
513
384
8
1
2048
2048
2
=
−
⋅
=
conv
O
864
108
67
2048
16
2
=
⋅
=
D
O
9
.
53
≅
S
conv
O
O
(
)
648
155
4
2048
2
log
6
2048
2
=
+
⋅
=
S
O
9. Analiza widmowa dyskretnych sygnałów zdeterminowanych.doc, 39/39
BIBLIOGRAFIA
1. Szabatin J.: Przetwarzanie sygnałów. Materiały dydaktyczne Politechniki Warszawskiej,
2003,
www.ise.pw.pl/~szabatin
.
2. Izydorczyk J., Płonka G., Tyma G.: Teoria sygnałów. Kompendium wiedzy na temat
sygnałów i metod ich przetwarzania, Helion, Gliwice, 2006
3. Zieliński T.P.: Cyfrowe przetwarzanie sygnałów. Od teorii do zastosowań. WKŁ,
Warszawa 2005.
4. Oppenheim A.V.: Cyfrowe przetwarzanie sygnałów. WKŁ, Warszawa, 1979.
5. Goca J.: Metody obróbki sygnałów wykorzystujące FFT. Część 1, Teoria szybkiego
przekształcenia Fouriera. Skrypt WAT, Warszawa, 1985.
6. Proakis J. G., Manoloakis D. G.: Digital Signal Processing. Principles, Algorithms, and
Applications. Third Edition. Prentice Hall, Upper Saddle River, New Jersey, 1996.