数字信号处理4人文科技ppt课件

《数字信号处理4人文科技ppt课件》由会员分享，可在线阅读，更多相关《数字信号处理4人文科技ppt课件（115页珍藏版）》请在金锄头文库上搜索。

1、第4章 FFT 4.1 引言 4.1.1 离散傅里叶变换的矩阵表示及其运算量 DFT在数字信号处理中起着非常重要的作用， 这是与DFT存在着高效算法， 即快速傅里叶变换(FFT) 分不开的。快速运算的关键是减少运算量。,离散傅里叶变换对为： (4.1) (4.2) 式中 。 下面要用矩阵来表示DFT关系。令：,并令TN、 表示两个变换方阵，有：,如果用i (0iN-1)表示这两个N阶方阵的行号，用j(0jN-1)表示这两个N阶方阵的列号，那末很容易看出，TN 方阵中i行j列的元素为 ，而方阵中i行j列的元素为 。 于是（4.1）式可以写成： 而（4.2）式可以写成：,一般情况下，信号序列x(n

2、) 及其频谱序列X(k) 都是用复数来表示的，WN当然也是复数。因此，计算DFT的一个值X(k) 需要进行N次复数乘法（与1相乘也包括在内）和N-1次复数加法；所以，直接计算N点的DFT需要进行N2 次复数乘法和N(N-1) 复数加法。,显然，直接计算N点的IDFT所需的复乘和复加的次数也是这么多。当N足够大时，N2 N(N-1), 因此，DFT与IDFT的运算次数与N2 成正比，随着N的增加，运算量将急剧增加，而在实际问题中，N往往是较大的，因此有必要对DFT与IDFT的计算方法予以改进。,4.1.2 因子的特性 DFT和IDFT的快速算法的导出主要是根据 因子的特性。 1周期性： 对离散变

3、量n有同样的周期性。,2对称性： 或 3. 其它:,4.2 基2时间抽选的FFT算法 4.2.1 算法推导 已经知道： 令DFT的长度N=2M，M为正整数。,令： 于是有：,其中， 是由x(n)的偶数抽样点形成的DFT；而,是由x(n)的奇数抽样点形成的DFT。但是这两个式子并不完全是N/2点的DFT，因为k的范围仍然是由0到N-1，因此，还应该进一步考虑k由N/2到N-1范围的情况。,现在令 ，故对于后半段有： 同理： 又知：,图 4.1 N点DFT分解为两个N/2点的DFT (N=8),图 4.2 N/2 点的DFT 分解为两个N/4点的DFT (N=8),综上所述，可以得到： 其中G(k

4、)、P(k) 分别是x(n)的偶数点和奇数点的N/2点DFT。,这样，我们就将一个N点的DFT分解成了两个N/2点的DFT，由于DFT的运算量与其点数的平方成正比，因此使运算量减少了。但是，还应该将每一个N/2点的DFT再分解为两个N/4点的DFT，如此下去，直到分解为2点的DFT为止，总共需要进行log2N-1=log2(N/2)次分解。,图 4.3 2 点 DFT 信号流图（蝶形图）,对于2点DFT，有： 所以2点DFT的运算只需一次加法和一次减法，这样的运算叫做蝶形运算，这样的信号流图叫做蝶形图。,该算法每次分解都是将时域序列按奇偶分为两组，因此要求N等于2的正整数幂，故将这种FFT算法

5、叫做基2时间抽选法。,4.2.2 算法特点 1. 倒序重排 这种FFT算法的每次分解都是将输入序列按照奇偶分为两组，故要不断地将每组输入数据按奇偶重排，直到最后分解为2点的DFT，输入数据才不再改变顺序。这样做的结果，使得作FFT运算时，输入序列的次序要按其序号的倒序进行重新排列。,现在将图4.4中输入序号以及重排后的序号按二进制写出如下（注：下标“2”表示二进制数）。可以看出，将输入序号的二进制表示（n2n1n0）位置颠倒，得到（n0n1n2），就是相应的倒序的二进制序号。因此，输入序列按倒序重排，实际上就是将序号为（n2n1n0）的元素与序号为（n0n1n2）的元素的位置相互交换。,2.

6、同址计算 从图4.4可以看出，整个算法流图可以分为四段，（0）段为倒序重排，后面3段为3(log28=3)次迭代运算：首先计算2点DFT，然后将2点DFT的结果组合成4点DFT，最后将4点DFT组合为8点DFT。因此，对于N点FFT，只需要一列存储N个复数的存储器。,开始时，输入序列的N个数放于此N个存储器内，倒序重排后仍存于这N个存储器中，每一次迭代运算后的结果也仍然存于这N个存储器中，整个运算完成后，这N个存储器中即为所求的频谱序列X(k) （k = 0、1、.、 N-1）。这就是所谓的同址计算，这样可以大大节约存储元件。,3. 运算量 观察图4.4可知，图4.3所示的蝶形图实际上代表了F

7、FT的基本运算，它实际上只包含了两次复数加法运算。一个N(N=2M) 点的FFT，需要进行M=log2N次迭代运算。每次迭代运算包含了N/2个蝶型，因此共有N次复数加法；此外，除了第一次的2点DFT之外，每次迭代还包括了N/2次复数乘法（即乘WN的幂）。因此，一个N点的FFT共有复数乘法的次数为：,复数加法的次数为： 因此，FFT算法比直接计算DFT大大减少了运算量，尤其是当N较大时，计算量的减少更为显著。比如，当N=1024时，采用FFT算法时复数乘法的次数，不超过直接计算DFT时复乘次数的千分之五。,4.2.3 关于FFT算法的计算机程序 在一般情况下，进行FFT运算的序列至少都有几百点的

8、长度，因此需要编制FFT算法程序以便能够利用计算机来快速进行计算。可以参照图4.4来编制计算N (N必须等于2的正整数幂)点FFT的计算机程序，整个程序可以分为两部分：一部分是倒序重排，另一部分是用三层嵌套的循环来完成M=log2N次迭代。,三层循环的功能是：最里的一层循环完成蝶形运算，中间的一层循环完成因子WNk的变化，而最外的一层循环则是完成M次迭代过程。 倒序重排的程序是一段经典程序，它以巧妙的构思、简单的语句用高级编程语言来完成了倒序重排的功能。下面是一段用FORTRAN语言编写的倒序重排程序。,N=2*M （表示N=2M ，M是输入的正整数） NV2=N/2 （NV2是一个整数变量）

9、 NM1=N-1 （NM1也是一个整数变量） J=1 （对变量J赋初值） 100 DO 7 I=1,NM1 (循环开始，到语句7结束； 循环变量I从1开始，到NM1结束，步长为1),IF (I.GE.J) GOTO 5 （如果IJ，就转移到语句5） （将输入序列中序号互为倒序 的两个数值交换位置）,5 K=NV2 6 IF(K.GE.J) GOTO 7 (如果KJ，就转移到语句 7) J=J-k K=K/2 GOTO 6 （转移到语句6） 7 J=J+K ,由于是同址计算，因此程序中只用了一个数组X( )，这个数组共有N个元素。X( )既表示输入序列，也表示按倒序重排后的这N个数值。程序中的字

10、母都是大写的，这是FORTRAN语句的特点。,I既是循环变量，也代表输入序列的正序序号，J代表倒置后的序号。由于FORTRAN语言的循环变量不能从0开始，故以8点FFT为例，I的范围为18，下面是正序序号I与倒序序号J之间的对应关系： I: 1 2 3 4 5 6 7 8 J: 1 5 3 7 2 6 4 8,输入序列按倒序重排，实际上就是将X(I)和X(J)互换位置。显然，如果I=J，就不需要交换；而如果IJ，就表示X(I)与X(J)已经交换过了。因此，在循环语句下面的语句“IF (I.GE.J) GOTO 5”就表明了交换的条件：只有当IJ时才执行下面三条语句，使X(I)与X(J)互换位置

11、。,正序序号I也是循环变量，从1开始，每次循环增加1。关键问题是对于每一个I，所对应的J是什么？程序中从语句5开始直到循环结束就是为下一次循环确定所对应的J的。虽然I-1和J-1的二进制表示是互为倒序的关系，但是，程序中并不是由I得到J，而是由上一个J来得到下一个J。思路是：I-1由0到7，用二进制来表示就是从0002开始，每次在最低位加1，逐次增加到1112 。,既然J-1的二进制表示是I-1二进制表示的倒置，那末J-1的变化就应该是在最高位逐次加1，而最高位的二进制数1表示N/2。所以，程序中将J与N/2比较来判断J-1的最高位是0还是1，如果是0，就执行J+K=J+N/2，也就是将J-1

12、的二进制最高位由0变为1。如果J-1的最高位是1，应该将它变为0，也就是将J减去N/2，然后考察次高位是0还是1，这应该用N/4来考察，于是执行“K=K/2”。如此下去，直到得到下一个J，完成此次循环。,4.3 基2频率抽选的FFT算法 时间抽选法是在时域内将输入序列x(n)逐次分解为偶数点子序列和奇数点子序列，通过求子序列的DFT而实现整个序列的DFT。而频率抽选法则是在频域内将X(k)逐次分解成偶数点子序列和奇数点子序列，然后对这些分解得越来越短的子序列进行DFT运算，从而求得整个的DFT。当然，同样要求N为2的正整数幂。,设 ，则可以分别表示出k为偶数和奇数时的X(k)。 其中，,其中，

13、 显然，X(2r) 为g(n) 的N/2点DFT，X(2r+1) 为p(n)WNn 的N/2点DFT。这样，一个N点的DFT分解为两个N/2点的DFT。将分解继续下去，直到分解为2点的DFT为止。当N=8时，基2频率抽选的FFT算法的整个信号流图如图4.6所示。,将图4.6与图4.4比较，可知频率抽选法的计算量与时间抽选法相同，而且都能够同址计算。时间抽选法是输入序列按奇偶分组，故x(n)的顺序要按倒序重排，而输出序列按前后分半，故X(k) 的顺序不需要重排；频率抽选法则是输出序列按奇偶分组，故X(k) 的顺序要按倒序重排，而输入序列按前后分半，故x(n) 不需要重排。,4.4 基 4时间抽选

14、的FFT算法 上面讨论的FFT算法都要求N=2M ，M是正整数，因此是基2的FFT算法。若N=4M ，则还可以采用基4的FFT算法。与推导基2 FFT算法类似，可以推导基4 FFT算法。 将x(n) 相间地分为四组，所得的X(k) 按前后分为四组。第一次分组的流图如图4.7所示。其中，中间的矩阵为变换方阵T4，,而 Di (i = 0,1,2,3) 则为N/4 阶的对角矩阵，即：,即变换方阵，即：,图 4.7 基 4 时间抽选的 FFT算法的第一次分解,为了理解基4 FFT算法，可以将基2时间抽选的FFT算法的第一次分解与基4的第一次分解进行比较。,基2的情形第一次分解为两组，基4为四组。基2

15、分解中的G(k) 和P(k) 分别为x(n)的偶数点和奇数点的N/2点DFT，而基4分解的每一项中的因子,都代表一个N/4点的DFT，x(n) 的间隔为4。基2中的前后两项用T2矩阵来连接；而在基4的情形为4项，是用T4矩阵来连接的。基2中的第二项的N/2点的DFT之前要乘上因子WNk；而基4的情况每个N/4点的DFT之前则要乘上对角矩阵Di，其对角线上的元素为WNki。因此，基4的FFT分解既与基2 FFT的分解相对应，又比之复杂。,基4的情形也要继续分解下去，直到分解为四点DFT为止，共要经过log4N-1= log4(N/4) 次分解。估算基4 FFT的计算量：一个N点的FFT，要经过log4N次变换。复数乘法体现在与对角矩阵D1、D2、D3相乘，总的复乘次数为： ；总的复加次数为： 。,基2 FFT算法的复乘次数为： 复加次数为：,将Mc4与Mc2比较，Ac4和Ac2比较，可知，基4的复乘次数约减少了1/4，但复加次数却增加了。因此，在乘法运算要转化为加法运算来实现的情况下，基4算法的计算量会比基2算法少；但是，近年来，在许多微处理器和DSP中，实现一次乘法运算与实现一次加法运算的时间完全相同，这时采用基4算法就不合算了，而且基4算法还比基2算法复杂。,4.5 快速傅里叶反变换（IFFT） IFFT是IDFT的快