数字信号处理05.docVIP

第五章 快速傅立叶算法 DFT与卷积运算是信号处理中两个最基本、最常用的运算，而实际上两者可以相互转化，不但卷积可以化为DFT处理，相关、滤波、谱分析都可以化为DFT来实现。 对于N点序列x (n)，其DFT变换对定义为： 其中，，因此，求N点X(k)需要N2次复数乘法，N(N-1)次复数加法，而实现一次复数乘法需要4次实数乘法和2次实数加法，而实现一次复数加法，则需要两次实数加法。当N较大时，计算量相当可观。如N=1024，则需要1048576次复数乘法，也就是4194304次实数乘法，因此这种变换在时间和操作上是极不现实的，尤其在遇到2D图象处理时，计算量实在大得惊人。 ； 但考察W矩阵，可以看出，DFT运算中其实包含了大量的重复计算，虽然其中有N2个元素，但其中只有N个是独立的。即：；且这N个值也有一定对称关系，这种周期性和对称性可以描述为： 如，对4点DFT，按公式直接计算需42=16次复数乘法，按上述周期性和对称性，可得：； 将该矩阵第二列和第三列交换，得：； 由此得：； 这样，求四点DFT实际上只需要一次复数乘法即可。问题的关键是如何利用W因子的周期性和对称性，导出一种高效的快速算法。 1965年J.W.Cooley和J.W.Tukey提出了快速傅立叶变换算法（FAST FOURIER TRANSFORM，FFT），使N点DFT乘法计算量由N2次下降为(Nlog2N)/2次，仍以N=1024为例，计算量降为5120次，仅为原来的4.88%，这一发现在数字信号处理领域具有里程碑式的意义，并且带动了其它新算法的不断涌现，使数字信号处理广泛应用于众多的技术领域。 近三十多年来，快速傅立叶变换的发展主要有两个方向：一类是针对N等于2的整数次幂的算法，如基2算法、基4算法、实因子算法、分裂基算法等，可以证明前面提到的四点DFT可以不用乘法，而只用加法来实现，因此基4算法比基2算法更有效。1984提出的分裂基（split-radix）算法同时使用基2和基4算法，是目前对N等于2的整数次幂的各类算法中最为理想的一种。另一类是N不等于2得整数次幂的算法，它以Winograd（WFTA）算法为代表，是建立在下标映射和数论的基础上的一套全新的算法，WFTA算法基于中国剩余定理，素因子算法基于素数定理，其运算速度比分裂基算法还要快，但理论复杂、编程困难、数据长度也受到较大限制，且在程序运行中，数据所占内存和数据传递次数比Cooley-Tukey增加了很多，因此在技术实现上是否真的具有突出的优越性，值得怀疑，因此，在我们的课程里，对WFTA不做讨论。 §5.1基2FFT算法 1．时间抽取（DIT）基2FFT算法 （1）算法的推导 对于（2-5-1）： 令N=2M，M为正整数，如果将x (n)按奇偶分成两组，即令n=2r，n=2r+1，r=0，1，…，N/2-1，于是）： 其中：； 令， 则：； A(k)，B(k)都是N/2点的DFT，X(k)是N点DFT，因此单用上式表示X(k)是不完全的，但：； 这样用A(k)，B(k)可完整地表示X(k)。当N=8时，A(k)，B(k)和X(k)关系如图： A(k)，B(k)仍是高复合数（N/2）的DFT，我们按照上述方法继续给以分解，令r=2l，r=2l+1，l=0，1，…，N/4-1，则A(k)和B(k)可分别表示为： ； 令：； 那么：； 同理，令： ； 那么：； 若N=8，这时C(k)，D(k)，E(k)，F(k)都是二点的DFT，无需再分，即： C(0)=x(0)+x(4)，E(0)=x(1)+x(5)， C(1)=x(0)-x(4)，E(1)=x(1)-x(5)， D(0)=x(2)+x(6)，F(0)=x(3)+x(7)，D(1)=x(2)-x(6)，F(1)=x(3)-x(7)； 若N=16，32，或2的更高次幂，可按这样的方法继续分下去，直到两点的DFT为止。 在以上算法中将时间下标n按奇偶分开，故称为时间抽取算法（Decimation in Time，DIT），计算过程可表述如下图： 基本运算单元如图所示： 2、算法的讨论 下面我们对上面的推导过程进行讨论，来找出FFT算法的一般性的规律。 （一）“级”的概念 上述过程中，将N点DFT先分成两个N/2点的DFT，再是4个N/4点DFT，进而八个N/8点DFT，直到N/2个两点DFT。每分一次，称为一“级”运算。因为M=log2N，所以，N点DFT可分成M级，如图，图中从左至右，依次为m=0级，m=1级，…，m=M-1级。 （二）蝶形单元 在算法的信号流图中存在大量几何形状像蝴蝶的运算结构，称为蝶形运算单元，在第m级有：； p，q是参与该蝶形单元运算的上、下节点的序号。很明显，第m级序号为p，q的两个点只参与该蝶形单元的运算，