Брза Фуријеова трансформација

Брза Фуријеова трансформација (енгл. Fast Fourier transformation; често се означава као FFT) је алгоритам за „брзо“ израчунавање вредности дискретне Фуријеове трансформације. Убрзање у односу на уобичајен поступак израчунавања дискретне Фуријеове трансформације постиже се избегавањем поновног израчунавања израза који се међусобно негирају. Алгоритам се приписује Џејмсу В. Кулију (James W. Cooley) и Џону В. Тукију (John W. Tukey) који су га објавили 1965. године. Међутим, Карл Фридрих Гаус га је развио већ 1805. да би израчунао путању астероида Палас и Јуно. Притом су многе верзије развијене и пре Кулијеве и Тукијеве варијанте. После су се појавила многа побољшања и варијације.

За брзу Фуријеову трансформацију постоји и алгоритам у супротном смеру - инверзна брза Фуријеова трансформација.

Неформалан опис Кули-Туки алгоритма

Кули-Туки алгоритам се базира на идеји подели-па-владај (divide-and-conquer, енг.). Предуслов за његово извршавање је да број тачака (тачке измерене за неки сигнал, на пример) на којима се врши трансформација буде степен двојке. Како често можемо сами да изаберемо колико тачака хоћемо да узмемо, ово и не представља велику препреку.

ДФТ израчунавамо тако што наше тачке (вектор) прво поделимо на два вектора, један који одговара компонентама изворног вектора са парним индексима, а други са непарним. Онда израчунамо ДФТ оба вектора и спојимо резултате. Притом користимо особине јединичног корена Фуријеове матрице. После понављамо рекурзивно поступак. Тиме можемо да ДФТ на крају израчунамо према сложености $O(n\log(n))$ у времену.

Формалан опис Кули-Туки алгоритма

Присетимо се дефиниције дискретне Фуријеове трансформације:

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

где је $c=(c_{0},\dots ,c_{N-1})$ вектор који желимо да трансформишемо, а ${\hat {c}}$ тај вектор Фурије трансформисан.

Дефинишимо $N'=N''={\frac {N}{2}}$.

Потом дефинишемо вектор са парним индексима:

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

и означимо његову ДФТ као:

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

те вектор са непарним индексима:

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

и његову ДФТ:

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

Следи спајање:

${\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}}$

Напомена: $N'=N''={\frac {N}{2}}$, али се ради лакшег разумевања наводи различито!

Често смо у пракси заинтересовани за конкретне фреквенције. Уводимо нотацију:

$\omega _{n}:=2\pi {\frac {n}{NT}},n=1-K,...,N-K$, $K$ је негде у близини ${\frac {N}{2}}$, а $T$ периода нашег мерења.

Онда је брза фуријеова трансформација за одређену фреквенцију:

${\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}}$

Литература

• Brenner, N.; C. Rader (1976). „A New Principle for Fast Fourier Transformation”. IEEE Acoustics, Speech & Signal Processing. 24 (3): 264—266. doi:10.1109/TASSP.1976.1162805. 
• Cooley James W.; Tukey, John W. (1965). „An algorithm for the machine calculation of complex Fourier series”. Math. Comput. 19 (90): 297—301. doi:10.1090/S0025-5718-1965-0178586-1. 
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, 2001. Introduction to Algorithms, 2nd. ed. MIT Press and McGraw-Hill. . ISBN 978-0-262-03293-3.  . Especially chapter 30, "Polynomials and the FFT."
• Duhamel, Pierre (1990). „Algorithms meeting the lower bounds on the multiplicative complexity of length-$2^{n}$ DFTs and their connection with practical algorithms”. IEEE Trans. Acoust. Speech. Sig. Proc. 38 (9): 1504—151. doi:10.1109/29.60070. 
• Duhamel, P.; Vetterli, M. (1990). „Fast Fourier transforms: a tutorial review and a state of the art”. Signal Processing. 19 (4): 259—299. doi:10.1016/0165-1684(90)90158-U. 
• Edelman, Alan; McCorquodale, Peter; Toledo, Sivan (1998). „The Future Fast Fourier Transform?”. SIAM Journal on Scientific Computing. 20 (3): 1094—1114. doi:10.1137/S1064827597316266. 
• D. F. Elliott, & K. R. Rao, 1982, Fast transforms: Algorithms, analyses, applications. New York: Academic Press.
• Funda Ergün, 1995, „Testing multivariate linear functions: Overcoming the generator bottleneck”. doi:10.1145/225058.225167. , 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.
• Gentleman, W. M.; Sande, G. (1966). „Fast Fourier Transforms”. Proceedings of the November 7-10, 1966, fall joint computer conference on XX - AFIPS '66 (Fall). стр. 563. S2CID 207170956. doi:10.1145/1464291.1464352. 
• Guo, Haitao; Burrus, C. Sidney (1996). Unser, Michael A.; Aldroubi, Akram; Laine, Andrew F., ур. „Fast approximate Fourier transform via wavelets transform”. Wavelet Applications in Signal and Image Processing IV. 2825: 250—259. S2CID 120514955. doi:10.1117/12.255236. 
• Guo, H.; Sitton, G.A.; Burrus, C.S. (1994). „The Quick Discrete Fourier Transform”. Proceedings of ICASSP '94. IEEE International Conference on Acoustics, Speech and Signal Processing. стр. III/445—III/448. ISBN 0-7803-1775-0. S2CID 42639206. doi:10.1109/ICASSP.1994.389994. 
• 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).
• T, Heideman M.; Johnson, D. H.; C. S. Burrus (1984). „Gauss and the history of the fast Fourier transform”. IEEE ASSP Magazine. 1 (4): 14—21. S2CID 10032502. doi:10.1109/MASSP.1984.1162257. 
• Heideman, Michael T.; Burrus, C. Sidney (1986). „On the number of multiplications necessary to compute a length-$2^{n}$ DFT”. IEEE Trans. Acoust. Speech. Sig. Proc. 34 (1): 91—95. doi:10.1109/TASSP.1986.1164785. 
• Johnson, Steven G.; Frigo, Matteo (2007). „A Modified Split-Radix FFT with Fewer Arithmetic Operations” (PDF). IEEE Transactions on Signal Processing. 55 (1): 111—119. S2CID 14772428. doi:10.1109/TSP.2006.882087. 
• Lundy, T.; Van Buskirk, J. (2007). „A new matrix approach to real FFTS and convolutions of length 2^k”. Computing. 80 (1): 23—45. S2CID 27296044. doi:10.1007/s00607-007-0222-6. .
• Kent, Ray D. and Read, Charles (2002). Acoustic Analysis of Speech. ISBN 978-0-7693-0112-9. CS1 одржавање: Вишеструка имена: списак аутора (веза). Cites Strang, G. (1994)/May–June). Wavelets. American Scientist, 82, 250-255.}-
• Morgenstern, Jacques (1973). „Note on a lower bound of the linear complexity of the fast Fourier transform”. J. ACM. 20 (2): 305—306. S2CID 2790142. doi:10.1145/321752.321761. 
• M. J. Mohlenkamp (1999). „A fast transform for spherical harmonics” (PDF). J. Fourier Anal. Appl. 5 (2–3): 159—184. S2CID 119482349. doi:10.1007/BF01261607. Архивирано из оригинала (PDF) 06. 02. 2007. г. Приступљено 25. 03. 2012. 
• H. J.Nussbaumer (1977). „Digital filtering using polynomial transforms”. Electronics Lett. 13 (13): 386—387. doi:10.1049/el:19770280. 
• V. Pan, 1986, Pan, Victor Ya. (1986). „The trade-off between the additive complexity and the asyncronicity of linear and bilinear algorithms”. Information Processing Letters. 22: 11—14. doi:10.1016/0020-0190(86)90035-9. , Information Proc. Lett. 22: 11-14.
• Christos H. Papadimitriou, 1979, Papadimitriou, Christos H. (1979). „Optimality of the fast Fourier transform”. Journal of the ACM. 26: 95—102. S2CID 850634. doi:10.1145/322108.322118. , 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).
• Press WH, Teukolsky SA, Vetterling WT, Flannery BP (2007). „Chapter 12. Fast Fourier Transform”. Numerical Recipes: The Art of Scientific Computing (3rd изд.). New York: Cambridge University Press. ISBN 978-0-521-88068-8. Архивирано из оригинала 11. 08. 2011. г. Приступљено 25. 03. 2012. 
• Rokhlin, Vladimir; Tygert, Mark (2006). „Fast algorithms for spherical harmonic expansions”. SIAM J. Sci. Computing. 27 (6): 1903—1928. doi:10.1137/050623073. 
• James C. Schatzman, 1996, Accuracy of the discrete Fourier transform and the fast Fourier transform, SIAM J. Sci. Comput. 17: 1150–1166.
• Shentov, O. V.; S. K. Mitra; Heute, U.; Hossen, A. N. (1995). „Subband DFT. I. Definition, interpretations and extensions”. Signal Processing. 41 (3): 261—277. doi:10.1016/0165-1684(94)00103-7. 
• Sorensen, H. V.; D. L. Jones; Heideman, M. T.; C. S. Burrus (1987). „Real-valued fast Fourier transform algorithms”. IEEE Trans. Acoust. Speech Sig. Processing. 35 (6): 849—863. doi:10.1109/TASSP.1987.1165220. 
• Welch, Peter D. (1969). „A fixed-point fast Fourier transform error analysis”. IEEE Trans. Audio Electroacoustics. 17 (2): 151—157. doi:10.1109/TAU.1969.1162035. 
• Winograd, S. (1978). „On computing the discrete Fourier transform”. Math. Computation. 32 (141): 175—199. JSTOR 2006266. S2CID 120055730. doi:10.1090/S0025-5718-1978-0468306-4.