FFT — szybka transformata Fouriera wyjaśniona prosto

FFT, czyli szybka transformata Fouriera, to szybki sposób obliczania dyskretnej transformaty Fouriera (DFT). Jeśli zaczynasz od równomiernie rozmieszczonych próbek, DFT mówi, ile każdego dyskretnego wzorca częstotliwości występuje w tych próbkach.

Najważniejsze jest to, że FFT nie zmienia wyniku. Daje te same wartości DFT co wzór bezpośredni, ale dochodzi do nich przy znacznie mniejszej liczbie powtarzających się obliczeń.

FFT w jednym zdaniu

FFT to szybszy algorytm obliczania tych samych wartości w dziedzinie częstotliwości, które definiuje DFT.

Co mierzy DFT

Załóżmy, że masz próbki $x_0, x_1, \dots, x_{N-1}$. DFT tworzy liczby $X_0, X_1, \dots, X_{N-1}$ zdefiniowane przez

$$X_k = \sum_{n=0}^{N-1} x_n e^{-i 2 \pi kn / N}$$

Każde $X_k$ mierzy, jak silnie dane pasują do jednego dyskretnego wzorca częstotliwości.

Jeśli próbki są równomiernie rozmieszczone z częstotliwością próbkowania $f_s$, to sąsiednie koszyki częstotliwości są oddalone o

$$\frac{f_s}{N}$$

Ten warunek ma znaczenie. Bez znanej częstotliwości próbkowania nadal masz koszyki DFT, ale nie możesz opisać ich jako fizycznych częstotliwości, takich jak herce.

Dlaczego FFT jest szybsza

FFT to rodzina algorytmów służących do wydajnego obliczania DFT. Główna sztuczka polega na ponownym wykorzystaniu struktury w zespolonych czynnikach wykładniczych zamiast przeliczać od zera niemal identyczne sumy.

Najłatwiejsza do wyobrażenia wersja to FFT radix-2. Działa najbardziej naturalnie, gdy $N$ jest potęgą liczby $2$, i dzieli jedną transformatę długości $N$ na dwie transformaty długości $N/2$, a potem łączy wyniki.

Dla bezpośredniego DFT liczba działań rośnie jak $N^2$. Dla typowych metod FFT spada do około $N \log N$.

To właśnie dlatego FFT ma tak duże znaczenie w praktyce. Dla małych danych wejściowych obie metody mogą wydawać się akceptowalne. Dla dużych danych FFT jest dramatycznie szybsza.

Jak FFT dzieli obliczenia

Zamiast bezpośrednio porównywać każdą próbkę z każdym wzorcem częstotliwości, FFT rozbija problem na mniejsze transformaty, a następnie składa je z powrotem za pomocą czynników fazowych.

Standardowy podział wygląda tak:

1. Umieść próbki o parzystych indeksach na jednej liście.
2. Umieść próbki o nieparzystych indeksach na drugiej liście.
3. Oblicz mniejsze transformaty dla tych list.
4. Połącz obie połówki.

To strategia „dziel i zwyciężaj” zastosowana do analizy częstotliwościowej.

Przykład FFT dla 4 punktów

Weźmy sygnał 4-punktowy

$$x = [1, 0, 1, 0]$$

Ten wzorzec zmienia się naprzemiennie między $1$ i $0$, więc oczekujemy pewnej struktury częstotliwościowej zamiast całkowicie płaskiego wyniku.

Podzielmy go na indeksy parzyste i nieparzyste:

$$x_{\text{even}} = [1, 1], \qquad x_{\text{odd}} = [0, 0]$$

DFT 2-punktowe części parzystej to

$$E = [2, 0]$$

a DFT 2-punktowe części nieparzystej to

$$O = [0, 0]$$

Dla 4-punktowego FFT krok łączenia ma postać

$$X_k = E_k + W_4^k O_k, \qquad X_{k+2} = E_k - W_4^k O_k, \qquad k = 0,1$$

gdzie

$$W_4 = e^{-i 2 \pi / 4}$$

Ponieważ $O_k = 0$, łączenie jest szczególnie proste:

$$X = [2, 0, 2, 0]$$

Teraz zinterpretujmy wynik.

$X_0 = 2$ to składnik o zerowej częstotliwości, więc odzwierciedla niezerową wartość średnią próbek. Niezerowa wartość przy $X_2$ opisuje naprzemienną część wzorca w tym przypadku 4-punktowym. Jeśli najpierw odejmiesz średnią, składnik $X_0$ zniknie, a składowa naprzemienna będzie wyraźniej widoczna.

Ten przykład jest mały, ale idea się skaluje: rozwiązujesz mniejsze transformaty, a potem je łączysz, zamiast za każdym razem budować całą sumę od nowa.

Typowe błędy związane z FFT

Traktowanie FFT i DFT jako różnych wyników

Tak nie jest. FFT to szybsza metoda obliczania DFT.

Odczytywanie koszyków jako częstotliwości fizycznych zbyt wcześnie

Położenia koszyków stają się częstotliwościami fizycznymi dopiero wtedy, gdy znany jest odstęp próbkowania. Jeśli częstotliwość próbkowania wynosi $f_s$, to odstęp między koszykami wynosi $f_s/N$ dla próbek równomiernie rozmieszczonych.

Zakładanie, że dopełnianie zerami dodaje nową informację

Dopełnianie zerami może sprawić, że widmo wygląda na gładsze, ponieważ gęściej próbuje transformatę leżącą u podstaw, ale nie dodaje nowych zmierzonych danych.

Ignorowanie przygotowania sygnału

Usunięcie średniej, okienkowanie i staranny dobór próbkowania mogą mieć duże znaczenie. Jeśli zignorujesz te warunki, wynik FFT może być nadal matematycznie poprawny dla danych próbek, ale mylący w interpretacji.

Gdzie używa się FFT

FFT pojawia się wszędzie tam, gdzie potrzebujesz szybkiej informacji o dziedzinie częstotliwości z danych próbkowanych. Typowe przykłady to analiza widma, filtrowanie, przetwarzanie obrazów, analiza drgań, numeryczne rozwiązywanie równań różniczkowych oraz szybkie obliczenia wielomianów lub splotu.

Powód jest praktyczny: wiele operacji staje się łatwiejszych albo szybszych po przejściu z dziedziny próbek do dziedziny częstotliwości.

Wypróbuj podobny przypadek

Weź $8$ równomiernie rozmieszczonych próbek jednej fali sinusoidalnej na jednym pełnym okresie i oblicz DFT za pomocą kalkulatora lub skryptu. Następnie dodaj stałe przesunięcie i porównaj nowy wynik. Silniejsza wartość przy $X_0$ to prosty sposób, by zobaczyć, co FFT rozdziela.