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

1、目 录摘要1 理论学习11.1圆周卷积原理11.2重叠相加法21.3重叠相加法圆周卷积41.4线性卷积、圆周卷积、重叠相加法、dft、fft之间的联系52 程序设计62.1程序设计思路62.2程序设计流程图72.3 程序代码73程序调试与结果与分析9心得体会11参考文献121 理论学习1.1圆周卷积原理对两个n点序列和，除了可以做线性卷积外，还有一种很重要的卷积运算，就是圆周卷积。令则圆周卷积结果长度不变, 为n.由上式可以得出圆周卷积与周期卷积的关系，就是有限长序列圆周卷积结果的周期延拓，等于它们周期延拓后的周期卷积。也就是说，周期卷积的主值序列，是各周期序列主值序列的圆周卷积。若、分别是长

2、度为n、m的序列则与线性卷积至多m+n-1个非零值，如果lm+n-1时，周期延拓才不会发生混叠。之所以讨论用圆周卷积来计算线性卷积的条件，是因为圆周卷积可在频域下利用dft求得，从而可采用dft的快速算法fft来计算，这样就可以利用fft来计算线性卷积，大大提高运算效率。圆周卷积的实现步骤如下图：图1.1 圆周卷积的实现步骤1.2重叠相加法dft 是连续傅里叶变换在时域和频域上都离散的形式，将时域信号的采样变换为在离散时间傅里叶变换频域的采样。在形式上，变换两端（时域和频域上）的序列是有限长的。dft 具备明确且合理的物理含义，适合应用于数字系统，同时可以方便地由计算机进行运算。对于线性非移变

3、离散系统，可由线性卷积表示时域输入输出关系，即y(n)=x(n)*h(n)通常采用循环卷积降低运算量，但实际中往往无法满足对信号处理的实时性要求。因此，产生了重叠相加法，用以快速计算线性卷积，成为了dft 的一个重要应用。重叠相加法是将待过滤的信号分割成长为n 的若干段，如图1 所示，每一段都可以和有限时宽单位取样响应作卷积，再将过滤后的各段重叠相加。具体算法实现原理如图2 所示，建立缓存序列，每次输入n 点序列，通过计算x(n) 和h(n) 的循环卷积实现线性卷积运算，将缓存的m-1 点序列和卷积结果相加，并输出前n 点作为计算结果，同时缓存后m-1 点，如此循环，直至所有分段计算完毕，则输

4、出序列y(n)为最终计算结果。图1.2 重叠相加法的分段示意图图1.3 重叠相加法算法示意图1.3重叠相加法圆周卷积在实际应用中利用fft来计算两个序列的圆周卷积从而实现计算其线性卷积，但是常遇到的问题是参加卷积的两个序列的长度相差较大，这样长度小的序列就需要补很多的零点，这样就需要较大的存储量，运算时间也会变长。所以常用到的解决方法有两种，其中一种就是重叠相加法。h(n)长度为n，x(n)长度为无限长，x(n)取m点，且与n尽量接近 x(n)与h(n)的卷积为图1.4 重叠相加法的卷积示意图重叠相加法的步骤如下（1）将h(n)补零延长到l =m+ n -1，并计算长为l的fft，得到 h(k

5、)。（2）分别将xk(n)补零延长到l =m+ n -1，并计算长为l的fft，得到 xk(k)（3）计算，并求长为l的反变换，即（4）将yk(n)的重叠部分相加，最后得到结果为1.4线性卷积、圆周卷积、重叠相加法、dft、fft之间的联系由时域与频域的关系可知，两序列和在时域下进行线性卷积的结果等于这两个序列在频域下相乘后进行反变换回时域的结果。圆周卷积在一定条件下（lm+n-1）与线性卷积得到的结果相同，而圆周卷积可在频域下利用dft求得，从而可采用dft的快速算法fft来计算，这样就可以利用fft来计算线性卷积，大大提高运算效率。而在利用fft来计算圆周卷积的过程中当两序列的长度相差较大

6、时采用重叠相加法来进行计算可有效提高计算的效率，减小存储空间的消耗。2 程序设计2.1程序设计思路函数conv (x1,x2,l)设计（1） x1(n)进行n点快速傅里叶变换得x1k（2） x2(n)进行n点快速傅里叶变换得x2k（3） 进行频域相乘yk=x1k*x2k（4） 对yk进行反变换得到时域卷积结果y(n)函数overlap_add(x,h,n)设计方案1：（1）首先取长序列x(n)进行分段的长度n，以使其分段后的长度与较短的相近（2）确定圆周卷积的周期l（3）填充序列使得循环中对序列的索引不会超出范围（4）确定分段数k（5）对序列进行分段调用conv ()函数计算圆周卷积（6）各段

7、重叠相加（7）取出实际的输出序列方案2：（1）首先取圆周卷积的周期l（即进行l点的快速傅里叶变换）（2）计算每一分段的大小n（3）填充序列使得循环中对序列的索引不会超出范围（4）计算分段数k（5）对序列进行分段调用conv ()函数计算圆周卷积（6）各段重叠相加（7）取出实际的输出序列结论：方案二比较接近我们平常的思维，使用较为方便，利于程序调试。2.2程序设计流程图开始输入序列x(n),h(n)计算各个序列长度，分段数，生成临时序列填入保留值后分段循环卷积输出前n个点并为t(n)重新赋为保留值完成所有分段计算输出序列y（n）结束图2.1 程序设计流程图2.3 程序代码function y =

8、 circular_conv( x1,x2,l) % 利用循环卷积计算线性卷积 % 循环卷积采用频域计算方法,已fft代替dft,降低运算量 x1k = fft(x1,l); %x1做l点fft x2k = fft(x2,l); %x1做l点fft yk = x1k.*x2k; %频域相乘 y = ifft(yk); %fft反变换得循环卷积结果 function y = overlap_add(x,h,n) %重叠相加法实现 %核心为将高点数dft转化为低点数dft，且用循环卷积计算线性卷积 m = length(h); %获得h(n)的长度 if n m %为n选择合适的值保证运算正确 n

9、 = m+1; end l = m+n-1; %循环卷积与线性卷积结果相同时需要进行运算的最少点数 lx = length(x); %获得x(n)的长度 t = ceil(lx/n); %确定分段数t t = zeros(1,m-1); %初始化序列t(n) x = x,zeros(1, (t+1)*n-lx); %不足的分段补零 y = zeros(1, (t+1)*n); %生成输出序列y(n),长度足够长 for i=0:1:t xi=i*n+1; x_seg = x(xi:xi+n-1); %选择低点数计算时的分段x(n) y_seg = circular_conv(x_seg,h,l

10、); %调用循环卷积计算线性卷积 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个点 end y=y(1:lx+m-1); %取出最终的输出序列3程序调试与结果与分析先输入程序段conv( x1,x2,l)保存为circular_conv.m再输入程序段overlap_add(x,h,n)保存为overlap_add.m如下图：图3.1 程序调试输入序列和周期lx1=1:1:10;x2=-2,0

11、,2;l=12;图3.2 程序调试结果1如图可见，运算结果：-2 -4 -4 -4 -4 -4 -4 -4 -4 -4 18 20输入指令输出图表可获得更直观的结论：x=1:1:10;h=-2,0,2;overlap_add(x,h,12);subplot(3,1,1);c=1:10;stem(c,x);subplot(3,1,2);b=1:3;stem(b,h);subplot(3,1,3);a=1:12;stem(a,ans);图3.3 卷积结果由程序运行结果与线性卷积结果比较可以知道程序计算结果正确的，程序设计完成。心得体会在画家眼里，设计是一幅清明上河图或是一幅向日葵；在建筑师眼中，设

12、计是昔日鎏金般的圆明园或是今日一塑自由女神像；在电子工程师心中，设计是贝尔实验室的电话机或是华为的程控交换机。凡此种种，但凡涉及设计都是一件美好的事情，因为她能给人以美的幻想，因为她能给人以金般财富，因为她能给人以成就之感，更为现实的是她能给人以成长以及成长所需的营养，而这种营养更是一种福祉，一辈子消受不竭享用不尽。我就是以此心态对待此次dsp课程设计的，所谓“态度决定一切”，于是偶然又必然地收获了诸多，概而言之，大约以下几点： 温故而知新。课程设计发端之始，思绪全无，举步维艰，对于理论知识学习不够扎实的我深感“书到用时方恨少”，于是想起圣人之言“温故而知新”，便重拾教材与实验手册，对知识系统

13、而全面进行了梳理，遇到难处先是苦思冥想再向同学请教，终于熟练掌握了基本理论知识，学会了如何思考的思维方式，找到了设计的灵感。 思路即出路。当初没有思路，诚如举步维艰，茫茫大地，不见道路。在对理论知识梳理掌握之后，茅塞顿开，柳暗花明，思路如泉涌，高歌“条条大路通罗马”。顿悟，没有思路便无出路，原来思路即出路。 实践出真知。文革之后，关于真理的大讨论最终结果是“实践是检验真理的唯一标准”，自从耳闻以来，便一直以为马克思主义中国化生成的教条。时至今日，课程设计基本告成，才切身领悟“实践是检验真理的唯一标准”，才明晓实践出真知。 创新求发展。“创新”目前在我国已经提升到国家发展战略地位，足见“创新”的举足轻重。而在dvd产品上市之初及以后相当长时间内，原本前景看好的国内市场却使国内dvd生产商无利可图，只因核心技术受制于人，每台售出总要交付高额专利技术使用费。因此，我们在课程设计中不忘在小处创新，未必是创新技术，但凡创新思维亦可，未必成功，只要实现创新思维培育和锻炼即可。 过而能改，善莫大焉。至善至美，是人类永恒的追求。但是，不从忘却“金无足赤，人无完人”，我们换种思维方式，去恶亦是至善，改错亦为至美。在课程设计过程中，我们不断发现错误，不断改