《数字信号处理》 第4章.pptVIP

\ 4.3.2 DIF-FFT算法特点及与DIT-FFT算法的异同 按频率抽取法的运算特点与按时间抽取法基本相同，它们是两种等价的FFT运算。整个DIF-FFT运算流图也全是由蝶形运算构成，每一个蝶形运算单元完成的迭代运算为 ,式中L表示第L级迭代，1≤L≤M，k和j表示数据所在的行数。所对应的蝶形运算单元: 不同点： DIF-FFT算法与DIT-FFT算法的蝶形运算单元不同，差别是乘旋转因子 的位置不同。DIF-FFT算法的蝶形运算是先加（减）后相乘，而DIT-FFT算法的蝶形运算是先乘后加（减）。 DIF-FFT算法的输入是自然顺序，而输出是倒位序的, 运算完毕后，要通过变址运算将倒位序转换为自然顺序，然后再输出。 DIT-FFT算法的输入是倒位序的，而输出是自然顺序, 序列输入后，要先进行变址运算将倒位序转换为自然顺序，然后再做碟形运算。 相同点：采用原位计算；N=2M时，共有M级运算，每级共有N/2个蝶形，整个计算是通过MN/2个蝶形运算完成的， DIT与DIF算法的运算次数相同， 复数乘法 次， 复数加法 次。 都有N/2个不同的旋转因子。 4.3.3 按频率抽取法与按时间抽取法运算流图的关系 这两个流图的形式如同是颠倒了信号的传输方向，其关系可谓是“互为转置”。利用信号流图的转置定理，可以导出其相应的转置流图的。 信号流图的转置定理:如果将原信号流图（网络）中的所有支路方向倒转或反向，保持各支路传输系数（增益）不变，并将输入和输出相互交换，则其相应网络的系统函数H(z)不改变。 对于N=2M，按频率抽取的FFT算法与按时间抽取的FFT算法都有M级蝶形运算，每一级都由N/2个蝶形运算组成，因此，把每一种按时间抽取的FFT运算流图按转置定理加以转置都可以得到相应的按频率抽取的FFT运算流图，反之亦然。 将右图 图 就可得到 下图 加以转置 按频率抽取，输入倒位序、输出自然顺序的FFT运算流图（N=8） 4.4 离散傅里叶反变换（IDFT）的快速计算方法 上面讨论的FFT算法，同样可以适用于离散傅里叶反变换（IDFT）运算，即快速傅里叶反变换，简称为IFFT。 比较IDFT与DFT的公式： 可以看出，只要把DFT运算中的每一个旋转因子 换成 ，最后再乘以常数1/N，则以上所有按时间抽取或按频率抽取的FFT算法都可以用来计算IDFT。 用FFT流图实现IDFT快速算法 将DIT-FFT或DIF-FFT蝶形运算流图中旋转因子WNp改为WN-p 在IDFT快速算法的最后结果输出前，乘以1/N常数；如要防止溢出，可在每一级运算中，输出支路分别乘以1/2，实现系数分级分担。 在IDFT快速算法中，输入序列为X(k)，而输出序列为x(n)。 流图对应关系： DIT-FFT对应DIF-IFFT DIF-FFT对应DIT-IFFT DIT-IFFT运算流图（N=8） 直接利用FFT程序来计算IFFT的方法: 由于DFT与IDFT公式结构的对称性，对IDFT公式取共轭可得 因此 实现方法： 先将X(k)取共轭，得到X*(k)； 再直接调用FFT程序计算DFT[X*(k)]的值； 最后将计算结果取一次共轭，并乘以1/N，即得到x(n)值。 这一方法虽然多用了两次对N点序列取共轭的操作，程序实现容易，也不会明显增加运算量。但是，FFT与IFFT运算可以共用一个子程序，实现方便。 4.5 N为复合数的FFT算法 若不满足基-2 FFT算法(N=2M) ，则可采用下面的几种办法： 1. 将x(n)补一些零值点，使N增长到最邻近的一个2M数值。由DFT的性质知道，有限长序列补零之后，并不影响其频谱 ，只不过是使其频谱的采样点数增加而已，但是，有时计算量增加太多，会造成很大的浪费。因此人们希望找到N≠2M时的FFT算法。 2. 如果要求准确的N点DFT，而N又是素数，则只能采用直接DFT方法，或者用后面将要介绍的线性调频变换（Chirp-变换）算法。 3. 若N是一个复合数，即它可以分解成一些因子的乘积，则可以