[e-mail]
Prof. Krzysztof Jemielniak 5 Przekształcenie Fouriera, część II
http://www.zaoios.pw.edu.pl/kjemiel
ST 107, tel. [phone]
" Przeciek DFT
Przeciek DFT
Cyfrowe
" Okna
przetwarzanie
" Poprawa rozdzielczości DFT
sygnałów
" Poprawa stosunku sygnał/szum DFT
" Szybka transformata Fouriera (FFT)
5. Przekształcenie Fouriera
część II
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
Przeciek DFT Przeciek DFT
DFT ogranicza się do:
" Poprzednie dwa przykłady DFT przyniosły poprawne wyniki,
" operowania na skończonych zbiorach N wartości wejściowych,
ponieważ wejściowe ciągi x[n] stanowiły starannie dobrane
próbkowanych z szybkością fs &
przebiegi sinusoidalne.
" dając w wyniku N-punktową transformatę,&
" Niestety DFT próbkowanych sygnałów rzeczywistych prowadzi do
" której dyskretne wartości wyjściowe są związane z kolejnymi
wyników w dziedzinie częstotliwości, które mogą być mylące.
wartościami częstotliwości fDFT[m]=mfs/N, gdzie m=0, 1, 2,..., N-1&
" Właściwość DFT, znana jako przeciek widma, powoduje że " dla których wyznaczamy kolejne prążki DFT.
wyniki DFT stanowią jedynie aproksymację rzeczywistych widm
DFT daje prawidłowe wyniki jedynie gdy ciąg danych wejściowych
oryginalnych sygnałów wejściowych, poddanych próbkowaniu.
zawiera energię rozłożoną dokładnie przy częstotliwościach mfs/N,
" Wprawdzie istnieją sposoby minimalizacji przecieku, nie możemy
(całkowite wielokrotności częstotliwości podstawowej fs/N)
wyeliminować go całkowicie.
Jeśli sygnał x[n] zawiera składową o częstotliwości leżącej pomiędzy
" Bardzo ważne jest więc zrozumienie, jaki ma on wpływ na
mfs/N, to ujawni się ona w pewnym stopniu przy wszystkich
uzyskiwane przez nas wyniki DFT.
wyjściowych wartościach częstotliwości DFT!
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
Przeciek DFT Przeciek DFT
Załóżmy, że wyznaczamy 64-punktową DFT ciągu x[n] o dokładnie trzech okresach zawartych w A teraz wyznaczmy 64-punktową DFT ciągu x[n] o dokładnie 3.4 okresach zawartych w N = 64
N = 64 próbkach, oznaczonego kwadratami: próbkach:
|X[m]|
|X[m]| DFT 1.vi DFT 1.vi
sygnał wejściowy x[n]  3 okresy sygnał wejściowy x[n]  3.4 okresy
1 2
czas czas
sinusoida służąca wyznaczeniu X[4]
Pierwszą połowa ciągu X[m] wyników DFT wykazuje, że ciąg x[n] ma
Ponieważ tu x[n] nie ma całkowitej liczby okresów w przedziale 64 próbek, energia wejściowa
zerową wartość średnią (X[0] = 0) oraz, że nie zawiera składowej o
 przecieka do wszystkich innych prążków DFT.
częstotliwości innej niż częstotliwość odpowiadająca m = 3.
Np. prążek dla m = 4, dla przykładu, nie jest równy zeru, ponieważ suma iloczynów ciągu wejściowego i
składowej odpowiadającej analizie częstotliwości dla m = 4 nie jest już równa zeru.
Pokazano tu, dla przykładu, przebieg sinusoidalny służący wyznaczeniu prążka X[4]: To jest przeciek - dowolny sygnał wejściowy, którego częstotliwość nie jest
przebiegi takie mają zawsze całkowitą liczbę okresów w pełnym przedziale próbkowania  dokładnie równa jednej z częstotliwości DFT, przecieka do wszystkich wyznaczanych
tu o długości 64 próbek.
prążków DFT.
Suma iloczynów ciągu wejściowego x[n] i składowej sinusoidalnej odpowiadającej prążkowi
Przy wyznaczamy DFT rzeczywistego ciągu czasowego o skończonej długości przeciek jest nie
DFT X[4] jest równa zeru, podobnie jak dla wszystkich innych sinusoid oprócz m=3.
do uniknięcia.
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
1
Ciągłe widmo cosinusoidy Ciągłe widmo cosinusoidy
Dla rzeczywistego przebiegu cosinusoidalnego, zawierającego k okresów w N-
|X[f]|
punktowym wejściowym ciągu czasowym x[n], wartości prążków N-punktowej
DFT w funkcji indeksu m są aproksymowane za pomocą funkcji sinc:
N sin[�p�(�k -� m)�]�
X[�m]� =� ��
2 p�(�k -� m)�
częstotliwość
Moduł ciągłego widma (k-3)fs/N (k-1)fs/N kfs/N (k+1)fs/N (k+3)fs/N (k+5)fs/N
Dyskretny ciąg DFT zdefiniowany jako
|X[f]|
dyskretnego ciągu
cosinusoidalnego o
" Krzywa przedstawia zawsze dodatnie widmo N-punktowego, rzeczywistego
skończonym czasie trwania
czasowego ciągu cosinusoidalnego, mającego k pełnych okresów w
wejściowym N-punktowym przedziale czasowym.
częstotliwość
" Wartości wyjściowe DFT są dyskretnymi próbkami, które znajdują się na tej
kfs/N
krzywej, czyli wynik DFT będzie spróbkowaną wersją tego widma ciągłego.
(k-3)fs/N (k-1)fs/N (k+1)fs/N (k+3)fs/N (k+5)fs/N
" Jeśli ciąg wejściowy ma dokładnie całkowitą liczbę k okresów, przeciek nie
pojawia się, ponieważ jeśli kąt w liczniku równania jest niezerową całkowitą
listek główny
listki boczne listki boczne
wielokrotnością p� to sinus tego kąta jest równy zeru.
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
Określenie wartości przecieku - przykład Określenie wartości przecieku - przykład
" A teraz załóżmy, że nasza sinusoida ma częstotliwość 8.5 kHz, i pozostawmy
" Na początek rozważymy przypadek, w którym częstotliwość wejściowa k jest
częstotliwość próbkowania bez zmian fs= 32kHz.
równa częstotliwości, dla której jest wyznaczany prążek DFT.
" Jej ciągłe widmo przesunie się w prawo o 0.5 kHz, ale ponieważ 32-punktowa DFT ma
" Załóżmy, że rzeczywista sinusoida o częstotliwości 8 kHz, mająca
punkty w tych samych częstotliwościach co poprzednio (mfs/N) czyli co 1 kHz&
jednostkową amplitudę, została spróbkowaną z szybkością fs= 32kHz.
" widmo amplitudowe tego sygnału, otrzymamy umieszczając wyniki DFT na krzywej dla
" 32-punktowa DFT tych próbek, ma rozdzielczości fs/N=32/32 kHz=1 kHz. tych częstotliwości:
10.17
" Widmo amplitudowe tego sygnału, otrzymamy umieszczając wartość
maksymalną modułu funkcji
częstotliwość kHz
8.5
4 5 6 7 8 9 10 11 12 13
w punkcie odpowiadającym częstotliwości 8 kHz:
16
Dla sinusoidy o częstotliwości 8.75 otrzymamy:
14.05
5.15
częstotliwość kHz
częstotliwość kHz
8.75
3 4 5 6 7 8 9 10 11 12 13
4 5 6 7 8 9 10 11 12 13
Kwadraciki pokazują wartości wyjściowych prążków DFT
Oczywiście badając przeciek metodą wykreślania modułów wartości wyjściowych DFT na
Są one próbkami ciągłej krzywej widmowej
komputerze, otrzymamy kwadraciki, a nie zobaczymy ciągłych krzywych widmowych J�
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
Okresowość widma raz jeszcze Groz
ne skutki przecieku
A teraz wróćmy do omówionej 64-punktowej DFT ciągu x[n] o dokładnie 3.4 okresach zawartych
Wez
my sumę sygnałów sinusoidalnych, 1szy o amplitudzie 10 i 3.2 okresach
w N = 64 próbkach: |X[m]|
w przedziale próbkowania, 2gi o amplitudzie 1 i 7 okresach w tym przedziale
Uzyskane widmo wydaje się niesymetryczne,
Przecieki widma pierwszego sygnału zamaskują widmo drugiego!
ale przecież pokazaliśmy tylko fragment!
Widmo to jest oczywiście cykliczne co 64
punkty. Możemy to przedstawić na wykresie
kołowym:
częstotliwość
lub konwencjonalnie:
m=32
DFT 1.vi
m=31
m=30
3
58
(-6)
60
62
m
(-4) 12
0
10
(-2) 2
8
4 6
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
2
5 Przekształcenie Fouriera, część II DFT z fragmentu sygnału
" DFT może być przeprowadzona jedynie na przedziale próbkowania o
skończonym czasie trwania.
" Przeciek DFT " Jeśli sygnał wejściowy jest nieskończenie długi, albo po prostu za długi
na nasze potrzeby, bierzemy jego fragment.
Okna
" Okna
" Możemy taki fragment traktować jako iloczyn ciągu nieskończonego (za
" Poprawa rozdzielczość DFT
długiego) i okna prostokątnego, tj., sygnału, którego wartość wynosi 1
w przedziale próbkowania (wykonywania DFT), a 0 poza nim.
" Poprawa stosunku sygnał/szum DFT
" Szybka transformata Fouriera (FFT)
Iloczyn sygnałów (modulacja): y[n] = x[n] � w[n]
x[n] y[n]
w[n]
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
DFT z fragmentu sygnału DFT funkcji prostokątnej
Za każdym razem, kiedy wyznaczamy DFT ciągu wejściowego o
skończonym czasie trwania, w sposób domyślny mnożymy ten
ciąg przez okno samych jedynek, a wartości wejściowe poza tym
przedziałem przez zera.
Jak się okazuje, kształt funkcji:
jest spowodowany przez to okno prostokątne, ponieważ
ciągła transformata Fouriera okna prostokątnego jest
funkcją sinc=sin(x)/x.
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
Okienkowanie Okno trójkątne
Okienkowanie zmniejsza przeciek DFT przez zminimalizowanie amplitudy To właśnie nieciągłe zmiany okna prostokątnego pomiędzy wartością jeden, a zero są
przyczyną listków bocznych widma tego sygnału, wyrażane funkcją sinc.
listków bocznych funkcji
Aby zminimalizować przeciek widma (listki boczne) należy zmniejszyć ich wartości
używając funkcji okna innych niż okno prostokątne
Zacznijmy od najprostszego rozwiązania: okno trójkątne.
x[n] y[n]
w[n]
" Wartości wynikowego sygnału wejściowego stają się takie same na początku i końcu
przedziału próbkowania.
" Zredukowana nieciągłość zmniejsza poziom wysokich składowych częstotliwościowych DFT
" poziomy prążków DFT listków bocznych mają zmniejszoną wartość
Okienkowanie polega na wymuszeniu na wartościach wejściowego ciągu
czasowego zarówno na początku, jak i na końcu przedziału próbkowania,
gładkiego zmierzania do pojedynczej wspólnej wartości.
DFT funkcji prostokątnej DFT funkcji trójkątnej
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
3
Funkcje okna Skalowanie funkcji okna
Ponieważ okna zmniejszają w dziedzinie czasu poziomy sygnałów poddawanych DFT, jeśli
Istnieje szereg innych funkcji okna, minimalizujących przecieki widma
interesują nas bezwzględne wartości składowych sygnałów, należy je pomnożyć przez
nawet bardziej niż okno trójkątne.
odpowiednie współczynniki, tak, by pole funkcji okna było równe polu okna prostokątnego:
Zestawmy wzory na najbardziej podstawowe:
syganał oryginalny po przemnożeniu przez okno po przemnożeniu przez okno i a
Okno prostokątne: w[n] = 1 dla n=0, 1, 2, ..., N-1
Okno trójkątne a = 1/0.5=2
Okno trójkątne: w[n] = n/(N/2) dla n=0, 1, 2,..., N/2 oraz
w[n] = 2  n/(N/2) dla n=N/2+1, ...., N-1
Okno Hanninga: a = 1/0.5=2
0.5  0.5 cos(2p�n/N)
Okno Hanninga: w[n] = 0.5  0.5 cos(2p�n/N) dla n=0, 1, 2,..., N-1
Okno Hamminga: a = 1/0.54=1.85
Okno Hamminga: w[n] = 0.54  0.4 6cos(2p�n/N) dla n=0, 1, 2,..., N-1
0.54  0.4 6cos(2p�n/N)
Okno Blackmana w[n] = 0.42  0.50cos(2p�n/N) + 0.08cos(2p�n/N)]
Okno Blackmana a = 1/0.42=2.38
dla n=0, 1, 2,..., N-1
0.42  0.50cos(2p�n/N) + 0.08cos(2p�n/N)] DFT 2 vi
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
Cechy charakterystyczne okien Porównanie modułów DFT okien
Amplitudy w skali liniowej Amplitudy w skali logarytmicznej
1. Rozdzielczość  zdolność do rozróżnienia różnych tonów
(czystych sinusoid)
" jest odwrotnie proporcjonalna do szerokości głównego listka
" pożądana jak najwyższa
2. Maksimum pierwszego listka bocznego.
fs/N 2fs/N 3fs/N 4fs/N fs/N 2fs/N 3fs/N 4fs/N
" decyduje o tym, czy słabe sygnały będą ukryte przez sąsiednie
" Główny listek boczny okna prostokątnego jest najwęższy, i wynosi 2fs/N (tu widzimy jego połowę). J�
silne
" jego pierwszy listek boczny leży jedynie o  13 dB poniżej szczytu listka głównego L�
" pożądane jak najniższe
" Inne okna mają zmniejszone listki boczne& J�
" & ale co najmniej dwukrotnie szerszy listek główny L�
3. Szybkość spadku amplitudy kolejnych listków " oznacza to dwukrotną degradację rozdzielczości częstotliwościowej DFT L�
" istotne korzyści zmniejszenia przecieku zazwyczaj przeważają nad tą stratą J�
" decyduje o wpływie silnych sygnałów na odleglejsze słabsze
" Okno trójkątne ma ponadto szerokie listki boczne L�
" kompromis z maksimum pierwszego
" Okno Hanninga szybciej zmniejsza poziom pierwszego i następnych listków bocznych J�
" Okno Hamminga ma nawet niniejsze poziomy pierwszego listka J�, lecz dalsze listki opadają wolniej w
" pożądana jak najwyższa
porównaniu z oknem Hanninga L�.
" Okno Blackmana ma najszerszy listek główny L� (aż 3fs/N) ale najmniejsze listki boczne J�
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
Wpływ okna na widmo sygnału Ograniczanie groz
nych skutków przecieku
Wróćmy do omawianego przykładu 64-punktowej DFT ciągu x[n] o dokładnie 3.4 okresach
Pamiętacie sumę sygnałów sinusoidalnych, 1szy o amplitudzie 10 i 3.2 okresach w
zawartych w N = 64 próbkach i zastosujmy do niego okno Hanninga:
przedziale próbkowania, 2gi o amplitudzie 1 i 7 okresach w tym przedziale?
sygnał w oknie prostokątnym
Zastosujmy okno Hanninga!
sygnał w oknie Hanniga
widmo sygnału w oknie prostokątnym
widmo sygnału w oknie Hanniga
widmo sygnału w oknie prostokątnym
w skali liniowej...
widmo sygnału w oknie prostokątnym DFT 1.vi
widmo sygnału w oknie Hanniga
widmo sygnału w oknie prostokątnym
4
widmo sygnału w oknie Hanniga
widmo sygnału w oknie Hanniga
...i logarytmicznej
Widmo amplitudowe dla okna Hanninga jest szersze lecz przeciek listków bocznych
jest zauważalnie zmniejszony w porównaniu z przeciekiem dla okna prostokątnego
Składowa stała może przysłonić sąsiednie prążki! Wyeliminować wcześniej!
Jest to szczególnie uderzające w skali decybelowej (logarytmicznej)
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
4
Wybór okna 5 Przekształcenie Fouriera, część II
" Istnieje bardzo wiele różnych funkcji okien
" nie jest oczywiste, że istnieje wielka różnica pomiędzy wieloma spośród nich
" Różne funkcje okien mają swoje własne indywidualne zalety i wady.
" Przeciek DFT
" Niezależnie od użytej funkcji okna, zmniejszyliśmy przeciek w
porównaniu z przeciekiem z użyciem okna prostokątnego.
" Okna
" Wybór okna stanowi kompromis pomiędzy:
" Poprawa rozdzielczość DFT
Poprawa rozdzielczość DFT
1. rozszerzeniem listka głównego,
2. poziomami pierwszego listka bocznego,
" Poprawa stosunku sygnał/szum DFT
3. szybkością malenia listków bocznych
" Szybka transformata Fouriera (FFT)
sygnał pożądane cechy okna zalecane okno
" odległe składowe " mocno malejące listki boczne " Hanninga
" Hamminga
" małe pierwsze listki boczne
" bliskie składowe
" dokładność pomiaru
" Blackmana
" szeroki listek główny
pojedynczej sinusoidy
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
Rozdzielczości DFT raz jeszcze Poprawa rozdzielczości DFT
" Przypomnijmy, że próbkowanie funkcji ciągłej w dziedzinie czasu, mającą
" Czy możemy zwiększyć rozdzielczość DFT bez zwiększania czasu
ciągłą transformatę Fouriera (Continuous Fourier Transform - CFT) i wyznaczanie
próbkowania?
DFT tych próbek daje w wyniku próbkowaną aproksymację CFT w dziedzinie
" TAK! Przez uzupełnienie sygnału zerami.
częstotliwości. fs=1024Hz,
Ns=16,
" Im więcej jest punktów w DFT, tym lepiej wartości wyjściowe tej DFT
dodane N0=16 próbek zerowych, razem N=32 próbki:
f=218Hz
aproksymują CFT, jako że rozdzielczość DFT wynosi fs/N=1/(czas próbkowania)
DFT 1.vi
5
fs=1024Hz,
N=16,
f=218Hz
dodane N0=112 próbki zerowe, razem N=128 próbki:
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
Amplitudy i częstotliwości DFT po uzupełnianiu zerami
Kolejność postępowania przy wyznaczaniu DFT
" Przy wyznaczaniu amplitudy składowych częstotliwościowych sygnału
Sygnał oryginalny
bierzemy pod uwagę jedynie liczbę próbek sygnału oryginalnego:
x0[m]=Xmag[m]/(Ns/2)=|X[m]|/(Ns/2)
1 Usuń składową stałą
gdzie Ns  liczba próbek w sygnale oryginalnym
" Przy wyznaczaniu częstotliwości poszczególnych składowych DFT
bierzemy pod uwagę całkowitą liczbę analizowanych próbek:
2 Zastosuj okno
mfs
fDFT[�m]�=�
Ns +� N0
" UWAGA! Jeśli stosujemy funkcje okna, należy uczynić to
x0[m]=|X[m]|/(Ns/2)
3 Uzupełnij zerami
przed uzupełnieniem zerami!
" A jeszcze wcześniej usuń składową stałą!
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
5
DFT 1.vi
Poprawa rozdzielczości DFT 5 Przekształcenie Fouriera, część II
6
UWAGA! Uzupełnienie sygnału zerami zwiększa rozdzielczość, lecz nie dokładność widma! L�
fs=100Hz, Ns=100,
f1=3.15Hz, f2=3.25Hz
" Przeciek DFT
T=1s, Df=1Hz
" Okna
jw. + N0=900,
T=10s, Df=0.1Hz
" Poprawa rozdzielczość DFT
" Poprawa stosunku sygnał/szum DFT
Poprawa stosunku sygnał/szum DFT
Zwiększyć dokładność widma można jedynie przez zwiększenie okna czasowego
" Szybka transformata Fouriera (FFT)
fs=10Hz, Ns=100,
f1=3.15Hz, f2=3.25Hz
T=10s, Df=0.1Hz
fs=100Hz, Ns=1000,
f1=3.15Hz, f2=3.25Hz
T=10s, Df=0.1Hz
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
Poprawa stosunku sygnał/szum pojedynczej DFT Poprawa stosunku sygnał/szum pojedynczej DFT
fs=1000Hz, x(t)=sin(2p�50), zakłócenie losowe s=5
" Pojedynczy prążek DFT możemy potraktować jako sygnał wyjściowy
filtru wąskopasmowego, którego środek pasma jest zlokalizowany przy
częstotliwości mfs/N
" Ta wartość wyjściowa jest związana z energią wejściową położoną pod
lub bardzo blisko, głównego listka funkcji sin(x)/x
" Przy wzroście N, listki główne prążka wyjściowego DFT stają się coraz
węższe, a wartość wyjściowa DFT rośnie (Xmag[m] = x0N/2)
" Zmniejszenie szerokości pasma filtru pasmowego jest użyteczne w
N=1000
N=100
N=10000
N=5000
detekcji sygnału, ponieważ poprawia rozdzielczość częstotliwościową.
Przy sygnale zakłóconym losowo zwiększanie liczby próbek
wzmacnia amplitudę sygnału prążka odpowiadającego
sygnałowi, wydobywając go powyżej szumu
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
SNR pojedynczej DFT SNR pojedynczej DFT
" Ogólnie można stwierdzić, że wartość odchylenia standardowego
" Zysk przetwarzania DFT, wyraża ilościowo stosunek
__
(rms) prążka wyjściowego DFT szumu jest proporcjonalna do "N,
sygnał/szum (Signal/Noise Ratio - SNR) zdefiniowany jako
a wartość wyjściowa DFT dla prążka zawierającego sygnał tonu
iloraz poziomu mocy sygnału wyjściowego DFT i uśrednionego
jest proporcjonalna do N
poziomu mocy szumu wyjściowego.
" Stąd zwiększenie liczby próbek z N1 do N2 daje zysk SNR:
" chcemy aby ten stosunek był tak duży, jak to możliwe.
ć� ��
N2 N1
SNRN =� SNRN +� 20log10�� ��
2 1 �� ��
N2 N1
Ł� ł�
" Nie da się stwierdzić jaki będzie SNR dla pojedynczej DFT.
" nie możemy dokładnie przewidzieć energii zawartej w dowolnych
danych N próbkach szumu przypadkowego.
" Czyli jeśli zwiększymy rozmiar DFT z N1 do N2 = 2N1 wyjściowy SNR
" jeśli częstotliwość sygnału wejściowego nie jest zlokalizowana w środku
procedury DFT wzrasta o 3 dB.
prążka, przeciek podniesie efektywny szum tła i obniży wyjściowy SNR
Inaczej mówiąc: zysk przetwarzania DFT wzrasta o
" każde użyte okno będzie miało pewien wpływ na przeciek, i przez to na
wyjściowy SNR
3 dB, jeśli N zostaje podwojone
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
6
SNR pojedynczej DFT Poprawa SNR DFT przez uśrednianie
" Wydłużanie liczby próbek N jest kosztownym obliczeniowo
fs=1000Hz, x(t)=sin(2p�50), zakłócenie losowe s=5
Widma mocy: sposobem poprawy SNR  liczba mnożeń rośnie
proporcjonalnie do N2
" Ponieważ dodawanie jest łatwiejsze i szybsze do
SNR=19.4
N=5000
przeprowadzenia niż mnożenie, możemy uśrednić wartości
wyjściowe wielokrotnych procedur DFT i w ten sposób
uzyskać poprawę SNR można także uzyskać przez
uśrednianie szeregu DFT
" Możliwe są dwa, zasadniczo odmienne typy uśredniania:
SNR=22.4
N=10000
" koherentne
DFT 3 SN ratio
" niekoherentne
1
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
DFT 3 SN ratio
Uśrednianie DFT Poprawa SNR DFT przez uśrednianie
2
niekoherentne koherentne
Uśrednianie niekoherentne
N=1000 N=5000 N=1000 N=5000
K = liczba DFT
DFT1(m) +� L� +� DFTK (m)
DFTINCOH(m) =�
K
m = numer prążka, m=0, 1 .. N-1
liczba
powtórzeń
Redukuje zmienność zakłóceń, ale średnia moc zakłóceń nie ulega zmianie.
100
Uśrednianie koherentne
Re{�DFT1(m)}�+� L� +� Re{�DFTK (m)}�+� j �� Im{�DFT1(m)}�+� L� +� Im{�DFTK (m)}�
DFTCOH(m) =�
K K
lp=1000
Moc zakłóceń ulega redukcji, ale wymaga synchronizacji czasowej (fazowej)
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
5 Przekształcenie Fouriera, część II Niewydajność procedury DFT
" DFT jest bezpośrednią procedurą matematyczną do określania
częstotliwościowej zawartości ciągu z dziedziny czasu,
" jest ona bardzo nieefektywna  kosztowna obliczeniowo
" przypomnijmy przykład 4-punktowej DFT:
" Przeciek DFT
X[0] = x[0][cos(2p��0�0/4)  j sin(2p��0�0/4)]+ X[1] =x[0][cos(2p��0�1/4)  j sin(2p��0�1/4)]+
" Okna
x[1][cos(2p��1�0/4)  j sin(2p��1�0/4)]+ x[1][cos(2p��1�1/4)  j sin(2p��1�1/4)]+
x[2][cos(2p��2�0/4)  j sin(2p��2�0/4)]+ x[2][cos(2p��2�1/4)  j sin(2p��2�1/4)]+
x[3][cos(2p��3�0/4)  j sin(2p��3�0/4)]+ x[3][cos(2p��3�1/4)  j sin(2p��3�1/4)]+
" Poprawa rozdzielczość DFT
X[2] =x[0][cos(2p��0�2/4)  j sin(2p��0�2/4)]+ X[3] = x[0][cos(2p��0�3/4)  j sin(2p��0�3/4)]+
" Poprawa stosunku sygnał/szum DFT x[1][cos(2p��1�2/4)  j sin(2p��1�2/4)]+ x[1][cos(2p��1�3/4)  j sin(2p��1�3/4)]+
x[2][cos(2p��2�2/4)  j sin(2p��2�2/4)]+ x[2][cos(2p��2�3/4)  j sin(2p��2�3/4)]+
x[3][cos(2p��3�2/4)  j sin(2p��3�2/4)]+ x[3][cos(2p��3�3/4)  j sin(2p��3�3/4)]+
" Szybka transformata Fouriera (FFT)
Szybka transformata Fouriera (FFT)
" wielokrotne powtarzanie tych samych obliczeń funkcji okresowych
" niewykorzystanie symetrii kosztownych obliczeniowo funkcji sin i cos
" gdy liczba punktów w DFT wzrasta do setek lub tysięcy, liczba
niezbędnych obliczeń staje się bardzo szybko gigantyczna 
DFT-FFT
DFT wymaga N2 mnożeń zespolonych!
1
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
7
Szybka transformata Fouriera (FFT) DFT a FFT
" W 1965 roku Cooley i Tuckey przedstawili bardzo wydajny algorytm
implementujący DFT tzw. szybkie przekształcenie Fouriera (Fast Fourier
" FFT nie jest przybliżeniem DFT!
Transform  FFT)
" można go zastosować liczba próbek jest potęgą 2 (N=2k)
" Jest ona równoważna DFT i to jest DFT.
" nazywany jest algorytmem o podstawie 2 (radix-2 algorithm)
N
Koszt obliczeniowy FFT wynosi: log2N (zauważmy, że log2N=k) " Wszystkie właściwości DFT, a więc symetria
2
wartości wyjściowych, liniowość, wartości
k N DFT FFT
wyjściowe, przeciek, strata zafalowań itd., dotyczą
2 4 16 4
również FFT
5 32 1024 80
7 128 16 384 448
DFT
10 1024 1 048 576 5120
Zakaszmy zatem rękawy i
FFT
12 4096 16 777 216 24 576
wyprowadz
my algorytm FFT!
DFT-FFT
2,3
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
Wyprowadzenie algorytmu FFT Wyprowadzenie algorytmu FFT
Zaczniemy od tradycyjnej N punktowej DFT
N N
-�1 -�1
2p� 2p� 2p�
N-�1 2 2
-� j (�2n)�m -�j m -�j (�2n)�m
N N N
X[�m]�=� +� e �� +� 1]�e
-�j2p�nm N ��x[�2n]�e ��x[�2n
X[�m]�=� n=�0 n=�0
��x[�n]�e dla m=0,1,2,3....,N-1
n=�0
Ciąg danych wejściowych x[n] może być podzielony na dwa podciągi przez wybór co
Dla uproszczenia notacji zapiszmy zespolony czynnik kąta fazowego jako:
drugiego elementu:
N N
-�1 -�1
2p� 2p�
2 2
-� j (�2n)�m -�j (�2n+�1)�m
N N otrzymamy:
X[�m]�=� +� +� 1]�e =�
��x[�2n]�e ��x[�2n
n=�0 n=�0
Zauważmy że:
a więc nasze równanie przyjmie postać:
Jako czynnik niezależny od indeksu sumowania n
 może być wciągnięte przed znak sumy
Zauważmy, iż teraz wykonujemy dwie DFT  dla parzystych i nieparzystych n
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
Wyprowadzenie algorytmu FFT Wyprowadzenie algorytmu FFT
Mamy dotychczas:
Oryginalne równanie DFT miało postać:
A teraz zastanówmy się, jaką postać przyjmie nasz wzór dla prążka (m+N/2)
Po modyfikacjach otrzymaliśmy:
Człony kątów fazowych wewnątrz sumowań można uprościć:
Ponieważ czynnik jest w obu sumach taki sam, można go wyznaczyć
raz uzyskując pewną oszczędność w obliczeniach
Również współczynnik stojący przed znakiem drugiej sumy można uprościć:
2p�
-� j N 2
m+�N m N m m
N
WN 2 =� WN �� WN 2 =� WN �� e =� WN �� e-�jp�
Przypomnijmy, że cały czas mamy indeksy m w zakresie 0...N-1
m m
=� WN ��[�cos(�p�)�-� sin(�p�)�]�=� -�WN
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
8
Wyprowadzenie algorytmu FFT Wyprowadzenie algorytmu FFT
Symetria współczynników
N N
-�1 -�1
2 2
obrotu zmniejsza ich liczbę
nm m nm
X[�m +� N 2]�=� -� WN �� +�1]�WN 2
��x[�2n]�WN 2 ��x[�2n Dla 8 punktowej DFT będziemy mieli:
Mamy ostatecznie:
n=�0 n=�0 potrzebną do obliczenia o
połowę!
x[0] A[0]
X[0]
x[2] A[1]
m
Ale przecież mieliśmy: X[�m]�=� A[m] +� W8 ��B[m]
4 punktowa X[1]
x[4] A[2]
DFT X[2]
Im
x[6] A[3]
jedyna różnica!
X[3]
Oznacza to, że dla otrzymania drugiej połowy widma wystarczy zmienić znak
3
nm
A[�m]�=� W4
współczynnika obrotu i wykorzystać wyniki obliczeń X[m] dla m=0& (N/2)-1 ��x[�2n]���
n=�0
Re
dla m=0...3
A więc do otrzymania N punktowej DFT wystarczy wykonać
3
nm
B[m] =� +�1]��� W4
��x[�2n
n=�0
dwie N/2 punktowe DFT (dla parzystych i nieparzystych n)
x[1]
B[0]
X[4]
dla m=1& (N/2)-1 i wykorzystując otrzymane wartości -1
x[3]
B[1]
X[5]
4 punktowa -1
obliczyć n punktowe DFT.
m
x[5] X[�m +� 4]�=� A[m] -� W8 ��B[m]
B[2]
X[6]
-1
DFT
x[7]
B[3]
Oznaczmy powtarzające się człony jako A i B X[7]
-1
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
2p�
-�j
Wyprowadzenie algorytmu FFT Wyprowadzenie algorytmu FFT
N
WN =� e
N N
-�1 -�1
4 4
N/2 punktową DFT można dalej podzielić na dwie, tym razem N/4 punktowe DFT:
nm m nm
m=0...(N/2)-1
A[�m]�=� WN 4 +� WN 2 �� +� 2]��� WN 4
��x[�4n]��� ��x[�4n
N N N
-�1 -�1 -�1 n=�0 n=�0
2 4 4
nm 2 n+�1)�m Podobnie jak poprzednio rozważmy postać tego wzoru dla m+n/4:
A[�m]�=� WN 2 =� WNnm +� +� 2]��� WN22 =�
��x[�2n]��� ��x[�4n]��� 2 ��x[�4n (�
N N
-�1 -�1
n=�0 n=�0 n=�0
4 4
n m+�N m+�N n m+�N
A[�m +� N 4]�=� WN(�4 4)� +� WN 4 �� +� 2]��� WN(�4 4)�
��x[�4n]��� ��x[�4n
N N
n=�0 n=�0
-�1 -�1
4 4
2 m 2
Człony kątów fazowych wewnątrz sumowań można uprościć:
=� WNnm +� WN 2 �� +� 2]��� WNnm
��x[�4n]��� 2 ��x[�4n 2
n=�0 n=�0 2p�
-� j nN 4
n m+�N nm n nm N 4 nm nm nm
WN(�4 4)� =� WN 4 �� WNN 4 =� WN 4 �� e =� WN 4 �� e-� j2p�n =� WN 4 ��[�cos(�2p�n)�-� jsin(�2p�n)�]�=� WN 4
4
m=0...(N/2)-1
2p� 2p� Współczynnik sprzed znaku drugiej sumy też można uprościć:
-�j 2 -�j
Ponieważ 2 N 2 N 4
WN 2 =� e =� e =� WN 4
2p�
-�j N 4
m+�N m N 4 m N 2 m m m
WN 2 4 =� WN 2 �� WN 2 =� WN 2 �� e =� WN 2 �� e-�jp� =� WN 2[�cos(�p�)�-� jsin(�p�)�]�=� -�WN 2
A[m] może być zapisane jako:
A teraz porównajmy A[m] z A[m+N/4]:
N N
-�1 -�1
4 4
nm m nm
A[�m +� N 4]�=� -� WN 2 �� +� 2]�WN 4 m=0...(N/2)-1
��x[�4n]�WN 4 ��x[�4n
n=�0 n=�0
Podobnie jak poprzednio jedyna różnica to znak
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
Wyprowadzenie algorytmu FFT Wyprowadzenie algorytmu FFT
Przyjrzymy się uważniej składnikom C, D, E i F
Dla naszej 8 punktowej DFT będziemy teraz mieli:
Przyjrzyjmy się uważniej składnikom C, D, E i F
x[0] C[0]
2 punktowa
A[0]
m
x[4] C[1]
DFT A[�m]�=� C[m] +� W4 ��D[m]
A[1]
1
C[m]= x[4n]W nm
S dla m=0, 1 itd.
2
n=0
zauważmy że
x[2]
D[0]
A[2] m
2 punktowa -1
A[�m +� 2]�=� C[m] -� W4 ��D[m] czyli:
x[6]
D[1]
A[3]
DFT -1
C[0]=x[0]+x[4]
Im
1
nm
C[1]=x[0] x[4]
D[m]=
S x[4n+2]W dla m=0, 1
2
n=0
x[1] E[0]
D[0]=x[2]+x[6]
2 punktowa
B[0] Otrzymaliśmy podstawowy element FFT
x[5] E[1]
Re
DFT D[1]=x[2] x[6]
B[1]
1
Pojedynczy motylek 2-punktowej DFT
E[m]= x[4n+1]W nm
S
2 dla m=0, 1
n=0 F[0]=x[1]+x[5]
x[m]
x[3]
F[0] F[1]=x[1] x[5]
B[2]
2 punktowa -1
x[7]
F[1]
B[3]
DFT -1
Symetria współczynników obrotu
E[0]=x[3]+x[7]
W 0
2
x[m+N/2] -1
1 zmniejsza ich liczbę potrzebną do
nm
E[1]=x[3] x[7]
F[m]= x[4n+3]W 2
S dla m=0, 1
obliczenia o połowę!
n=0
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
9
8-punktowe FFT Współczynnik obrotu FFT
C[0] A[0]
X[0]
x[0]
W 3 = W 6
4 8
C[1] A[1]
0
X[4] Im
x[4] W -1
2
5
W
8 W 7
D[0] A[2] 8
0 X[2]
x[2]
W -1
4
Re
D[1] A[3]
W 1 =W2 4
= W
1
2 4 8
X[6]
x[6] 0
W 0 -1 W -1
= = =1
W 0 W 0 W
4
2
8 4 2
E[0] B[0]
3
1
W
X[1] W
x[1]
8
8
W 0
8
= W 1
W 2 4
8
E[1] B[1]
1
x[5] W X[5]
W 0 -1
8
2
F[0] B[2]
0 X[3]
x[3]
W -1 W 2
4
8
Uwzględnienie okresowych nadmiarowości współczynników obrotu
F[1] B[3]
3 w algorytmie FFT umożliwia uzyskanie dodatkowych oszczędności
W X[7]
x[7] W 0 -1 1 -1 W
2 4
8
(zmniejszenie liczby wykonywanych operacji)
Krok 1 Krok 2 Krok 3
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
Zysk obliczeniowy algorytmu FFT Zysk obliczeniowy algorytmu FFT
Bezpośrednia implementacja N-punktowego DFT
" W każdym kroku algorytmu FFT wykonuje się N/2 mnożeń
zespolonych i N sumowań zespolonych
2p�
-� j nm
N-�1 N-�1
N
�� 2p� �� ć� 2p� ��
ć� ł�
" Dwukrotne zwiększenie liczby próbek N wymaga wykonania kolejnego
m=0...N-1
X[�m]� =� e =� x[�n]��� nm�� -� j sin�� nm��ś� =�
��x[�n]��� �� ę�cos�� N N
n=�0 n=�0 �� Ł� ł� Ł� ł�
��
kroku w algorytmie FFT
�� 2p� �� ć� 2p� �� ć� 2p� �� ć� 2p� ��
ć� ł� �� ł�
=� x[�0]��� 0m�� -� j sin�� 0m��ś� +� x[�1]��� 1m�� -� j sin�� 1m��ś� +� " mamy zatem zawsze k=log2(N) kroków w algorytmie FFT
ę�cos�� N N ę�cos�� N N
�� Ł� ł� Ł� ł� Ł� ł� Ł� ł�
�� �� ��
" lub inaczej: dla liczby próbek N=2k liczba kroków wynosi k
�� 2p� �� ć� 2p� �� ć� 2p� �� ć� 2p� ��
ć� ł� �� ł�
+� x[�2]��� 2m�� -� j sin�� 2m��ś� +� x[�3]��� 3m�� -� j sin�� 3m��ś� +�
ę�cos�� N N ę�cos�� N N " W całym algorytmie FFT wykonywanych jest N/2 log2(N) mnożeń
�� Ł� ł� Ł� ł� Ł� ł� Ł� ł�
�� �� ��
Rozpiszmy to na poszczególne składniki&
zespolonych i N log2(N) dodawań zespolonych
L�
�� 2p� �� ć� 2p� �� ć� ł�
ć� ł� �� 2p� �� ć� 2p� ��
(�N (�N
+� x[�(�N -� 2)�]��� (�N -� 2)�m�� -� j sin�� -� 2)�m��ś� +� x[�(�N -� 1)�]��� (�N -� 1)�m�� -� j sin�� -� 1)�m��ś� Liczba mnożeń Liczba dodawań
ę�cos�� N ę�cos�� N
N N
�� Ł� ł� Ł� ł� Ł� ł� Ł� ł� N
�� �� ��
DFT FFT FFT/DFT DFT FFT FFT/DFT
8 64 12 18.75% 56 24 42.86%
N2 mnożeń zespolonych: dla każdego z N prążków DFT wykonywanych
16 256 32 12.50% 240 64 26.67%
jest  jak widać  N mnożeń zespolonych
32 1024 80 7.81% 992 160 16.13%
64 4096 192 4.69% 4032 384 9.52%
N(N-1) sumowań zespolonych: dla każdego z N prążków DFT
128 16384 448 2.73% 16256 896 5.52%
wykonywanych jest  jak widać  N-1 sumowań zespolonych
256 65536 1024 1.56% 65280 2048 3.34%
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
Dostępne programy FFT Dostępne kody FFT
Oczywiście nie ma potrzeby samodzielnie opracowywać algorytmów FFT! Jeśli chcesz samodzielnie wprowadzić kod FFT w swoim programie,
Odpowiednie procedury są dostępne w każdym pakiecie matematycznym również poszukaj kodu w sieci!
Np. w LabVIEW istnieje podprogram: Np. w C++
W sieci można znalez
ć bardzo wiele
programów demonstracyjnych,
pakietów obliczeniowych
http://www.relisoft.com/freeware/freq.html
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
10
Dostępne biblioteki FFT
Oczywiście dostępne są także biblioteki (dll) Jakieś pytania?
http://www.fftw.org/index.html
Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania Politechnika Warszawska, Wydział Inżynierii Produkcji, Instytut Technik Wytwarzania
Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem Zakład Automatyzacji, Obrabiarek i Obróbki Skrawaniem
11