2012数字信号处理课件第二章第五节.pdf

⚫ DFT变换对于离散时间信号处理的分析、设计 都起着十分重要的作用，它实现了信号频谱的离散化， 使得在频域上用数字信号处理成为可能。 ⚫ 有关DFT的性质以及有限长序列的DFT与 变换 和Z变换之间的关系，都是在频域进行系统分析和设 计的重要工具； ⚫ 同样重要的还有实现DFT的高效率的快速算法—— FFT，借助于FFT，使得DFT变换的理论在实际工作 中得以广泛运用，并且在相当多的数字信号处理算法 中位于 的位置。 ⚫ 有限长序列的DFT变换相当于对其 变换 在频域做等间隔的采样，因此计算点DFT相当 于计算 变换在个等间隔频率采样点上的 值。 ⚫ 有关算法有效性和复杂度的评估，存在不同的 方法和标准，根据信号处理的不同应用而侧重 点不同。这里我们采用算术乘法和加法的次数 来度量算法的复杂度。 ⚫ DFT的计算量 N -1 设x(n) ，0 £n £N -1 ，则X (k ) =DFT[x(n)] =  x(n) W kn ， n=0 N 。其中，求一点X (k ) ，复数乘法 次，复数加法 次； 0 £k £N -1 N N -1 2 求 点 ，复数乘法 次，复数加法 次。由于： N X (k ) N N (N -1) 一次复乘＝4 次实乘＋2 次实加；一次复加＝2 次实加，所以： 求N 点X (k ) ，共有4N 2 次实乘，2N 2 ＋2N (N -1) »4N 2 次实加。 ⚫ DFT的计算量 6 例如：设N =1024 ，则有约4 ·10 次实乘与实加。可见 运算量太大，用以实时处理几乎不可能。同样的， 1 N -1 x(n) =IDFT[X (k )] =  X (k )W-kn ， N n=0 N 0 £n £N -1 ，也具有相同的运算量。 ⚫ 1．算法原理 x(n) ，0 £n £N -1 ，N =2M ，即x(n) ={x (0), x(1), x(2),L , x (N -1)} ， 将x(n) 按照n 的奇偶分解成两个子序列，就是： x (n) ={x(0), x(2), x(4),L , x (N -2)} =x(2n) ，0 £n £N 2 -1 1 x (n) ={x(1), x(3), x(5),L , x (N -1)}=x(2n +1) ，0 £n £N 2 -1 2 ⚫ N 2-1 记：X (k ) =DFT[x (n)] = x (n) Wkn ，0 £k £N 2 -1 1 1 n=0 1 N 2 N 2-1 X (