关于快速傅里叶变换介绍

[拼音]：kuaisu Fuliye bianhuan

[外文]：fast Fourier transformation

简称FFT，是指进行“有限离散傅里叶变换”(简称DFT)的快速算法。一维DFT是把N元数组A(0)，A(1)，…，A(N-1)按线性关系式

(1)

变为N元数组x(0)，x(1)，…，x(N-1)的一种线性变换，其中记号W是一个复常数，满足=1，其值为

传统算法是直接计算(1)，大约需要N2次运算(这里所说的运算每一次包含一个复数乘法和一个复数加法)。1965年，美国人库利和图基提出的FFT算法把运算次数缩减为Nlog2N。因此，FFT算法比传统算法提高工效约为N/log2N倍。当N很大时，这是巨量的提高。例如，在图像处理问题中，一个图像分为10000×10000个点，因而对所进行的DFT来说，应有N=108，于是用FFT算法提高工效约为1016/(108log2108)3750000倍。如用每秒能作一千万次运算的电子计算机进行计算，按FFT算法，几百秒即可完成，若按传统算法要几十年才能算完。

总的来说是利用复常数W 的性质把关系式(1)的各项重新组合为新的算式，并使用递推的步骤，以缩减运算次数。以N=2n为例，设j1是j 除以时的余数，新的算式是

即先行计算两个元数组Y(j1)和Z(j1)，然后再用2n个乘法和2n个加法算出2n元数组x(j)。类似地，可把元数组的计算化为两个元数组的计算，等等，如此递推，最后把计算M元数组的运算次数记为T(M)，按上述计算步骤有关系式:，·，由此可得。如果N不是2n的形式，而是有分解式 ，则可建立运算次数不超过的FFT算法。

上述算法同样可应用于逆DFT，即从N 元数组x(0)，x(1)，…，x(N-1)按线性关系式变换为数组A(0)，A(1)，…，A(N-1)。FFT算法在数值计算中的一个重要应用是计算卷积，即从N元数组A(0)，A(1)，…，A(N-1)及具有周期N的数组B(0)，B(1)，…，B(N-1)(B(-1)=B(N-1)，B(-2)=B(N-2)，…)按关系式

计算N元数组C(0)，C(1)，…，C(N-1)。采用如下步骤:首先把两个数组A(k)和B(k)用FFT算法分别得数组X(j)和Y(j)，其次作数组（只需N个乘法）

Z(j)=X(j)·Y(j) (j=0，1，…，N-1)，最后用FFT算法把数组Z(j)作逆DFT，得卷积C(0)，C(1)，…，C(N-1)。上述算法的运算次数约为3Nlog2N，而传统算法则是N 2。除用于计算卷积外，FFT算法还可用作计算两个多项式的乘积等等。

FFT算法在实际问题中已广泛应用，在光谱、声谱、地震谱分析、晶体结构分析、滤波、数字信号处理、图像信息处理、物探、天线、雷达、卫星摄影分析、全息图，以及医疗卫生上的心电图、脑电图、X光相片强化等等方面，已大量应用，很有发展前途。

近年来，FFT算法本身不断增添新的内容。在一维DFT的算法方面有:“素因子”法、不要调换排列顺序法、修剪法、N为素数的算法、余弦变换算法、一维DFT的二维处理方法、基底3-FFT的新算法、维诺格拉特算法(这是DFT算法的一个重要进展)以及雷德-布莱纳算法等；二维DFT的算法除以一维FFT为基础的算法外，也建立了若干直接对二维数组进行运算（分解和变换）的算法。

如上所述，计算卷积要做三次 FFT，这在N很大时的计算量仍然很大。此外，还存在由于舍入误差而不能得到高精度的卷积以及要贮存三角函数以保证有关的计算需要等缺点。以上缺点为70年代发展起来的快速数论变换算法所克服。设M是大于 1的正整数，表示从0到M-1的非负整数全体，使用同余概念，即 α呏b(modM)表示两整数α与b的差α-b是M的倍数。设α是中任一数，N是使呏1(modM)成立的最小正整数，称 α 为中的N 次本原单位根。中的数组A(0)，A(1)，…，A(N-1)按线性同余关系式

变为中的数组x(0)，x(1)，…，x(N-1)，称为数论变换。在一定的条件下，可以把FFT算法平行地移植到上以进行NTT，称为快速数论变换。仿照上述利用FFT算法计算卷积的步骤，同样可用快速数论变换来计算卷积。它具有速度更快，没有舍入误差和不需要贮存三角函数或其他基础函数等优点。但变换本身没有物理意义。

1979年出现了把维诺格拉特算法和数论变换相结合的计算DFT的新混合算法，进一步缩减了乘法次数。

参考书目

1. 游兆永著：《线性代数与多项式的快速算法》，上海科学技术出版社，上海，1980。
2. 孙琦、郑德勋、沈仲琦著：《快速数论变换》，科学出版社，北京，1980。