Szybka transformacja Fouriera (FFT)

<<< Powrót do strony głównej przedmiotu Metody numeryczne

Algorytm FFT (Fast Fourier Transform) dla dyskretnej transformacji Fouriera (DFT, Discrete Fourier Transform) i jego krewniacy dla wyznaczania dyskretnej transformacji cosinusów (DCT, Discrete Cosine Transform i MDCT, Modified Discrete Cosine Transform), choć dotyczą pozornie dość abstrakcyjnych zadań, zrewolucjonizowały wiele dziedzin życia. Między innymi wykorzystuje się je w

kompresji obrazów w formacie JPEG (DCT)
kompresji dźwięku w formacie MP3 i pokrewnych (MDCT)
rozwiązywaniu ważnych równań różniczkowych cząstkowych (DFT)

a także do

filtrowania szumów (DFT)
szybkiego mnożenia wielomianów (DFT)

W niniejszym wykładzie ograniczymy się do przedstawienia szybkiego algorytmu rozwiązywania zadania DFT. Algorytmy rozwiązywania zadań pokrewnych (DCT, MDCT, itp.) opierają się na podobnych zasadach.

Zacznijmy od postawienia zadania obliczeniowego DFT. Jest ono (pozornie!) banalne i jednocześnie wydumane:

Dla danego zestawu $\displaystyle N$ liczb $\displaystyle f_{\alpha }\in C$ , $\displaystyle \alpha =0,\ldots ,N-1$ , wyznaczyć $\displaystyle N$ wartości

\displaystyle c_{j}=\sum _{\alpha =0}^{N-1}f_{\alpha }\omega _{N}^{j\alpha },

dla $\displaystyle j=0,\ldots ,N-1$ , przy czym $\displaystyle \omega _{N}=\exp(-i{\frac {2\Pi }{N}})$ . Jak pamiętamy, jednostka urojona $\displaystyle i$ spełnia $\displaystyle i={\sqrt {-1}}$ . Taką operację nazywamy dyskretną transformacją Fouriera, DFT.

Jean Baptiste Joseph Fourier
Zobacz biografię

Ponieważ dane $\displaystyle f$ są wektorem $\displaystyle f=[f_{0},\ldots ,f_{N-1}]^{T}$ , wynik $\displaystyle c$ też jest wektorem, a zadanie jest liniowe, możemy wszystko zapisać macierzowo:

\displaystyle c=F_{N}f,

gdzie

\displaystyle F_{N}=(\omega _{N}^{j\alpha })_{j,\alpha =0,\ldots ,N-1}={\begin{pmatrix}1&1&1&\cdots &1\\1&\omega _{N}&\omega _{N}^{2}&\cdots &\omega _{N}^{N-1}\\1&\omega _{N}^{2}&\omega _{N}^{4}&\cdots &\omega _{N}^{2(N-1)}\\&&&\cdots &\\1&\omega _{N}^{N-1}&\omega _{N}^{2(N_{1})}&\cdots &\omega _{N}^{(N-1)^{2}}\end{pmatrix}}.

Tak więc, gdyby naiwnie podejść do zadania, moglibyśmy je rozwiązać brutalnie, tworząc na początek macierz $\displaystyle F_{N}$ , a następnie wyznaczając iloczyn macierzy przez wektor, co łatwo zrobić kosztem $\displaystyle O(N^{2})$ operacji. Dlatego istotne jest, że algorytm FFT, który za chwilę omówimy, będzie działać kosztem $\displaystyle O(N\log \,N)$ , czyli praktycznie liniowym (w obu przypadkach stałe proporcjonalności są niewielkie) w dodatku będzie miał znacznie mniejsze wymagania pamięciowe.

Algorytm FFT

Aby móc taniej mnożyć przez $\displaystyle F_{N}$ , musimy odkryć kilka bardzo szczególnych własności tej macierzy.

Fakt

Macierz $\displaystyle F$ jest symetryczna oraz $\displaystyle {\frac {1}{N}}F_{N}^{*}F_{N}=I$ .

Dowód

Dowód pozostawiamy jako ćwiczenie.

Zauważmy, że nasza macierz ma jeszcze więcej specjalnej struktury, powtarza się w niej bardzo wiele takich samych współczynników (sprawdź dla $\displaystyle N=4$ , w ogólności $\displaystyle F_{N}$ ma tylko $\displaystyle N$ różnych wyrazów), gdyż $\displaystyle \omega _{N}^{N}=1$ (dla $\displaystyle j=0,\ldots ,N-1$ , $\displaystyle \omega _{N}^{j}$ to nic innego jak kolejne zespolone pierwiastki z jedynki).

W wyprowadzeniu algorytmu szybkiej transformacji Fouriera (Fast Fourier Transform, FFT) oprzemy się po raz kolejny na regule "dziel i rządź". Dla uproszczenia analizy przyjmiemy, że $\displaystyle N$ jest naturalną potęgą dwójki, w szczególności $\displaystyle N=2m$ dla pewnego naturalnego $\displaystyle m$ .

Rzeczywiście, rozbijając naszą sumę na sumę po indeksach parzystych i sumę po indeksach nieparzystych, mamy

\displaystyle {\begin{aligned}c_{j}&=f_{0}\omega _{N}^{0\cdot j}+f_{2}\omega _{N}^{2\cdot j}+\ldots +f_{N-2}\omega _{N}^{(N-2)\cdot j}\\&&+f_{1}\omega _{N}^{1\cdot j}+f_{3}\omega _{N}^{3\cdot j}+\ldots +f_{N-1}\omega _{N}^{(N-1)\cdot j}.\end{aligned}}

Suma po indeksach parzystych da się zapisać w postaci

\displaystyle \sum _{k=0}^{m-1}f_{2k}(\omega _{m})^{jk}

i analogicznie suma po indeksach nieparzystych da się zapisać

\displaystyle \omega _{N}^{j}\cdot \sum _{k=0}^{m-1}f_{2k+1}(\omega _{m})^{jk}

gdyż $\displaystyle \omega _{N}^{2}=\omega _{m}$ , a więc wygląda na to, że nasze zadanie wyznaczenia dyskretnej transformacji Fouriera wymiaru $\displaystyle N$ da się sprowadzić do analogicznych zadań mniejszego rozmiaru.

Rzeczywiście, korzystając z tego, że $\displaystyle j=\beta m+{\widetilde {j}}$ , gdzie $\displaystyle {\widetilde {j}}=0,\ldots ,m-1$ , oraz $\displaystyle \beta =0$ lub $\displaystyle 1$ , mamy $\displaystyle \omega _{m}^{j}=\omega _{m}^{\widetilde {j}}$ .

Oznaczając

\displaystyle {\begin{aligned}\Phi _{\widetilde {j}}&=\sum _{k=0}^{m-1}f_{2k}\omega _{m}^{{\widetilde {j}}k},\qquad {\widetilde {j}}=0,\ldots ,m-1,\\\Psi _{\widetilde {j}}&=\sum _{k=0}^{m-1}f_{2k+1}\omega _{m}^{{\widetilde {j}}k},\end{aligned}}

(jak widać są to DFT dla dwa razy krótszych wektorów, złożonych z tylko parzystych lub tylko nieparzystych współrzędnych Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \displaystyle f} ), dostajemy ostatecznie

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \displaystyle \begin{align} c_{\widetilde{j}} = \Phi_{\widetilde{j}} + \omega_N^{\widetilde{j}} \Psi_{\widetilde{j}},\\ c_{\widetilde{j}+m} = \Phi_{\widetilde{j}} - \omega_N^{\widetilde{j}} \Psi_{\widetilde{j}}. \end{align}}

Tym samym, wyznaczenie DFT wymiaru Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \displaystyle N} udało się rzeczywiście sprowadzić do wyznaczenia dwóch DFT wymiaru Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \displaystyle m = N/2} oraz drobnej manipulacji na ich wynikach zgodnie z powyższym wzorem. Oczywiście, te mniejsze transformacje można wyznaczyć takim samym sposobem, co prowadzi do zależności rekurencyjnej, która kończy się na wektorach długości 1, na których DFT to po prostu identyczność.

Proste sprawdzenie pokazuje, że koszt takiego algorytmu jest rzędu Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \displaystyle O(N\log\,N)} , a nie Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \displaystyle O(N^2)} , jak dla naiwnego algorytmu mnożenia wektora przez gęstą macierz. Zysk jest więc, nawet dla niewielkich Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \displaystyle N} , istotny.

Algorytm Prosta wersja algorytmu FFT

function y = fft(x)
	N = length(f);
	if N == 1 
		y = f;
	else
		<math>\displaystyle \omega</math> = <math>\displaystyle \exp(-\frac{2\Pi}{N}i)</math>;
		<math>\displaystyle \omega_k</math> = <math>\displaystyle \omega^{N/2-1}</math>;
		
		u = fft( f[0:2:N-2] );
		v = fft( f[1:2:N-1] );
		
		v = v * <math>\displaystyle \omega_k</math>;
		
		y = [ u+v ; u-v ];
	end
end

Jak już zdążyliśmy się przyzwyczaić, gdy tylko to możliwe, w algorytmach numerycznych unikamy stosowania jawnej rekurencji. W przypadku FFT można jej również uniknąć, wyznaczając zawczasu --- korzystając z tzw. odwrócenia bitów --- porządek, w którym należy składać 1-wymiarowe DFT w coraz dłuższe wektory zgodnie ze wzorem powyżej tak, by na końcu dostać pożądany wektor Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \displaystyle c = F_Nf} .

Ponadto, istnieją warianty algorytmu FFT, które np. działają na danych rzeczywistych. Na analogicznych zasadach co FFT oparte są również algorytmy wykonujące tzw. dyskretną transformację cosinusów (DCT) i jej wariant MDCT stosowany w kodekach audio takich jak MP3, AAC, czy OggVorbis.

Interpolacja trygonometryczna

Jednym z wielu zadań, w których daje się zastosować algorytm FFT, jest zadanie interpolacji trygonometrycznej:

Dla danych węzłów Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \displaystyle x_k = \frac{2\pi k }{N}} , Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \displaystyle k = 0,\ldots,N-1} , znaleźć wielomian $\displaystyle P$ (zmiennej rzeczywistej, o wartościach zespolonych) stopnia $\displaystyle \leq N-1$ postaci

\displaystyle P(x)=\sum _{k=0}^{N-1}\beta _{k}{\bar {\omega }}^{k},

gdzie $\displaystyle {\bar {\omega }}=e^{ix}=\cos(x)+i\,\sin(x)$ (stąd nazwa: trygonometryczny) taki, że

\displaystyle P(x_{k})=y_{k},\qquad k=0,\ldots ,N-1,

dla zadanych wartości $\displaystyle y_{k}$ .

W języku macierzy DFT możemy zapisać zadanie interpolacji trygonometrycznej jako zadanie wyznaczania wektora $\displaystyle \beta$ takiego, że

\displaystyle {\overline {F_{N}}}\beta =y

dla zadanego wektora $\displaystyle y$ .

Twierdzenie O współczynnikach wielomianu interpolacji trygonometrycznej

Współczynniki $\displaystyle \beta =[\beta _{0},\ldots ,\beta _{N-1}]^{T}$ poszukiwanego wielomianu trygonometrycznego wyrażają się wzorem

\displaystyle \beta ={\frac {1}{N}}F_{N}y.

Dowód

Jak wiemy, $\displaystyle {\frac {1}{N}}F_{N}^{*}F_{N}=I$ , z symetrii macierzy $\displaystyle F_{N}$ wynika więc, że $\displaystyle ({\overline {F_{N}}})^{-1}={\frac {1}{N}}F_{N}$ .

Można pokazać, że gdy dane są rzeczywiste, zadanie interpolacji trygonometrycznej możemy wyrazić korzystając wyłącznie z liczb rzeczywistych. Jeśli $\displaystyle y_{k}\in R$ , $\displaystyle k=0,\ldots ,N-1$ , to wtedy (rzeczywisty) wielomian trygonometryczny

\displaystyle p(x)=\sum _{k=0}^{N-1}\left(a_{k}\cos({\frac {2k\pi }{N}}x)-b_{k}\sin({\frac {2k\pi }{N}}x)\right),

gdzie $\displaystyle a_{k}=Re(\beta _{k})$ , $\displaystyle b_{k}=Im(\beta _{k})$ , interpoluje $\displaystyle y_{k}$ w węzłach $\displaystyle x_{k}$ . Oczywiście, powyższa formuła w rzeczywistości ma o połowę mniej wyrazów, ze względu na własności funkcji trygonometrycznych.

Splot

W niektórych zastosowaniach potrzebne jest wyznaczenie splotu dwóch wektorów, to znaczy wyznaczenie wyrażeń postaci

\displaystyle z_{k}=\sum _{j=0}^{N-1}u_{j}v_{k-j},\qquad k=0,\ldots ,N-1.

(przyjmujemy tu konwencję, że wektory rozszerzamy $N$ -periodyczne tak, że z definicji $v_{j+kN}=v_{j}$ dla dowolnych całkowitych $j,k$ ).

Zapisując to macierzowo, szukamy iloczynu wektora $\displaystyle u$ z cykliczną macierzą Toeplitza (macierz Toeplitza ma stałe wyrazy wzdłuż diagonali) wyznaczoną przez $\displaystyle v$ ,

\displaystyle z={\begin{pmatrix}v_{0}&v_{1}&\cdots &v_{N-1}\\v_{N-1}&v_{0}&\cdots &v_{N-2}\\\vdots &\ddots &\ddots &\vdots \\v_{1}&\cdots &v_{N-1}&v_{0}\end{pmatrix}}\cdot {\begin{pmatrix}u_{0}\\u_{1}\\\vdots \\u_{N-1}\end{pmatrix}}.

Mogłoby się zdawać, że zadanie wyznaczenia splotu powinno kosztować tyle, co mnożenie macierzy przez wektor, a więc $\displaystyle O(N^{2})$ operacji. Tymczasem prosty rachunek pozwala sprawdzić, że odpowiednie transformacje Fouriera, $\displaystyle {\hat {z}}=F_{N}z$ , $\displaystyle {\hat {u}}=F_{N}u$ , $\displaystyle {\hat {v}}=F_{N}v$ spełniają równanie z macierzą diagonalną!

\displaystyle {\hat {z}}=N\cdot {\begin{pmatrix}{\hat {v}}_{0}&&\\&\ddots &\\&&{\hat {v}}_{N-1}\end{pmatrix}}\cdot {\hat {u}}=N\cdot {\begin{pmatrix}{\hat {v}}_{0}{\hat {u}}_{0}\\\vdots \\{\hat {v}}_{N-1}{\hat {u}}_{N-1}\end{pmatrix}},

a to mnożenie daje się wykonać kosztem liniowym, tym samym całe zadanie daje się policzyć kosztem $\displaystyle O(N\log \,N)$ .

Biblioteki

Najpopularniejszą obecnie biblioteką implementującą algorytm FFT dla DFT, DCT i innych pokrewnych (bez ograniczenia, że wymiar jest naturalną potęgą dwójki), jest biblioteka o niezbyt skromnie brzmiącej nazwie FFTW (The Fastest Fourier Transform in the West). Z tej biblioteki korzystają m.in. funkcje MATLABa i Octave'a fft oraz ifft dla transformacji DFT (to znaczy mnożenia przez $\displaystyle F_{N}$ ) i, odpowiednio, transformacji odwrotnej, $\displaystyle {\frac {1}{N}}{\overline {F}}_{N}$ .

FFTW jest napisana w C i w dużym stopniu wykorzystuje możliwości współczesnych procesorów, takie jak potokowanie i instrukcje wektorowe SSE2 i SSE3. Poniżej pokazujemy przykładowy prościutki kod w C realizujący DFT na pojedynczym wektorze zespolonym.

/* Kompilacja:
	gcc -o dft dft.c -lfftw3 -lm */
#include <complex.h> /* rozszerzenie GCC dające operacje na typach zespolonych */
#include <fftw3.h>
#include <math.h>
#define N 8

int main(void)
{
fftw_complex *F, *C;
fftw_plan Plan;
double normfactor = 1.0/N;
int i;

F = fftw_malloc( N * sizeof(fftw_complex) );
C = fftw_malloc( N * sizeof(fftw_complex) );

for( i = 0; i < N; i++ ) /* inicjalizacja wartości tablicy F */
{
	F[i] = i*M_PI*(1-0.5*I); 
}

Plan = fftw_plan_dft_1d( N, F, C, FFTW_FORWARD, FFTW_ESTIMATE );

fftw_execute( Plan );

for( i = 0; i < N; i++ ) /* normalizacja wyznaczonego C */
	C[i] *= normfactor; 

for( i = 0; i < N; i++ )
{
	printf("F[%d] = %8.3lf + %8.3lfi | C[%d] = %8.3lf + %8.3lfi\n", 
	i, creal(F[i]), cimag(F[i]), i, creal(C[i]), cimag(C[i])); 
}

/* .... teraz moglibyśmy zmienić wartości F i ponownie wyznaczyć C,
korzystając z tego samego Planu! */

/* sprzątamy */

fftw_destroy_plan( Plan );
fftw_free( F ); 
fftw_free( C ); 

return(0);
}

Zwrócmy uwagę na linię Plan=fftw_plan_dft_1d(...). To tutaj dokonywane są ustalenia, w jakiej kolejności mają być prowadzone obliczenia. Jest to operacja dość kosztowna, dlatego jeśli mamy wyznaczyć wiele takich samych DFT, ale na różnych danych $\displaystyle f$ , należy przed pierwszą DFT taki plan zachować, a potem, aplikując DFT dla następnych danych, wykorzystać gotowy.

Literatura

W celu dogłębnego zapoznania się z omawianym na wykładzie materiałem, przeczytaj rozdział 6.12--6.13 w

D. Kincaid, W. Cheney Analiza numeryczna, Wydawnictwa Naukowo-Techniczne, Warszawa 2006, ISBN 83-204-3078-X.

MN10

Spis treści

Szybka transformacja Fouriera (FFT)

Algorytm FFT

Interpolacja trygonometryczna

Splot

Biblioteki

Literatura

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia