数字信号处理_程佩青_PPT第四章讲述.ppt

和上面的讨论一样， 用FFT法实现重叠相加法的步骤如下:? ① 计算N点FFT， H(k)=DFT［h(n)］； ② 计算N点FFT，Xi(k)=DFT［xi(n)］； ③ 相乘，Yi(k)=Xi(k)H(k)； ④ 计算N点IFFT，yi(n)=IDFT［Yi(k)］； ⑤ 将各段yi(n)（包括重叠部分）相加。 重叠相加的名称是由于各输出段的重叠部分相加而得名的。 例 已知序列x[n]=n+2,0?n?12, h[n]={1,2,1}试利用重叠相加法计算线性卷积, 取L=5 。 y[n]={2, 7, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 41, 14} 解: 重叠相加法 x1[n]={2, 3, 4, 5, 6} x2[n]={7, 8, 9, 10, 11} x3[n]={12,13, 14} y1[n]={2, 7, 12, 16, 20, 17, 6} y2[n]={ 7, 22, 32, 36, 40, 32, 11} y3[n]={12, 37, 52, 41, 14} 2、重叠保存法 此方法与上述方法稍有不同。 先将x(n)分段，每段L=N-M+1个点，这是相同的。 不同之处是，序列中补零处不补零，而在每一段的前边补上前一段保留下来的（M-1）个输入序列值， 组成L+M-1点序列xi(n) 。 如果L+M-12m， 则可在每段序列末端补零值点，补到长度为2m，这时如果用DFT实现h(n)和xi(n)圆周卷积，则其每段圆周卷积结果的前（M-1）个点的值不等于线性卷积值，必须舍去。 重叠保留法示意图 重叠保留法示意图 y[k]={2, 7, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 41, 14} x1[k]={0, 0, 2, 3, 4} x2[k]={3, 4, 5, 6 ,7} x3[k]={6 ,7 , 8, 9, 10} y1[k]= x1[k]?h[k]= {11, 4, 2, 7, 12} x4[k]={9, 10 , 11, 12,13} y2[k]= x2[k]?h[k]= {23, 17, 16, 20, 24} y3[k]= x3[k]?h[k]= {35, 29, 28, 32, 36} y4[k]= x4[k]?h[k]= {47, 41, 40, 44, 48} x5[k]={12,13, 14, 0, 0} y5[k]= x5[k]?h[k]= {12, 37, 52, 41, 14} 解: 重叠保留法 例 已知序列x[n]=n+2,0?n?12, h[n]={1,2,1}试利用重叠保留法计算线性卷积, 取L=5 。 语音信号消噪过程 信号淹没在啸叫噪声中； (b) 信号与噪声的功率谱； (c) 去噪后的功率谱； (d) 重构原语音信号 FFT应用举例 * 常系数线性差分方程 例 用FFT算法处理一幅N×N点的二维图像，如用每秒可做10万次复数乘法的计算机，当N=1024时，问需要多少时间（不考虑加法运算时间）？ 解 当N=1024点时，FFT算法处理一幅二维图像所需复数乘法约为 次，仅为直接计算DFT所需时间的10万分之一。 即原需要3000小时，现在只需要2 分钟。 §4.3 按频率抽选（DIF）的FFT算法 与DIT-FFT算法类似分解，但是抽取的是X(k)。即分解X(k)成奇数与偶数序号的两个序列。 设： N = 2L，L 为整数。将X(k)按k的奇偶分组前，先将输入x(n)按n的顺序分成前后两半： （Decimation In Frequency) 一、算法原理 下面讨论 按k的奇偶将X(k)分成两部分： 显然： 令： 用蝶型结构图表示为： x1(0) x1(1) -1 x1(2) x1(3) -1 x2(0) x2(1) -1 x2(2) x2(3) -1 N/2点 DFT N/2点 DFT x(0) x(7) x(1) x(2) x(3) x(4) x(5) x(6) X1(0)=X(0) X2(0)=X(1) X1(1)=X(2) X1(2)=X(4) X1(3)=X(6) X2(1)=X(3) X2(2)=X(5) X2(3)=X(7) N/2仍为偶数，进一步分解：N/2 → N/4 x3(0) x3(1) -1 -1 x4(0) x4(1) N/4点 DFT N/4点 DFT x1(0) x1(1) x1(2) x1(3) X3(0)=X1(0)=X(0) X4(0)=X1(1)=X(2) X3(1)=X1(2)=X(4) X4(1)=X1(