数字信号处理实践与应用-MATLAB话数字信号处理（第2版） 课件 案例十二 - 化整为零之重叠相加法

案例十二——化整为零之重叠相加法内容概要案例设置目的相关基础理论情境任务及步骤原理初探实际信号滤波测试思考题总结报告要求案例设置目的通过实验理解大量数据处理给平台带来的影响；理解重叠相加法实现大数据线性卷积的原理与方法；进一步认识线性卷积在工程实践中的实现思路。相关基础理论直接对大量数据进行基于FFT的滤波处理通常会产生这些问题：延迟增加明显，处理器负荷指数增长，

存储空间消耗严重，甚至会出现不堪重负的情况，比如死机。在按照快速卷积实现原理对大量数据信号直接进行处理时，FFT的计算点数N要求不小于M+Ls。由于快速卷积是按帧（Ls个数据一起处理）进行处理的，当Ls非常大时，输出的结果是在完成N点的FFT和IFFT之后才得到的，因此延迟会明显增加。

为处理大量数据又能避免上述问题，先辈们想到了对大数据进行分段处理，然后再对分段处理结果进行拼接，从而实现对所有数据的处理，即化整为零的方式。常用的分段处理有两种方式，重叠相加法（overlap-add）和重叠保留法（overlap-save）。重叠相加法是首先将Ls长的输入信号x(n)

切分成长为L的相邻但不重叠的短序列xi(n)，再将每个短序列xi(n)

与M阶FIR滤波器的单位脉冲响应h(n)(M+1点)

进行线性卷积得到分段处理结果yi(n)

，最后将yi(n)

进行拼接便得到Ls长的输入信号x(n)

与M+1点h(n)

进行线性卷积的结果。如何拼接每个yi(n)

是该方法能否奏效的关键，下面通过一个例子讨论该方法的原理。相关基础理论设输入信号x(n)是一个10点长的序列，FIR系统单位脉冲响应h(n)是3点长序列。为演示重叠相加法原理，这里将x(n)平均分成2段，分别记为x0(n)

和x1(n)，其中x0(n)={x(0),x(1),x(2),x(3),x(4)}，x1(n)={x(5),x(6),x(7),x(8),x(9)}，x(n)与h(n)直接计算卷积和分段计算卷积的关系参见表12-1。细观表12.1可以得到如下三个结论：1每个L=5点长的输入序列段与M+1=3点长序列卷积后输出的结果都是L+M+1-1=L+M=7点长序列，比输入序列长3－1=2=M点；2后一段卷积结果的前M个点加到前一段卷积结果的后M个点上，得到原始输入序列x(n)

与h(n)卷积时对应点上的值；3后一段卷积结果经过2的修正后，正确样点值个数能达到L个，即后一段卷积结果的的前M个点加上前一段输出的后M个点，得到的序列的前L点是x(n)

与h(n)

卷积时对应点上的值，可以直接输出，即每次叠加后能直接输出L点的正确结果。由该例可以推广到一般形式。

相关基础理论

表12.1卷积计算对照表相关基础理论首先将Ls长的输入信号x(n)切分成长为L的相邻但不重叠的短序列xi(n)，当Ls不是L的整倍数时，要在x(n)的后边补零。（12.1）然后计算每段短序列xi(n)

与M阶FIR滤波器的单位脉冲响应h(n)

的线性卷积，结果记为yi(n)，即（12.2）最后，每个后段卷积结果yi(n)与前段卷积结果重叠部分相加（

），并将重叠相加后结果的前L点作为最终结果输出，第i段的输出结果记为youti(n)，即（12.3）顺次将youti(n)串在一起，就可以得到Ls长的输入信号x(n)与M+1点h(n)

进行线性卷积的结果。x(n)与h(n)的卷积结果y(n)也可以直接写成各分段卷积结果yi(n)和的形式，即（12.4）相关基础理论

以上便是重叠相加法计算Ls长的输入信号x(n)与M+1点h(n)线性卷积的整个过程。重叠相加法的思想可以用图表示，原理如图12.1所示。每段短序列xi(n)与h(n)的线性卷积既可以直接计算，也可以用快速卷积实现。设快速卷积实现时FFT的点数为N，要求N为2的整数次幂。已知FIR滤波器的阶数为M，FFT的点数N确定后，每个分段的长度L就可以确定了，L≤N-M

。当L=N-M时，补零的个数最少，效率最高。图12.1重叠相加法原理示意图情境任务及步骤一、原理初探设x(n)是输入信号，FIR系统单位脉冲响应h(n)

是3点长序列。其中x(n)

=

{1,2,4,

2,2,0,

6,2,

4,2,2,

10,6,2,2,0,2}，h(n)

=

{1,1/2,1/4}。1．直接计算x(n)与h(n)的

线性卷积y(n)二者的线性卷积可以手动计算，也可以调用函数conv实现。创建图形窗口Figure1，用stem函数画出y(n)～n的波形，n=0,1,…,19。在图中加注网格线，纵坐标显示范围为

10～10。2．用重叠相加法计算x(n)与h(n)的线性卷积y(n)（1）将x(n)

分成长为5的段，所得短序列分别记为x0(n)、x1(n)、x2(n)

和x3(n)。各短序列与h(n)的线性卷积分别记为y0(n)、y1(n)、y2(n)

和y3(n)。（2）创建图形窗口Figure2，并从上至下分成4个子窗口，分别画出yi(n)～n，i=0,1,2,3，横轴显示n=0,1,…,19的范围。在图中加注网格线和图题，纵坐标显示范围为

10～10。情境任务及步骤（3）对照图形窗口Figure1和Figure2，找出样值幅度相同的点。（4）合成y(n)。按照式（12.4）将yi(n)相加得到序列y(n)，i=0,1,2,3。创建图形窗口Figure3，并从上至下分成5个子窗口，上边的4个子窗口分别画出yi(n)～n，i=0,1,2,3，最下面的子窗口画出y(n)～n，n=0,1,…,19。在图中加注网格线和图题，纵坐标显示范围为

10～10。仔细对照图形窗口Figure3，记录第5个子窗口中序列与前4个子窗口中每个序列样值幅度相同点的变量标号，并将Figure3中的第5个子窗口与Figure1对比。3．画流程图画出基于重叠相加法计算x(n)

与h(n)

的线性卷积y(n)的程序实现流程框图。情境任务及步骤二、实际信号滤波测试设有一个由四个单音组成的复合信号xt，四个单频的频率分别是f1=100Hz，f2=200Hz，f3=300Hz，f4=400Hz，且幅度均为单位1。假定采样频率Fs=8000Hz，试用窗函数法设计FIR滤波器，以滤除频率为f1和f4的单频，并评估所设计滤波器的性能。1．生成复合信号xtxt是四个单位幅度单频正弦信号的叠加，信号持续时间tend为2s。2．用窗函数法设计数字带通滤波器1）滤波器指标设定（1）边界频率设定。通带截止频率这样设定，通带低端截止频率fp1=190Hz，通带高端截止频率fp2=310Hz，阻带低端截止频率fs1=110Hz，阻带高端截止频率fs2=390Hz。

（2）衰减指标设定。在阻带截止频率处的衰减不低于60dB。情境任务及步骤2）调用函数设计满足滤波器指标的FIR滤波器调用函数fir1确定FIR滤波器系数或滤波器的单位脉冲响应，并记为b。

b=fir1(M,[Wn1Wn2],'bandpass',winB);其中滤波器阶数M设定为600，带通滤波器两个归一化边界频率分别按照下述方式进行设置：Wn1=2*pi*(fp1+fs1)/2/Fs/pi;Wn2=2*pi*(fp2+fs2)/2/Fs/pi;WinB表示所用的窗函数，每个样点值由下述语句确定：winB=blackman(M+1);函数fir1更为详细的调用语法可以通过MATLAB中的Help文件学习。

情境任务及步骤

3）指标验证（1）调用函数fft，计算b的DFT，结果记为H。（2）调用函数abs计算H的模值，记为AH；调用函数max计算AH的最大值，记为maxAH；以maxAH为单位对AH进行归一化。（3）创建图形窗口画出幅频特性图。画出20

lg(AH/maxAH)与f的曲线，f的取值范围是0～Fs；调用函数axis，使得纵坐标的显示范围为

100～5，横坐标的显示范围为0～1000。（4）调用函数line，画出六条线以标记界频率和关键衰减指标的位置，(0,

1)

(1000,

1)、(0,

60)

(1000,

60)、(fp1,

100)

(fp1,

1)、(fp2,

100)

(fp2,

1)、(fs1,

100)

(fs1,

1)、(fs2,

100)

(fs2,

1)。

对照图确定所设计滤波器是否满足滤波器指标要求。

情境任务及步骤3．滤波（1）对信号xt进行直接进行线性卷积滤波，结果记为filteredxt1，即filteredxt1=conv(b,xt)；（2）对信号xt通过重叠相加法进行滤波，结果记为filteredxt2。调用MATLAB函数实现重叠相加法时需要两步：调用函数dfilt，指定系数b所描述的滤波器为重叠相加法结构；调用函数filter将这种结构滤波器施加于信号xt。hd=dfilt.fftfir(b,lb);filteredx2=filter(hd,xt);其中lb设定为1024。相关函数的调用语法可以通过MATLAB中的Help文件学习。情境任务及步骤4．卷积计算算法性能评估1）主观评价调用函数sound，试听xt、filteredxt1、filteredxt2的声效，重点对比后两者的效果。为提高对比效果，建议执行完主程序后在命令窗口中调用sound进行试听。2）时域对比创建新的图形窗口，画出两次滤波结果的差值波形，即filteredxt1-filteredxt2，并添加网格线（grid）。分析两种实现方法结果的差异在什么样的数量级，并将结果记入情境任务总结报告。3）频域对比调用函数fft，计算xt、filteredxt1、filteredxt2的DFT，并将结果分别记为X0、X1、X2。创建新的图形窗口，并将窗口从上至下分为两个子窗口，分别显示滤波前后的频谱图。两个子窗口中显示的频谱都要进行归一化，即最大幅度对应0dB。分析两种实现方法的结果在什么情况下有明显差异，并将结果记入情境任务总结报告。情境任务及步骤4）时效对比在程序中，conv和filter两个函数调用语句之前均首先调用tic，语句之后随即都再调用toc。（1）测试信号长度影响。将tend分别设置为2s、20s、200s和1200s重新执行程序，比较分段处理与非分段处理执行时间的差异，并将比较结果记入情境任务总结报告。（2）测试分段长度影响。在tend取1200s条件下，将lb分别设置为1

1024、2

1024、4

1024、8

1024和16

1024重新执行程序，比较分段处理与非分段处理执行时间的差异，并将比较结果记入情境任务总结报告。思考题（1）重叠相加法的提出是为了解决什么样的问题？（2）若已知x(n)={1,2,4,

2,2,0,

6,2,

4,2,2,

10,6,2,2,0,2}和h(n)={1,1/2,1/4}，用函数conv和filter两种方式实现滤波，输出结果会有哪些差异？并尝试回答差异出现的原因。总结报告要求（1）情境任务总结报告中原理部分要简要描述重叠相加法分段计算线性卷积的原理，书写情境任务时可适当进行归纳和总结，但至少要列出【情境任务及步骤】相关内容的各级标题。（2）情境任务的程序清单除在报告中出现外，还必须以独立的m文件形式单独提交。程序清单要求至少按程序块进行注释。（3）效果图和得出的结论附于相应的情境任务下。（4）下述内容翻译成中文写在情境任务总结报告中。Theoverlap-addalgorithmfilt