北邮《数字信号处理》Matlab实验——实现重叠相加和重叠保留算法完成线性卷积的分段计算

实验题目1：线性卷积的分段计算实验目的： 实现重叠相加和重叠保留算法，完成线性卷积的分段计算（可任意指定x(n)及h(n)）。  试验内容： 1、对算法的概括性说明 重叠相加法是将待过滤的信号分割成长为N 的若干段，每一段都可以和有限时宽单位取样响应作卷积，再将过滤后的各段重叠相加。建立缓存序列，每次输入N 点序列，通过计算x(n)和h(n) 的循环卷积实现线性卷积运算，将缓存的M‐1 点序列和卷积结果相加，并输出前N 点作为计算结果，同时缓存后M‐1 点，如此循环，直至所有分段计算完毕，则输出序列y(n)为昀终计算结果。  重叠保留法相当于将想xl(n)和h(n)作循环卷积，然后找出循环卷中相当于线性的部分。在这种情况下，将序列 y(n)分为长N的若干段，每个输入段和前一段有 M‐1个重叠点。此时只需要将发生重叠的前 M‐1个点舍去，保留重叠的部分并输出，则可获得序列 y(n)。   2、流程图及源代码 序列衔接 M‐1点缓存 每N点输入 h(n) 后M‐1点 xl(n) y(n) N+M‐1点循环卷积 后N点 L点循环卷积 M‐1点缓存 + xl(n) L=N+M‐1 h(n) 后M‐1点 前N点 y(n)  function[y]=circular_conv(x1,x2,L)%利用循环卷积计算线性卷积%循环卷积采用频域计算方法,已FFT代替DFT,降低运算量X1k=fft(x1,L);%x1做L点FFTX2k=fft(x2,L);%x1做L点FFTYk=X1k.*X2k;%频域相乘y=ifft(Yk);%FFT反变换得循环卷积结果endfunction[y]=overlap_add(x,h,N)%重叠相加法实现%核心为将高点数DFT转化为低点数DFT，且用循环卷积计算线性卷积M=length(h);%获得h(n)的长度ifNM%为N选择合适的值保证运算正确N=M+1;endL=M+N-1;%循环卷积与线性卷积结果相同时需要进行运算的昀少点数开始 输入序列X(n)，h(n) 计算各序列长度、分段数、生成临时序列 填入保留之后分段循环卷积 输出前N个点并为t(n)重新赋为保留值 完成所有分段计算？ 输出序列y(n) 结束 否 是 重叠保留法 开始 输入序列X(n)，h(n) 计算各序列长度、分段数、生成临时序列分段循环卷积 重叠相加后输出前N点 完成所有分段计算？ 输出序列y(n) 结束 是 否 重叠相加法 Lx=length(x);%获得x(n)的长度T=ceil(Lx/N);%确定分段数Tt=zeros(1,M-1);%初始化序列t(n)x=[x,zeros(1,(T+1)*N-Lx)];%不足的分段补零y=zeros(1,(T+1)*N);%生成输出序列y(n),长度足够长fori=0:1:Txi=i*N+1;x_seg=x(xi:xi+N-1);%选择低点数计算时的分段x(n)y_seg=circular_conv(x_seg,h,L);%调用循环卷积计算线性卷积y_seg(1:M-1)=y_seg(1:M-1)+t(1:M-1);%完成重叠相加t(1:M-1)=y_seg(N+1:L);%重新对t(n)赋值为保留的后M-1点y(xi:xi+N-1)=y_seg(1:N);%直接输出前N个点endy=y(1:Lx+M-1);%取出昀终的输出序列endfunction[y]=overlap_save(x,h,N)%重叠保留法实现%核心为将高点数DFT转化为低点数DFT，且用循环卷积计算线性卷积Lx=length(x);%获得x(n)的长度M=length(h);%获得h(n)的长度ifNM%为N选择合适的值保证运算正确N=M+1;endL=N+M-1;%为降低点数,取M+N-1点循环卷积即可t=zeros(1,M-1);%初始化序列t(n)T=ceil(Lx/N);%确定分段数x=[x,zeros(1,(T+1)*N-Lx)];%为不足的分段补零y=zeros(1,(T+1)*N);fori=0:1:Txi=i*N+1;x_seg=[t,x(xi:xi+N-1)];%确定每个低点数卷积的分段x(n)t=x_seg(N+1:N+M-1);%为t(n)重新赋值为后M-1个点的值y_seg=circular_conv(x_seg,h,L);%循环卷积计算线性卷积y(xi:xi+N-1)=y_seg(M:N+M-1);%直接取出后N个点作为一次计算的输出endy=y(1:Lx+M-1);%取出实际的输出序end 3、实验结果 输入（参考教材例3.4、3.5）： n=0:9;xn=n+1;hn=[1,0,-1];N=6;y1=conv(hn,xn)y2=overlap_add(xn,hn,N)y3=overlap_save(xn,hn,N)输出： y1=1222222222-9-10y2=Columns1through101.00002.00002.00002.00002.00002.00002.00002.00002.00002.0000Columns11through12-9.0000-10.0000y3=Columns1through101.00002.00002.00002.00002.00002.00002.00002.00002.00002.0000Columns11through12-9.0000-10.0000可见，用重叠相加法和重叠保留发分别计算的卷积结果与直接利用线性卷积计算的结果一致。算法正确性得以验证。  4、结合教材3.5.1节作运算量分析 若有限长因果序列x(n)和h(n)的长度分别为N和M，计算其线性卷积y(n)，需MN次乘法运算，(M‐1)(N‐1)次加法运算。如果利用循环卷积方法，按基2时域抽选法实现L点FFT和IFFT，需23log2LLL次乘法运算，23logLL次加法运算。可以看出：（1）当M、N取值较大且相近时，可实现对线性卷积的快速计算；（2）当M、N有较大差异时，线性卷积和循环卷积运算量相当，此时若希望降低线性卷积计算开销，需采用重叠相加法或重叠保留法。 重叠保留法和相加运行效率与分段长度关性较强。分段数和卷积运算的序列长度为非线性关系，在实际应用中，重叠保留和相加主要用于实施信号处理，在保证实时性的要求下，输入序列的分段不能太长。  5、总结实验过程中出现的问题以及解决问题的具体措施 1.利用自定义函数解决代码重复使用的问题，避免多次输入同样代码。 2.构造分段补零不会实现，通过上网查资料后获得实现相关功能的代码。