数字信号处理课件第四章.pptVIP

例： 的第一级分解得4个分裂基 同样对 、 、 可以作进一步分解。 和 的第二级分解分别是基-4的4点DFT。 的第二级分解得2个分裂基，以及 1个基-4的4点DFT和2个基-2的2点DFT。 2点DFT、4点DFT碟形都没有乘法，只有每个分裂基有两次复乘。 运算量：（ ） 分裂基碟形数： §4-10 线性卷积与线性相关的FFT算法 一、线性卷积的FFT算法 乘法运算量： 若系统满足线性相位，即： 则需运算量： 若x(n)长度为L，h(n)长度为M， 则直接计算其线性卷积 y(n)： FFT法：以圆周卷积代替线性卷积 步骤：1) H(k) = FFT [h(n)] N /2*log2N 次乘 4) y(n) = IFFT [Y(k)] N /2*log2N 次乘 3) Y(k) = H(k)X(k) N 次乘 2) X(k) =FFT [x(n)] N /2*log2N 次乘 N 总乘法次数： FFT FFT IFFT x(n) h(n) y(n) X(k) H(k) Y(k) 流程图 直接计算和FFT法计算的运算量比较： 讨论： 1）当 2）当L M 分段方法： 1. 重叠相加法 N 设h(n)的点数为M，信号x(n)为很长的序列。 计算过程： 各断的重叠部分要相加 2. 重叠保留法 舍弃yi(n)的前M-1个点，再将yi(n)顺次连接，即得y(n)。 分段 右移序列 卷积 N L h(-n) h(-n) h(n) 二、线性相关的FFT算法 线性相关 DFT （圆周翻褶） 若x(n)长为L，y(n)长为M，计算线性相关： 利用FFT计算线性相关的步骤： 计算量：与计算线性卷积相同。 作业： P195： 14 第四版 P267 : 11 * * * 1.相同点 (1)进行原位运算； (2)运算量相同,均为复乘 复加 2.不同点 (1) DIT输入为倒位序,输出为自然顺序； DIF正好与此相反。但DIT也有输入为自然顺序,输出为倒位序的情况。 三. DIF法与DIT法的比较： (2) 蝶形运算不同 DIT的蝶形： 用矩阵表示 = 1 1 DIF的蝶形： 用矩阵表示 = 1 1 (3) 两种蝶形运算的关系： 互为转置（矩阵） 转置定理：将流图的所有支路方向倒转,并交换输入与输出，所得系统的输入输出关系不变。 （图4.5的DIT与图4.17的DIF基2FFT流图实质为一个图） DIT： DIF: 1 1 1 1 转置后即为： 作业： P194： 3 （ N 改为8 ） 第四版 P266: 2 （N改为8） §4-5 IDFT的快速计算方法 一. 稍微变动FFT程序和参数可实现IFFT： 比较两式的区别： 比较可知,对DFT作如下修改便可实现IDFT: (1) (2) 输出前乘以常数1/N。 另外,可以将常数1/N分配到每级运算中: ∵ , ∴ 每级蝶形运算均乘 1/2。 二. 利用FFT程序直接实现IFFT: 利用FFT子程序实现IDFT的步骤： （1）取共轭：即将 的虚部乘 -1 ； （2）调用FFT子程序：计算DFT； （3）取共轭：对FFT的输出再取一次共轭； （4）乘1/N ： 即得 。 共轭 FFT 共轭 乘1/ N §4-7 基-4 FFT 算法 基-4FFT条件： 基本思想：将N点DFT化为4个 点DFT。 一. 按时间抽选（DIT）： Radix-4 N/4DFT … … N/4DFT … … N/4DFT … … N/4DFT … … -j -1 j -1 -1 -1 j -j N/4DFT … … N/4DFT … … N/4DFT … … N/4DFT … … - j -1 -1 -1 -1 二. 按频率抽选（DIF）： 其中 这里的系数矩阵与DIT中的矩阵相同。 N/4DFT … … N/4DFT … … N/4DFT … … N/4DFT … … -1 -j -1 j -1 -1 j -j N/4DFT …