Rozdział 7DFT i FFT

Wszystko dotychczas budowało intuicję. To jest rzeczywisty algorytm: mając tylko listę spróbkowanych liczb, oblicz dokładnie, jakie częstotliwości są w sygnale — bez podglądania, jak został zbudowany.

Zaprojektuj sygnał (tak jak w Rozdziale 5)

Przeciągnij, by ustawić amplitudę każdej częstotliwości

Widmo obliczone wyłącznie z próbek (wynik DFT)

Sygnał / próbki |X_k| odzyskane przez DFT

Wzór

Dyskretna Transformata Fouriera bierze $N$ próbek $x_0, x_1, \dots, x_{N-1}$ i produkuje $N$ liczb zespolonych opisujących zawartość częstotliwościową sygnału:

Dyskretna Transformata Fouriera

$$ X_k = \sum_{n=0}^{N-1} x_n \, e^{-i 2\pi k n / N} \qquad k = 0, 1, \dots, N-1 $$

Każde $X_k$ odpowiada na jedno pytanie: „ile jest częstotliwości $k$ (w cyklach na okno próbek)?" $|X_k|$ — moduł tej liczby zespolonej — to dokładnie wysokość słupka, którą widzisz na wykresie powyżej. To ta sama rotacja $e^{-i\theta}$ co okręgi z Rozdziału 4, tylko wykonana raz dla każdej częstotliwości, którą chcesz sprawdzić, zamiast rysowana w czasie.

Zauważ, że widmo powyżej zapala się tylko na częstotliwościach, które faktycznie ustawiłeś suwakami — wszystko inne odczytuje się jako praktycznie zero. DFT odzyskała twoją recepturę częstotliwości z niczego innego jak surowych wartości próbek.

Dlaczego istnieje FFT

Obliczony bezpośrednio, powyższy wzór kosztuje $O(N^2)$ mnożeń — dla każdej z $N$ częstotliwości wyjściowych sumujesz po wszystkich $N$ próbkach wejściowych. Szybka Transformata Fouriera (FFT) to nie inny wzór; to ta sama DFT obliczona sprytnie, poprzez rekurencyjne dzielenie sumy na próbki o parzystych i nieparzystych indeksach oraz ponowne wykorzystanie pracy między nimi. To obniża koszt do $O(N \log N)$:

N (próbki)	DFT: N² operacji	FFT: N·log₂N operacji	Przyspieszenie

Przy małym $N$ różnica ledwo ma znaczenie. Przy rozmiarach używanych w rzeczywistym przetwarzaniu dźwięku, obrazów i sygnałów radiowych — miliony próbek — FFT jest jedynym powodem, dla którego cokolwiek z tego działa w czasie rzeczywistym.

Cała pętla, w jednym zdaniu: sygnał jest próbkowany (Rozdz. 6) z zachowaniem limitu Nyquista, FFT zamienia te próbki w widmo (ten rozdział), korzystając z tego samego pomysłu wirującego fazora co epicykle (Rozdz. 4), to widmo jest edytowane lub analizowane w dziedzinie częstotliwości (Rozdz. 5), a transformata odwrotna — ten sam wzór wykonany wstecz — odtwarza sygnał w dziedzinie czasu jako sumę fal sinusoidalnych (Rozdz. 3). Ta pętla w obie strony to transformata Fouriera.