Brza furijeova transformacija

**Brza Furijeova transformacija** (; č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 O(\log(n) ) u vremenu.

## Formalan opis Kuli-Tuki algoritma

Prisetimo se definicije diskretne Furijeove transformacije:
:\hat c_k = \sum_{j=0}^{N-1} e^{-2\pi \mathrm{i}\cdot\frac{jk}{N}}\cdot c_j za k=0,\dots,N-1
gde je c = (c_0, \dots, c_{N-1}) vektor koji želimo da transformišemo, a \hat c taj vektor Furije transformisan.

Definišimo N' = N* = \frac{N}{2}</math>.

Potom definišemo vektor sa parnim indeksima:
:<math>c'_0 = c_0, c'_1 = c_2, \dots, c'_{N'-1} = c_{N-2}</math>

i označimo njegovu DFT kao:
:<math>\hat c'_0, \hat c'_1, \dots,\hat c'_{N'-1}</math>

te vektor sa neparnim indeksima:
:<math>c*_0 = c_1, c*_2 = c_3, \dots, c*_{N*-1} = c_{N-1}</math>

i njegovu DFT:
:<math>\hat c*_0, \hat c*_1, \dots, \hat c*_{N*-1}</math>

Sledi spajanje:
:<math>

\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 \ge n'
\end{cases}

\end{matrix}

Napomena: N' = N* = \frac{N}{2}</math>, ali se radi lakšeg razumevanja navodi različito!

Često smo u praksi zainteresovani za konkretne frekvencije. Uvodimo notaciju:
:<math>\omega_n:=2\pi\frac{n}{NT}, n=1-K,..., N-K</math>, <math>K</math> je negde u blizini <math>\frac{N}{2}</math>, a <math>T</math> perioda našeg merenja.

Onda je brza furijeova transformacija za određenu frekvenciju:
:<math>\hat c(\omega_k) = \begin{cases} 
\hat c'(\omega_k) + e ^ {-\mathrm{i} \omega_k T }\cdot \hat c*(\omega_k) & \mbox{kada } k 

## Literatura

* 
* 
* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, 2001. *Introduction to Algorithms*, 2nd. ed. MIT Press and McGraw-Hill. . Especially chapter 30, "Polynomials and the FFT."
* 
* P. Duhamel and M. Vetterli, 1990, , *Signal Processing* **19**: 259–299.
* A. Edelman, P. McCorquodale, and S. Toledo, 1999, , *SIAM J. Sci. Computing* **20**: 1094–1114.
* D. F. Elliott, & K. R. Rao, 1982, *Fast transforms: Algorithms, analyses, applications*. New York: Academic Press.
* Funda Ergün, 1995, , *Proc. 27th ACM Symposium on the Theory of Computing*: 407–416.
* M. Frigo and S. G. Johnson, 2005, "The Design and Implementation of FFTW3," *Proceedings of the IEEE* **93**: 216–231.
* Carl Friedrich Gauss, 1866. "Nachlass: Theoria interpolationis methodo nova tractata," *Werke* band **3**, 265–327. Göttingen: Königliche Gesellschaft der Wissenschaften.
* W. M. Gentleman and G. Sande, 1966, "Fast Fourier transforms—for fun and profit," *Proc. AFIPS* **29**: 563–578. 
* H. Guo and C. S. Burrus, 1996, , *Proc. SPIE Intl. Soc. Opt. Eng.* **2825**: 250–259.
* H. Guo, G. A. Sitton, C. S. Burrus, 1994, , *Proc. IEEE Conf. Acoust. Speech and Sig. Processing (ICASSP)* **3**: 445–448.
* Steve Haynal and Heidi Haynal, "Generating and Searching Families of FFT Algorithms ", *Journal on Satisfiability, Boolean Modeling and Computation* vol. 7, pp. 145-187 (2011).
* 
* 
* S. G. Johnson and M. Frigo, 2007. "A modified split-radix FFT with fewer arithmetic operations," *IEEE Trans. Signal Processing* **55** (1): 111–119.
* T. Lundy and J. Van Buskirk, 2007. "A new matrix approach to real FFTs and convolutions of length 2k," *Computing* **80** (1): 23-45.
* Kent, Ray D. and Read, Charles (2002). *Acoustic Analysis of Speech*. . Cites Strang, G. (1994)/May–June). Wavelets. *American Scientist, 82,* 250-255.
* 
* 
* 
* V. Pan, 1986, , *Information Proc. Lett.* **22**: 11-14.
* Christos H. Papadimitriou, 1979, , *J. ACM* **26**: 95-102.
* D. Potts, G. Steidl, and M. Tasche, 2001. "Fast Fourier transforms for nonequispaced data: A tutorial", in: J.J. Benedetto and P. Ferreira (Eds.), *Modern Sampling Theory: Mathematics and Applications* (Birkhauser).
* 
* 
* James C. Schatzman, 1996, Accuracy of the discrete Fourier transform and the fast Fourier transform, *SIAM J. Sci. Comput.* **17**: 1150–1166.
* 
* 
* 
*