FFT
Masz już teraz pewne pojęcie, jak potężnym narzędziem jest dyskretna transformata Fouriera (DFT). Fourier żył w XVIII wieku, jednak prawdziwa sygnałowa rewolucja nastąpiła w drugiej połowie XX wieku. Dopiero kiedy opracowano algorytm szybkiego obliczania DFT przetwarzanie sygnałów na dobre zaczęło swój rozwój.To, co kiedyś zajmowało nieprawdopodobnie dużo czasu teraz przy użyciu komputerów może być obliczone w przeciągu sekund. Dzięki FFT możliwe stało się przetwarzania złożonych sygnałów, składających się z setek tysięcy czy milionów próbek. To właśnie temu algorytmowi zawdzięczamy m.in. przetwarzanie mowy czy kompresję obrazów.
Co więc takiego szczególnego wniosło FFT do przetwarzania sygnałów ? Paradoksalnie odpowiedzią jest kolejne pytanie:
Ile operacji wymaga obliczenie DFT ?
Hm... To zależy...
Obliczanie DFT przy użyciu wzoru, który poznałeś wcześniej wymaga O(N^2) operacji.
FFT znacznie zmniejsza tą liczbę.
Poszczególne implementacje FFT różnią się złożonością obliczeniową (liczbą działań, które musimy wykonać). Algorytmy bazujące na metodzie dziel i zwyciężaj mają złożoność O(N). Należy do nich najpopularniejsza wersja FFT - algorytm Cooleya-Tukeya.
Polega on na dzieleniu transformaty na odcinki o długości N/2 w każdym kolejnym kroku. Dlatego ilość obliczanych punktów musi być całkowitą wielokrotnością liczby 2.
Istnieją jednak implementacje, które osiągają złożoność O(N logN) !
Wykonanie każdej z operacji zajmuje komputerowi określoną ilość czasu, dlatego im jest ich mniej tym odpowiednio krótszy czas przetwarzania.
Żeby uświadomić sobie jak radykalna jest różnica pomiędzy tymi trzema algorytmami spójrz na wykres poniżej.
Dla małej ilości próbek różnice są zaniedbywalne, ale jeśli jest ich tysiąc różnica robi się imponująca.
Który algorytm byś wybrał mając do przetworzenia 100 000 próbek ?
