8416072477

Zauważmy, że

^c* = :rn;£/fe)^e “^Jt>

ⁿ ^ ¹ i=o zaś

T_n(x) = ±c_jeⁱ*i. j=o

Można więc powiedzieć że analiza i synteza fourierowska sprowadzają się do obliczania kombinacji liniowych funkcji wykładniczych.

Na przykład, wyliczanie Co, Ci, • • •, Cn przy użyciu powyższych wzorów wymaga liczby działań rzędu (n + l)² (mnożenie przez e^tXj uważamy za jedno działanie). Istnieje jednak algorytm bardziej oszczędny: FFT (Fast Fourier Transform - Szybkie Przekształcenie Fouriera).

FFT FAST FOURIER TRANSFORM -SZYBKIE PRZEKSZTAŁCENIE FOURIERA

Algorytm FFT przedstawimy w szczególnym przypadku, gdy liczba węzłów interpolacji spełnia równość N = n+1 = 2^r, dla pewnego całkowitego r. Zajmiemy się przypadkiem analizy fourierowskiej, czyli wyliczeniem wartości współczynnika fourierowskiego, to jest wyrażenia

< = ^ £

j=0

gdzie N = n + 1 = 2^r dla pewnego całkowitego r, i dla ustalonego q spośród ę = 0,1,2, • • •, A — 1. Przypadek syntezy fourierowskiej nie różni się od analizy w sposób istotny.

Pomysł polega na tym, żeby nie wykonywać zbędnych obliczeń: w tym wypadku żeby nie wykonywać mnożeń przez 1.

Przeanalizujemy dokładnie wzór dla współczynnika c_q. Zapiszemy najpierw q i j w systemie binarnym:

q = £    = _gi2° + ?₂2¹ + • • ■ + q_T2^r~\

k= 1

19