快速的傅立叶变换 The Fast Fourier Transform

快速的傅立叶变换
快速的傅立叶变换(FFT)是要计算离散傅立叶变换(DFT)和它的逆变换的一种高效率的算法。FFTs对于各种各样的从数字的到整数的快速倍增算法加工和解决偏微分方程信号的应用是极端重要的。这篇文章描述许多算法，使我们可以了解离散傅立叶变换的作用与应用。
设x0，…，xN1是一段复杂数组。DFT由惯例定义为：
   
计算这些数的总和将直接地采取O(N2)算法操作。FFT是要计算仅在O(NlogN)操作情况下得到的同一个结果的算法。一般来说，这种算法取决于N的取值，同样,与O(N log N)对应的复杂FFTs算法，也取决于N的取值。
许多FFT算法只取决于是第n个样本并可以近似的在所有有限变换领域中运用，例如数字理论变换。
因为DFT逆变换与DFT十分相似，但是不同之处在于DFT的逆变换取决于1/N的取值，所有FFT算法可能被它很容易地运用。

The Fast Fourier Transform
A fast Fourier transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. FFTs are of great importance to a wide variety of applications, from digital signal processing and solving partial differential equations to algorithms for quick multiplication of large integers. This article describes the algorithms, of which there are many, see discrete Fourier transform for properties and applications of the transform.
Let x0, ...., xN-1 be complex numbers. The DFT is defined by the formula
   
Evaluating these sums directly would take O(N2) arithmetical operations. An FFT is an algorithm to compute the same result in only O(N log N) operations. In general, such algorithms depend upon the factorization of N, but (contrary to popular misconception) there are FFTs with O(N log N) complexity for all N, even for prime N.
Many FFT algorithms only depend on the fact that is an Nth primitive root of unity, and thus can be applied to analogous transforms over any finite field, such as number-theoretic transforms.

13000字