第四章快速傅里叶变换(FFT)2..ppt

4.3 IDFT的快速算法 IDFT的计算公式重写如下： 可以看到，除了常数 和 外，IDFT 和DFT是完全一样的，因此，只要将FFT算法 中的旋转因子（W因子）改为共轭，所有支路 乘以 ，就得到了一种IDFT的快速算法。 由于 ，可以将 分配到M级中 的每一个蝶形的输出支路上，如图所示，这种 算法的好处是在一 定程度上可以防止算法运算 过程中发生溢出。 如果希望直接调用FFT模块来计算 IDFT，可以采用如下第二种方法： 这种算法是先将输入的 取共轭，然 后直接调用FFT算法，对结果再取共轭，最 后乘以1/N，结果就是 。 4.4 基4-FFT算法 除了基2-FFT算法外，基4-FFT算法也是 应用非常广泛的FFT算法。类似于基2算法， 基4算法要求的点数 ，序列DFT的计算 最终分解成N/4个4点序列的DFT计算，4点序 列的DFT实际上也没有乘法。  首先，将序列按下标分为4组： 4r,4r+1,4r+2,4r+3,r=0,1,2,…，N/4-1,分别记 为 所以 将分成4部分： 和 ， ，利用 的周 期为N/4，可得 可以看到，N点 的计算可以分成四部 分，分别由四个N/4点序列的DFT线性组合而 得。每一个N/4点序列的DFT实际上不需要求 解，仍可以按照此思路继续分解，直到分为N/4 个4点序列，4点序列的DFT可以直接计算，不 需要乘法运算。 根据以上算法的原理，可以画出一个N=8 的基4-FFT算法流图，如图4-5所示。 4.5 实序列的FFT算法 在实际中，数据一般都是实序列，而FFT 算法一般针对复序列，直接处理实序列时，是 将序列的虚部看成零，将会浪费很多运算时间 和存储空间，因此设计了专门用于实序列的 FFT算法。本节介绍的2种算法都是以复数FFT 算法为基础，利用了DFT的对称性和FFT算法 特点而设计的，有较大的实用价值。  算法一：是用一次N点FFT完成两个N点实序 列的DFT计算。设 和 是两个N点实 序列，以 作实部， 作虚部，构成一 个复序列 ，求出 的DFT ，然后 根据DFT的对称性中序列实部的DFT等于序 列DFT的共轭偶对称部分，序列虚部的DFT 等于序列DFT的共轭奇对称部分，即可求出 和 的DFT了，具体步骤如下： （1）构造复序列 （2）求 的N 点FFT，记为 （3）根据对称性求出 和 算法二：N点实序列 ，可以把序列分成两 个N/2的实序列，分别记为 和 ，然后 仿造第一种算法，得到 和 ，最后根 据所采用分解方法和实序列DFT的共轭对称 性，求出 ，具体步骤如下： （1）将N点实序列分解成两个N/2点的实序 列，分解方法采用时间抽取方法； （2）构造复序列 ； （3）求 的N /2点FFT，记为 ； （4）根据对称性求出 和 ； （5）按时间抽取算法的蝶形公式求出 。 4.6 FFT的软件实现 数字信号处理包括数字信号处理的理 论、分析方法、算法与数字信号处理的实 现，即数字信号处理的软件及硬件实现方 法。 实现数字信号处理的方法有三种。 1.采用计算机或者微机 通过程序，用软件的方法来完成数字信号 处理任务。这一实现方法的优点是可适用于各 种数字信号处理的应用场合，很灵活，缺点是 不能实时处理。由于数字信号处理算法中有大 量重复的运算，它只需要利用计算机的一部分 运算系统，没有充分发挥计算机的能力，造成 不必要的浪费。 2.采用专用的信号处理器 针对某种信号处理的特有运算，用专用的 硬件或专用信号处理芯片组成专用的数字信号 处理器。它对于大量经