主题
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 变换

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 中被引用

快速傅里叶变换

请引用为

魏斯stein，埃里克·W. "快速傅里叶变换。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/FastFourierTransform.html

主题分类