基于重叠相加法圆周卷积的实现

目录摘要..................................................................Ⅰ1理论学习.............................................................11.1圆周卷积原理.....................................................11.2重叠相加法.......................................................21.3重叠相加法圆周卷积................................................41.4线性卷积、圆周卷积、重叠相加法、DFT、FFT之间的联系.................52程序设计..............................................................62.1程序设计思路.....................................................62.2程序设计流程图....................................................72.3程序代码.........................................................73程序调试与结果与分析...................................................9心得体会...............................................................11参考文献...............................................................12武汉理工大学《信号分析与处理》课程设计说明书11理论学习1.1圆周卷积原理对两个N点序列)(1nx和)(2nx，除了可以做线性卷积外，还有一种很重要的卷积运算，就是圆周卷积。令则圆周卷积结果长度不变,为N.由上式可以得出圆周卷积与周期卷积的关系，就是有限长序列圆周卷积结果的周期延拓，等于它们周期延拓后的周期卷积。也就是说，周期卷积的主值序列，是各周期序列主值序列的圆周卷积。若)(1nx、)(2nx分别是长度为N、M的序列则)(1nx与)(2nx线性卷积至多M+N-1个非零值，如果LM+N-1则周期延拓时必然会有一部分非零值发生混叠；只有当LM+N-1时，周期延拓才不会发生混叠。之所以讨论用圆周卷积来计算线性卷积的条件，是因为圆周卷积可在频域下利用DFT求得，从而可采用DFT的快速算法FFT来计算，这样就可以利用FFT来计算线性卷积，大大提高运算效率。1010)()(1111NnNNnnxnx1010)()(2222NnNNnnxnx1012102121))(()())(()()()()(NmNNmNmnxmxmnxmxnxnxny武汉理工大学《信号分析与处理》课程设计说明书2圆周卷积的实现步骤如下图：图1.1圆周卷积的实现步骤1.2重叠相加法DFT是连续傅里叶变换在时域和频域上都离散的形式，将时域信号的采样变换为在离散时间傅里叶变换频域的采样。在形式上，变换两端（时域和频域上）的序列是有限长的。DFT具备明确且合理的物理含义，适合应用于数字系统，同时可以方便地由计算机进行运算。对于线性非移变离散系统，可由线性卷积表示时域输入输出关系，即y(n)=x(n)*h(n)武汉理工大学《信号分析与处理》课程设计说明书3通常采用循环卷积降低运算量，但实际中往往无法满足对信号处理的实时性要求。因此，产生了重叠相加法，用以快速计算线性卷积，成为了DFT的一个重要应用。重叠相加法是将待过滤的信号分割成长为N的若干段，如图1所示，每一段都可以和有限时宽单位取样响应作卷积，再将过滤后的各段重叠相加。具体算法实现原理如图2所示，建立缓存序列，每次输入N点序列，通过计算x(n)和h(n)的循环卷积实现线性卷积运算，将缓存的M-1点序列和卷积结果相加，并输出前N点作为计算结果，同时缓存后M-1点，如此循环，直至所有分段计算完毕，则输出序列y(n)为最终计算结果。图1.2重叠相加法的分段示意图图1.3重叠相加法算法示意图武汉理工大学《信号分析与处理》课程设计说明书41.3重叠相加法圆周卷积在实际应用中利用FFT来计算两个序列的圆周卷积从而实现计算其线性卷积，但是常遇到的问题是参加卷积的两个序列的长度相差较大，这样长度小的序列就需要补很多的零点，这样就需要较大的存储量，运算时间也会变长。所以常用到的解决方法有两种，其中一种就是重叠相加法。h(n)长度为N，x(n)长度为无限长，x(n)取M点，且与N尽量接近图1.4重叠相加法的卷积示意图重叠相加法的步骤如下（1）将h(n)补零延长到L=M+N-1，并计算长为L的FFT，得到H(k)。kknxnx)()()()()(kMnRnxnxMkx(n)与h(n)的卷积为)(*)()(*)()(nxnhnhnxnykk)()](*)([nynhnxkkkk武汉理工大学《信号分析与处理》课程设计说明书5（2）分别将xk(n)补零延长到L=M+N-1，并计算长为L的FFT，得到Xk(k)（3）计算)()()(kHkXkYkk，并求长为L的反变换，即)]([)(kYIFFTnykk（4）将yk(n)的重叠部分相加，最后得到结果为kknyny)()(1.4线性卷积、圆周卷积、重叠相加法、DFT、FFT之间的联系由时域与频域的关系可知，两序列)(1nx和)(2nx在时域下进行线性卷积的结果等于这两个序列在频域下相乘后进行反变换回时域的结果。圆周卷积在一定条件下（LM+N-1）与线性卷积得到的结果相同，而圆周卷积可在频域下利用DFT求得，从而可采用DFT的快速算法FFT来计算，这样就可以利用FFT来计算线性卷积，大大提高运算效率。而在利用FFT来计算圆周卷积的过程中当两序列的长度相差较大时采用重叠相加法来进行计算可有效提高计算的效率，减小存储空间的消耗。武汉理工大学《信号分析与处理》课程设计说明书62程序设计2.1程序设计思路函数conv(x1,x2,L)设计（1）x1(n)进行N点快速傅里叶变换得X1(k)（2）x2(n)进行N点快速傅里叶变换得X2(k)（3）进行频域相乘Y(k)=X1(k)*X2k（4）对Y(k)进行反变换得到时域卷积结果y(n)函数overlap_add(x,h,N)设计方案1：（1）首先取长序列x(n)进行分段的长度N，以使其分段后的长度与较短的相近（2）确定圆周卷积的周期L（3）填充序列使得循环中对序列的索引不会超出范围（4）确定分段数K（5）对序列进行分段调用conv()函数计算圆周卷积（6）各段重叠相加（7）取出实际的输出序列方案2：（1）首先取圆周卷积的周期L（即进行L点的快速傅里叶变换）（2）计算每一分段的大小N（3）填充序列使得循环中对序列的索引不会超出范围（4）计算分段数K（5）对序列进行分段调用conv()函数计算圆周卷积（6）各段重叠相加（7）取出实际的输出序列结论：方案二比较接近我们平常的思维，使用较为方便，利于程序调试。武汉理工大学《信号分析与处理》课程设计说明书72.2程序设计流程图图2.1程序设计流程图2.3程序代码functiony=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反变换得循环卷积结果开始输入序列x(n),h(n)计算各个序列长度，分段数，生成临时序列填入保留值后分段循环卷积输出前N个点并为t(n)重新赋为保留值完成所有分段计算输出序列y（n）结束武汉理工大学《信号分析与处理》课程设计说明书8functiony=overlap_add(x,h,N)%重叠相加法实现%核心为将高点数DFT转化为低点数DFT，且用循环卷积计算线性卷积M=length(h);%获得h(n)的长度ifNM%为N选择合适的值保证运算正确N=M+1;endL=M+N-1;%循环卷积与线性卷积结果相同时需要进行运算的最少点数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);%取出最终的输出序列武汉理工大学《信号分析与处理》课程设计说明书93程序调试与结果与分析先输入程序段conv(x1,x2,L)保存为circular_conv.m再输入程序段overlap_add(x,h,N)保存为overlap_add.m如下图：图3.1程序调试输入序列和周期Lx1=[1:2:20];x2=[-2:1:2];L=14;图3.2程序调试结果武汉理工大学《信号分析与处理》课程设计说明书10如图可见，运算结果：-2-7-13-18-20-20-20-20-20-2022475338输入指令输出图表可获得更直观的结论：x=[1:2:20];h=[-2:1:2];overlap_add(x,h,14);subplot(3,1,1);c=1:2:20;stem(c,x);subplot(3,1,2);b=1:5;stem(b,h);subplot(3,1,3);a=1:14;stem(a,ans);图3.3卷积结果由程序运行结果与线性卷积结果比较可以知道程序计算结果正确的，程序设计完成。武汉理工大学《信号分析与处理》课程设计说明书11心得体会总是说学习要温故而知新。课程设计进行之初，思绪全无，举步维艰，对于理论知识学习不够扎实的我深感“书到用时方恨少”，于是想起圣人之言“温故而知新”，便重拾教材与实验手册，对知识系统而全面进行了梳理，遇到难处先是苦思冥想再向同学请教，终于熟练掌握了基本理论知识，学会了如何思考的思维方式，找到了解决的方案。虽然第一遍的方案总有那么多的欠缺，但是过而能改，善莫大焉。至善至美，是人类永恒的追求。但是，不从忘却“金无足赤，人无完人”，换种思维方式，去恶亦是至善，改错亦为至美。在课程设计过程中，我不断发现错误，不断改正，不断领悟，不断获取。最终的仿真环节，本身就是在践行“过而能改，善莫大焉”的知行观。我要感谢所有给与我帮助的同学和老师，正是有你们的帮助才使得我理清了思路，少走了许多弯路。同时你们的许多独到的想法也给与了我一种全新的认识，使那些原本在脑海中的零零散散的知识点最终汇聚一堂，形成了一个完整的体系。并且在实践中得到了肯好的印证，使原本相对生硬的知识给我留下了相当直观的不可磨灭的影响。这一切都为今后我自己的发展提供了有力的保障。武汉理工大学《信号分析与处理》课程设计说明书12参考文献[1]刘泉、阙大顺、郭志强，《数字信号处理》，电子工业出版社，2009[2]Ingle.V.K，《数字信号处