Monte Carlo Simulation | mysimulator.uk

Dyskreta Transformata Fouriera i dlaczego jest wolna

DFT przekształca N próbek z domeny czasu na N współczynników w domenie częstotliwości, X[k] = Σ x[n]·e^(−j2πkn/N), gdzie każdy wyjściowy X[k] mierzy, jak duża jest część częstotliwości k/N w sygnale. Bezpośrednie obliczanie tego wymaga sumowania N terminów dla każdego z N wartości wyjściowych – N × N = N² mnożeń zespolonych. Dla N = 1024 oznacza to ponad milion operacji; przed powstaniem FFT, 1024-punktowa DFT na sprzęcie z lat 60. zajmowała kilka minut.

Podział i podbój: podział na parzyste i nieparzyste

Wskazówka Cooleya i Tookeya z 1965 roku (przewidziana przez Gauss’a około 1805 roku) polegała na podzieleniu N-punktowego DFT na dwie DFT o rozmiarze N/2, jedną dotyczącą próbek o parzystych indeksach, a drugą dotyczących próbek o nieparzystych indeksach: X[k] = E[k] + W_N^k·O[k]. Ponieważ E[k] i O[k] są okresowe z określeniem N/2, każdy wynik jest wykorzystywany zarówno dla k, jak i k+N/2 dzięki aktualizacji motylkowej X[k+N/2] = E[k] − W_N^k·O[k]. Rekursyjne zastosowanie tego podziału daje rekurencję T(N) = 2T(N/2) + O(N), która rozwiązuje się do O(N log N) — dla N = 1024, około 10 000 operacji zamiast miliona, co stanowi przyspieszenie 100-krotne, a jego wpływ staje się jeszcze bardziej dramatyczny w przypadku większych N.

demo na żywo · powiązana symulacja● LIVE

Czynniki rotacyjne i odwrotna permutacja bitów

Termin obrotowy W_N^k = e^(-j2πk/N) nazywany jest czynnikiem twidla. Jego kluczowa symetria, W_N^(k+N/2) = -W_N^k, oznacza, że każdy motyl (butterfly) wykorzystuje pojedyncze mnożenie zespolone do wygenerowania dwóch wyników — ponownie obniżając liczbę mnożeń na poziomie podziału i podboju. Ponieważ rekurencyjne rozdzielenie parzyste-nieparzyste naturalnie dezorganizuje kolejność wyjścia, implementacja w miejscu najpierw przekształca wejście przy użyciu permutacji bitowej odwrotnej — zamieniając każdy indeks na jego cyfry binarne — aby fazy motyla mogły działać w miejscu i nadal dostarczać naturalnie ułożony spektrum na końcu.

N (samples)   Naive DFT (N²)   FFT (N log₂N)   Speedup
64            4,096            384             ~10×
1,024         1,048,576        10,240          ~100×
65,536        4,294,967,296    1,048,576       ~4,000×

Gdzie faktycznie działa FFT

Przetwarzanie audio wykorzystuje ciągłą FFT: okno N próbek, transformacja, dostosowanie binów częstotliwości dla korektora graficznego lub bramy szumowej, a następnie odwrotna operacja i nakładanie z powtórzeniem — przetwarzanie audio w czasie rzeczywistym o częstotliwości 44.1 kHz zazwyczaj wykorzystuje N = 512-4096 odświeżanych dziesiątkami razy na sekundę. Dzięki twierdzeniu konwolucji, łańcuch FFT-pomnożenie-odwrócenie-FFT przekształca O(N²) bezpośrednią konwolucję w O(N log N), podstawę do rewerbuacji konwolucyjnej i szybkiego mnożenia wielomianów. Kompresja blokowa 8x8 JPEG wykorzystuje blisko spokrewnioną transformację kosinusową, DCT. OFDM bezprzewodowy — Wi-Fi, 4G/5G, DAB radio — wykorzystuje odwrotną FFT do przekształcania symboli QAM w domenie częstotliwości na falę do przesyłania, z N sięgającym od 64 (Wi-Fi) do 4096 (5G NR).

Często zadawane pytania

Dlaczego DFT naiwny ma złożoność O(N²) i jak FFT unika tego kosztu?

Obliczanie każdego z N wartości wyjściowych na częstotliwość wymaga sumowania N elementów wejściowych, co daje całkowitą liczbę mnożeń równą N pomnożone przez N = N kwadrat. Zamiast tego, FFT Cooley'ego-Tukeya rekurencyjnie dzieli transformatę na połowy o indeksach parzystych i nieparzystych, wykorzystując współdzielone wyniki poprzez czynniki okresowe (twiddle factors), co zmniejsza całkowitą pracę do O(N log N).

Co to jest czynnik twiddle?

Czynnik twiddle W_N^k = e^(-j2πk/N) to termin rotacji zespolonej mnożony przez próbki na każdym etapie FFT. Jego okresowość i symetria 180-stopniowa, W_N^(k+N/2) = -W_N^k, pozwalają każdemu etapowi skrzyżkowemu (butterfly) ponownie wykorzystać jedno mnożenie do wygenerowania dwóch wyników, co stanowi kluczową sztuczkę stojącą za szybkością algorytmu.

Dlaczego FFT potrzebuje permutacji bit-reversal?

Algorytm Cooley'ego-Tukeya w miejscu naturalnie miesza kolejność wyjściową, dzieląc rekurencyjnie próbki o indeksach parzystych i nieparzystych. Przestawienie wejścia najpierw poprzez odwrócenie bitów każdego indeksu pozwala etapom skrzyżkowym działać w miejscu i nadal generować spektrum w naturalnej kolejności na końcu.

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz the simulation i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.

▶ Otwórz symulację the simulation