W tym rozdziale przedstawimy zadania laboratoryjne, w których przetestujemy
dyskretną transformatę Fouriera (DFT) oraz szybki algorytm jej obliczania, czyli algorytm szybkiej trasformaty Fouriera; FFT (ang. Fast Fourier Transform)
W opisie matematycznym przyjmujemy, że mamy do czynienia z wektorami okresowymi o okresie długości indeksowanymi od zera i
dla
ujemnych.
Przez oznaczymy wynik działania operatora DFT na wektorze
, a przez
oznaczymy wynik działania operatora odwrotnego do DFT na wektorze
.
- Funkcja octave'a z algorytmem FFT
fft()
, która oblicza wartość DFT i funkcja octave'a z algorytmem odwrotnym FFTifft()
, która oblicza wartość transformaty odwrotnej do DFT.Sprawdź, czy rzeczywiście operacje wykonywane przez
fft()
iifft()
są do siebie odwrotne, tzn. dla różnych losowych wektorów
o długości
policz
za pomocą
fft()
, a następnieza pomocą
ifft()
.Policz normy drugie różnicy
.
- Skalowanie w funkcjach octave'a
fft()
iifft()
.W literaturze zdarza się definicja DFT bez
przed macierzą.
Wtedy macierz odwrotną do DFT należy przemnożyć przezalbo obie przez
.
Sprawdź, jaka jest stała przed DFT obliczanym przez funkcję
fft()
, tzn. wyznacztakie, że
dla
obliczanego przez tę funkcję octave'a .
-
Sprawdź, czy DFT obliczona przy pomocy funkcji
fft()
spełniaze stałą
dla stu losowych wektorów
, oraz czy analogicznie odwrotna DFT obliczona
ifft()
spełnia: - Algorytm szybkiego mnożenia wielomianów.
Napisz funkcję octave'a
function w=polymult(p,q)szybko mnożącą dwa wielomiany stopnia nie większego od
, dla których znamy ich współczynniki w bazie potęgowej. Funkcja powinna korzystać z DFT i odwrotnej DFT, czyli dyskretnej transformaty Fouriera i odwrotnej dyskretnej transformaty Fouriera.
Parametry funkcji powinny być:
- wektor
ze współczynnikami wielomianu
,
- wektor
ze współczynnikami wielomianu
.
- DFT a dyskretny splot dwóch wektorów.
Napisz dwie funkcje
obliczające splot dwóch wektorów - wprost z definicji, tzn.
- z wykorzystaniem DFT - tu musimy skorzystać z tego, że
dla pewnej stałej
.
Trzeba tę stałą wyznaczyć teoretycznie albo eksperymentalnie.Przetestuj obie funkcje dla losowych wektorów i różnych
.
Porównaj z wynikami funkcji octave'aconv()
. Należy zapoznać się z pomocą do tej funkcji. - Filtry a DFT.
W niektórych zastosowaniach współczynniki wektora
mogą odpowiadać próbkom sygnału (np. dźwięku). Stosuje się wtedy filtry w postaci splotu
z zadanym wektorem
pełniącym rolę filtru:
.
Rozważmy filtr postaci
(pierwsze cztery współrzędne są równe
, pozostałe - zero).
Zastosuj ten filtr do wektora imitującego próbki sygnału z szumem:
,
gdziedla
- imituje sygnał bez szumów, a
jest wektorem losowym o wartościach w
imitującym losowe zaburzenie, czyli tzw. szumy. Przetestuj filtr dla dużych
, np.
lub
, tzn.:
-
Narysuj wykres
przed zastosowaniem filtra i po zastosowaniu, tzn.
wykresyi
. Można narysować mały fragment wykresu, np dla
. Jaki efekt optyczny widać na wykresach?
- Policz maksimum z modułu różnicy kolejnych elementów obu wektorów, tzn.
i
. Im ta wartość dla danego wektora z próbkami sygnału jest mniejsza, tym sygnał jest gładszy, czyli możemy uznać go za sygnał z mniejszą ilością szumów.
Funkcja powinna zwrócić
współczynniki wielomianu .
Sprawdź działanie funkcji dla wielomianów i
, czyli
, a potem dla wielomianów dużych stopni, czyli np. dla
i
funkcja powinna zwrócić współczynniki wielomianu
.
Porównaj czas obliczeń tej funkcji z wynikiem funkcji octave'a conv()
dla wielomianów różnych stopni z losowymi współczynnikami.