Brza furijeova transformacija

Brza Furijeova transformacija (engl. Fast Fourier transformation; često se označava kao FFT) je algoritam za „brzo“ izračunavanje vrednosti diskretne Furijeove transformacije. Ubrzanje u odnosu na uobičajen postupak izračunavanja diskretne Furijeove transformacije postiže se izbegavanjem ponovnog izračunavanja izraza koji se međusobno negiraju. Algoritam se pripisuje Džejmsu V. Kuliju (James W. Cooley) i Džonu V. Tukiju (John W. Tukey) koji su ga objavili 1965. godine. Međutim, Karl Fridrih Gaus ga je razvio već 1805. da bi izračunao putanju asteroida Palas i Juno. Pritom su mnoge verzije razvijene i pre Kulijeve i Tukijeve varijante. Posle su se pojavila mnoga poboljšanja i varijacije.

Za brzu Furijeovu transformaciju postoji i algoritam u suprotnom smeru - inverzna brza Furijeova transformacija.

Neformalan opis Kuli-Tuki algoritma

Kuli-Tuki algoritam se bazira na ideji podeli-pa-vladaj (divide-and-conquer, eng.). Preduslov za njegovo izvršavanje je da broj tačaka (tačke izmerene za neki signal, na primer) na kojima se vrši transformacija bude stepen dvojke. Kako često možemo sami da izaberemo koliko tačaka hoćemo da uzmemo, ovo i ne predstavlja veliku prepreku.

DFT izračunavamo tako što naše tačke (vektor) prvo podelimo na dva vektora, jedan koji odgovara komponentama izvornog vektora sa parnim indeksima, a drugi sa neparnim. Onda izračunamo DFT oba vektora i spojimo rezultate. Pritom koristimo osobine jediničnog korena Furijeove matrice. Posle ponavljamo rekurzivno postupak. Time možemo da DFT na kraju izračunamo prema složenosti ${\displaystyle O(\log(n))}$ u vremenu.

Formalan opis Kuli-Tuki algoritma

Prisetimo se definicije diskretne Furijeove transformacije:

${\displaystyle {\hat {c}}_{k}=\sum _{j=0}^{N-1}e^{-2\pi \mathrm {i} \cdot {\frac {jk}{N}}}\cdot c_{j}}$ za ${\displaystyle k=0,\dots ,N-1}$

gde je ${\displaystyle c=(c_{0},\dots ,c_{N-1})}$ vektor koji želimo da transformišemo, a ${\displaystyle {\hat {c}}}$ taj vektor Furije transformisan.

Definišimo ${\displaystyle N'=N''={\frac {N}{2}}}$.

Potom definišemo vektor sa parnim indeksima:

${\displaystyle c'_{0}=c_{0},c'_{1}=c_{2},\dots ,c'_{N'-1}=c_{N-2}}$

i označimo njegovu DFT kao:

${\displaystyle {\hat {c}}'_{0},{\hat {c}}'_{1},\dots ,{\hat {c}}'_{N'-1}}$

te vektor sa neparnim indeksima:

${\displaystyle c''_{0}=c_{1},c''_{2}=c_{3},\dots ,c''_{N''-1}=c_{N-1}}$

i njegovu DFT:

${\displaystyle {\hat {c}}''_{0},{\hat {c}}''_{1},\dots ,{\hat {c}}''_{N''-1}}$

Sledi spajanje:

${\displaystyle {\begin{matrix}{\hat {c}}_{k}&=&\sum _{j=0}^{N-1}e^{-2\pi \mathrm {i} \cdot {\frac {jk}{N}}}\cdot c_{j}\qquad \ \ \qquad \ \ \ \ \qquad \ \ \ \ \qquad \ \ \ \ \qquad \ \ \ \\\\&=&\sum _{j=0}^{N-1}e^{-2\pi \mathrm {i} {\frac {(2j)k}{N}}}\cdot c_{2j}+\sum _{j=0}^{{\frac {N}{2}}-1}e^{-2\pi \mathrm {i} {\frac {(2j+1)k}{N}}}\cdot c_{2j+1}\\\\&=&\sum _{j=0}^{N'-1}e^{-2\pi \mathrm {i} \cdot {\frac {jk}{N'}}}\cdot c'_{j}+\sum _{j=0}^{N''-1}e^{-2\pi \mathrm {i} \cdot {\frac {jk}{N''}}}\cdot c''_{j}\\\\&=&{\begin{cases}{\hat {c}}'_{k}+e^{-2\pi \mathrm {i} {\frac {k}{N}}}\cdot {\hat {c}}''_{k}&{\mbox{kada }}k<n'\\{\hat {c}}'_{k-N'}-e^{-2\pi \mathrm {i} {\frac {k-N''}{N}}}\cdot {\hat {c}}''_{k-N''}&{\mbox{kada }}k\geq n'\end{cases}}\end{matrix}}}$

Napomena: ${\displaystyle N'=N''={\frac {N}{2}}}$, ali se radi lakšeg razumevanja navodi različito!

Često smo u praksi zainteresovani za konkretne frekvencije. Uvodimo notaciju:

${\displaystyle \omega _{n}:=2\pi {\frac {n}{NT}},n=1-K,...,N-K}$, ${\displaystyle K}$ je negde u blizini ${\displaystyle {\frac {N}{2}}}$, a ${\displaystyle T}$ perioda našeg merenja.

Onda je brza furijeova transformacija za određenu frekvenciju:

${\displaystyle {\hat {c}}(\omega _{k})={\begin{cases}{\hat {c}}'(\omega _{k})+e^{-\mathrm {i} \omega _{k}T}\cdot {\hat {c}}''(\omega _{k})&{\mbox{kada }}k<0\\{\hat {c}}'(\omega _{-k})-e^{-\mathrm {i} \omega _{k}(1-{\frac {NT}{2}})}\cdot {\hat {c}}''(\omega _{-k})&{\mbox{kada }}k\geq 0\end{cases}}}$

Literatura