主題
Search

快速傅立葉變換

快速傅立葉變換 (FFT) 是一種離散傅立葉變換 演算法，它減少了計算 N 個點所需的計算次數，從 2N^2 減少到 2NlgN，其中 lg 是以 2 為底的對數。

FFT 最初由 Cooley 和 Tukey (1965) 討論，儘管高斯實際上早在 1805 年就描述了關鍵的因子分解步驟 (Bergland 1969, Strang 1993)。 如果點數 N 是 2 的冪，則可以使用 FFT 透過 Danielson-Lanczos 引理 計算離散傅立葉變換。 如果點數 N 不是 2 的冪，則可以對與 N 的質因數相對應的點集執行變換，但速度會略有降低。 高效的實傅立葉變換演算法或快速 Hartley 變換 (Bracewell 1999) 可以將速度進一步提高大約兩倍。 以 4 為基數和以 8 為基數的快速傅立葉變換使用最佳化的程式碼，並且可能比以 2 為基數的快速傅立葉變換快 20-30%。 當因子很大時，質因子分解速度很慢，但使用 Winograd 變換 演算法，可以使 N=2、3、4、5、7、8、11、13 和 16 的離散傅立葉變換變得快速 (Press et al. 1992, pp. 412-413, Arndt)。

快速傅立葉變換演算法通常分為兩類：按時間抽取和按頻率抽取。 Cooley-Tukey FFT 演算法 首先以位逆序重新排列輸入元素，然後構建輸出變換（按時間抽取）。 基本思想是使用以下恆等式將長度為 N 的變換分解為兩個長度為 N/2 的變換

sum_(n=0)^(N-1)a_ne^(-2piink/N)=sum_(n=0)^(N/2-1)a_(2n)e^(-2pii(2n)k/N) +sum_(n=0)^(N/2-1)a_(2n+1)e^(-2pii(2n+1)k/N) =sum_(n=0)^(N/2-1)a_n^(even)e^(-2piink/(N/2)) +e^(-2piik/N)sum_(n=0)^(N/2-1)a_n^(odd)e^(-2piink/(N/2)),

有時稱為 Danielson-Lanczos 引理。 視覺化此過程的最簡單方法或許是透過傅立葉矩陣。

Sande-Tukey 演算法 (Stoer and Bulirsch 1980) 首先進行變換，然後重新排列輸出值（按頻率抽取）。

另請參閱

混疊, Danielson-Lanczos 引理, 離散傅立葉變換, 傅立葉矩陣, 傅立葉變換, 分數傅立葉變換, Hartley 變換, 洩漏, 數論變換, Winograd 變換

使用 探索

參考文獻

Arndt, J. "FFT Code and Related Stuff." http://www.jjj.de/fxt/.Bell Laboratories. "Netlib FFTPack." http://netlib.bell-labs.com/netlib/fftpack/.Bergland, G. D. "A Guided Tour of the Fast Fourier Transform." IEEE Spectrum 6, 41-52, July 1969.Blahut, R. E. Fast Algorithms for Digital Signal Processing. New York: Addison-Wesley, 1984.Bracewell, R. The Fourier Transform and Its Applications, 3rd ed. New York: McGraw-Hill, 1999.Brigham, E. O. The Fast Fourier Transform and Applications. Englewood Cliffs, NJ: Prentice Hall, 1988.Chu, E. and George, A. Inside the FFT Black Box: Serial and Parallel Fast Fourier Transform Algorithms. Boca Raton, FL: CRC Press, 2000.Cooley, J. W. and Tukey, O. W. "An Algorithm for the Machine Calculation of Complex Fourier Series." Math. Comput. 19, 297-301, 1965.Crandall, R.; Jones, E.; Klivington, J.; and Kramer, D. "Gigaelement FFTs on Apple G5 Clusters." 27 Aug 04. http://images.apple.com/acg/pdf/20040827_GigaFFT.pdf.Duhamel, P. and Vetterli, M. "Fast Fourier Transforms: A Tutorial Review." Signal Processing 19, 259-299, 1990.Lipson, J. D. Elements of Algebra and Algebraic Computing. Reading, MA: Addison-Wesley, 1981.Nussbaumer, H. J. Fast Fourier Transform and Convolution Algorithms, 2nd ed. New York: Springer-Verlag, 1982.Papoulis, A. The Fourier Integral and its Applications. New York: McGraw-Hill, 1962.Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. "Fast Fourier Transform." Ch. 12 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 490-529, 1992.Ramirez, R. W. The FFT: Fundamentals and Concepts. Englewood Cliffs, NJ: Prentice-Hall, 1985.Stoer, J. and Bulirsch, R. Introduction to Numerical Analysis. New York: Springer-Verlag, 1980.Strang, G. "Wavelet Transforms Versus Fourier Transforms." Bull. Amer. Math. Soc. 28, 288-305, 1993.Van Loan, C. Computational Frameworks for the Fast Fourier Transform. Philadelphia, PA: SIAM, 1992.Walker, J. S. Fast Fourier Transform, 2nd ed. Boca Raton, FL: CRC Press, 1996.

在 中被引用

快速傅立葉變換

請引用為

魏斯stein，埃裡克·W. "快速傅立葉變換。" 來自 —— 資源。 https://mathworld.tw/FastFourierTransform.html

主題分類