第3章快速傅里叶变换3.1引言3.2直接计算DFT的问题及改进的途径二者的差别只在于WN的指数符号不同，以及差一个常数乘因子1/N，所以IDFT与DFT具有相同的运算工作量。下面我们只讨论DFT的运算量。一般来说，x(n)和WNnk都是复数，X(k)也是复数，因此每计算一个X(k)值，需要N次复数乘法和N-1次复数加法。而X(k)一共有N个点（k从0取到N-1），所以完成整个DFT运算总共需要N2次复数乘法及N(N-1)次复数加法。在这些运算中乘法运算要比加法运算复杂，需要的运算时间也多一些。因为复数运算实际上是由实数运算来完成的，这时DFT运算式可写成（3-3）当然，上述统计与实际需要的运算次数稍有出入，因为某些WNnk可能是1或j，就不必相乘了，例如W0N=1，WNＮ／２=-1，WNN/4=-j等就不需乘法。但是为了便于和其他运算方法作比较，一般都不考虑这些特殊情况，而是把WNnk都看成复数，当N很大时，这种特例的影响很小。从上面的统计可以看到，直接计算DFT，乘法次数和加法次数都是和N2成正比的，当N很大时，运算量是很可观的，有时是无法忍受的。例3-1根据式（3-1），对一幅N×N点的二维图像进行DFT变换，如用每秒可做10万次复数乘法的计算机，当N=1024时，问需要多少时间（不考虑加法运算时间）？解直接计算DFT所需复乘次数为（N2)2≈1012次，因此用每秒可做10万次复数乘法的计算机，则需要近3000小时。这对实时性很强的信号处理来说，要么提高计算速度，而这样，对计算速度的要求太高了。另外，只能通过改进对DFT的计算方法，以大大减少运算次数。3.2.2改善途径能否减少运算量，从而缩短计算时间呢？仔细观察DFT的运算就可看出，利用系数WＮnk的以下固有特性，就可减少运算量：（1）WNnk的对称性（3）WNnk的可约性3.3按时间抽取（DIT）的基-2FFT算法则可将DFT化为式中，X1(k)与X2(k)分别是x1(r)及x2(r)的N/2点DFT：这样可得到再考虑到WkN的以下性质:图3-1时间抽取法蝶形运算流图符号图3-2按时间抽取将一个N点DFT分解为两个N/2点DFT（N=8）一个N点DFT分解为两个N/2点DFT，每一个N/2点DFT只需(N/2)2=N2/4次复数乘法，N/2(N/2-1)次复数加法。两个N/2点DFT共需2×(N/2)2=N2/2次复数乘法和N(N/2-1)次复数加法。此外，把两个N/2点DFT合成为N点DFT时，有N/2个蝶形运算，还需要N/2次复数乘法及2×N/2=N次复数加法。因而通过第一步分解后，总共需要(N2/2)+(N/2)=N(N+1)/2≈N2/2次复数乘法和N(N/2-1)+N=N2/2次复数加法。由此可见，通过这样分解后运算工作量差不多节省了一半。既然这样分解是有效的，由于N=2M，因而N/2仍是偶数，可以进一步把每个N/2点子序列再按其奇偶部分分解为两个N/4点的子序列。（3-13）且图3-3N/2点DFT分解为两个N/4点DFTX2(k)也可进行同样的分解：图3-4一个N=8点DFT分解为四个N/4点DFT根据上面同样的分析知道，利用四个N/4点的DFT及两级蝶形组合运算来计算N点DFT，比只用一次分解蝶形组合方式的计算量又减少了大约一半。最后，剩下的是2点DFT，对于此例N=8，就是四个N/4=2点DFT，其输出为X3(k)，X4(k)，X5(k)，X6(k)，k=0,1，这由式（3-14）～式（3-17）四个式子可以计算出来。例如，由式（3-14）可得：这种方法的每一步分解，都是按输入序列在时间上的次序是属于偶数还是属于奇数来分解为两个更短的子序列，所以称为“按时间抽取法”。3.3.2按时间抽取的FFT算法与直接计算DFT运算量的比较由按时间抽取法FFT的流图可见，当N=2M时，共有M级蝶形，每级都由N/2个蝶形运算组成，每个蝶形需要一次复乘、二次复加，因而每级运算都需N/2次复乘和N次复加，这样M级运算总共需要实际计算量与这个数字稍有不同，因为W0N=1，ＷNN/2=-1，ＷNN/2=-j，这几个系数都不用乘法运算，但是这些情况在直接计算DFT中也是存在的。此外，当N较大时，这些特例相对而言就很少。所以，为了统一作比较起见，下面都不考虑这些特例。由于计算机上乘法运算所需的时间比加法运算所需的时间多得多，故以乘法为例，直接DFT复数乘法次数是N2，FFT复数乘法次数是(N/2)lbN。直接计算DFT与FFT算法的计算量之比为例3-2用FFT算法处理一幅N×N点的二维图像，如用每秒可做10万次复数乘法的计算机，当N=1024时，问需要多少时间（不考虑加法运算时间）？解当N=1024点时，FFT算法处理一幅二维图像所需复数乘法