序列的卷积和快速卷积运算的编程实现

..1.MATLAB简介MATLAB软件由美国MathWorks公司于1984年推出,经过不断的发展和完善,如今己成为覆盖多个学科的国际公认的最优秀的数值计算仿真软件。MATLAB具备强大的数值计算能力,许多复杂的计算问题只需短短几行代码就可在MATLAB中实现。作为一个跨平台的软件,MATLAB已推出Unix、Windows、Linux和Mac等十多种操作系统下的版本,大大方便了在不同操作系统平台下的研究工作。MATLAB软件具有很强的开放性和适应性。在保持内核不变的情况下,MATLAB可以针对不同的应用学科推出相应的工具箱<toolbox>,目前己经推出了图象处理工具箱、信号处理工具箱、小波工具箱、神经网络工具箱以及通信工具箱等多个学科的专用工具箱,极大地方便了不同学科的研究工作。国内已有越来越多的科研和技术人员认识到MATLAB的强大作用,并在不同的领域内使用MATLAB来快速实现科研构想和提高工作效率。MATLAB提供了20类图像处理函数,涵盖了图像处理的包括近期研究成果在内的几乎所有的技术方法,是学习和研究图像处理的人员难得的宝贵资料和加工工具箱。这些函数按其功能可分为:图像显示;图像文件I/O;图像算术运算;几何变换;图像登记;像素值与统计;图像分析;图像增强;线性滤波;线性二元滤波设计;图像去模糊;图像变换;邻域与块处理;灰度与二值图像的形态学运算;结构元素创建与处理;基于边缘的处理;色彩映射表操作;色彩空间变换;图像类型与类型转换。MATLAB的应用领域十分广阔,典型的应用举例如下：<1>数据分析<2>数值与符号计算；<3>工程与科学绘图；4>控制系统设计；<5>航天工业；<6>汽车工业；<7>生物医学工程；8>语音处理；<9>图像与数字信号处理；<10>财务、金融分析；<11>建模、仿真及样机开发；<12>新算法研究开发；13>图形用户界面设计MATLAB的应用范围非常广,包括信号和图像处理、通讯、控制系统设计、测试和测量、财务建模和分析以及计算生物学等众多应用领域。附加的工具箱〔单独提供的专用MATLAB函数集扩展了MATLAB环境,以解决这些应用领域内特定类型的问题。它的主要特点是：〔1Matlab可以用来解线性方程组、进行矩阵变换与运算、数据插值运算等,能使用户从繁杂的数学运算分析中解脱出来。〔2Matlab中有许多高级的绘图函数,包括二维、三维、专用图形函数、图形句柄、用户图形界面工具等,利用这些函数可以轻松地完成各种图形的绘制和编辑工作,实现计算结果和编程的可视化。〔3友好的用户界面及接近数学表达式的自然化语言,使学习者易于学习和掌握。〔4功能丰富的应用工具箱<如信号处理工具箱,通信工具箱,控制系统工具箱等>为用户提供了大量方便实用的处理工具。Matlab的上述特点,使它深受工程技术人员及科技专家的欢迎,并很快成为应用学科计算机辅助分析、设计、仿真、教学等领域不可缺少的基础软件。目前,国内很多理工院校已经或者正在把该软件作为学生必须掌握的一种软件。2.项目设计目的及技术要求序列的卷积和快速卷积运算的编程实现,具体包括：直接卷积及运用、快速卷积方法及实现、二者的比较分析等。1． 已知线性非移变系统的h<n>=[6,2,3,6,4,2],输入为x<n>=[1,2,3,4,5]；〔1 用人工计算系统输出y<n>；〔2 编写程序输出y<n>,并作图。2. 用函数conv和FFT计算长为1000序列的卷积,比较其计算时间。3. 用快速卷积法计算和两个序列的卷积；并测试直接卷积和快速卷积的时间。3.基本原理3.1基本概念在数字信号处理<DSP>系统中,无论在时域或频域都离不开卷积运算和快速傅里叶<FFT>运算。Matlab具有强大的矩阵运算能力,方便实用的绘图功能和语言的高度集成性,在DSP开发中,使用Matlab可以快速对系统进行仿真运算。设输入信号为x<t>,其频谱函数为X<jΩ>,该信号通过滤波器h<t>后,其输出信号y<t>的频谱函数Y<jΩ>是频谱函数x<jΩ>与滤波器的频谱函数H<jΩ>的乘积,即：而在时域,输出信号y<t>实际是输入信号x<t>与滤波器h<t>的卷积。就是说频谱函数的乘积相当于时间函数的卷积,反之亦然。即：由于DSP主要依靠计算机完成,而计算机无论在时域或频域只能处理有限长的离散信号,因此上述关系可表示为：式中：n表示离散时间；数字频率ω=ΩT；f为输入信号频率；f,T为抽样频率和周期。3.2原理分析可以使用线性卷积、圆周卷积实现离散卷积,也可以根据时域信号函数与频谱函数的关系,使用快速傅里叶变换<FFT,IFFT>实现离散卷积。3.2.1离散傅里叶变换〔DFT和快速傅里叶变换〔FFT离散傅里叶变换,是连续傅里叶变换在时域和频域上都离散的形式,将时域信号的采样变换为在离散时间傅里叶变换频域的采样。在形式上,变换两端〔时域和频域上的序列是有限长的,而实际上这两组序列都应当被认为是离散周期信号的主值序列。即使对有限长的离散信号作DFT,也应当将其看作经过周期延拓成为周期信号在做变换。在实际应用中通常采用快速傅里叶变换〔FFT高效计算DFT。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少,特别是被变换的抽样点数N越多,FFT算法计算量的节省就越显著。3.2.2序列的卷积和快速卷积运算卷积是数字信号处理中最常见的,也是最重要的运算之一。利用卷积可以实现相关计算和FIR滤波等等,正因为卷积如此重要,所以半个世纪以来,学者们提出了多种不同卷积实现结构,这些结构各有优点,针对不同应用可以灵活选择,而其中快速卷积无疑是重要的卷积方法之一。顾名思义,快速卷积重点在一个"快",如果对卷积速度要求较高,快速卷积无疑是理想的工具。当然,为了提高速度,就要牺牲面积和功耗。3.2.3快速傅里叶变换和快速卷积在此,我们是利用快速傅里叶变换实现快速卷积运算。同时在进行Matlab编程时也是利用快速傅里叶变换来得到快速卷积的结果。4.程序设计及仿真结果分析4.1题目一长度为m的向量序列h和长度为n的向量序列x,卷积w的向量序列长度为<m+n-1>,当m≠n时,应以0补齐阶次低的向量的高位后进行计算y<1>=h1>*x<1>y<2>=h<1>*x<2>+h<2>*x<1>y<3>=h<1>*x<3>+h<2>*x<2>+h<3>*x<1>=…y<n>=h<1>*x<n>+h<2>*x<n-1>+…+h<n>*x<1>…y<m+n-1>=h<1>*x<m+n-1>+h<2>*x<m+n>+h<3>*x<m+n+1>+…+h<m+n-1>*x<1>那么所得的结果就是y〔n=[6,14,25,42,63,50,55,52,28,10]用matlab仿真编程程序如下：h=[6,2,3,6,4,2];x=[1,2,3,4,5];y=conv<h,x>;stem<y>图4.1系统输出函数y<n>由图4.1可和自己求出的y<n>函数相比较可以得到,用matlab编写程序得出的系统输出函数与自己人工计算的结果相同。4.2题目二在matlab实现卷积的.函数为CONV,对于N值较小的向量,这是十分有效的。对于N值较大的向量卷积可用FFT加快计算速度。若DFT和IDFT均采用FFT和IDFT算法,可提高卷积速度。计算x1<n>和x2<n>的线性卷积的FFT算法可由下面步骤实现：1、 计算X1<k>=FFT[x1<n>];2、 计算X2<k>=FFT[x2<n>];3、 Y<k>=X1<k>·X2<k>;4、 计算x1<n>*x2<n>=IFFT[Y<k>]在本题目中计算的两个函数分别是x1<n>=2*n,x2<n>=3.^n。用matlab编写的完整程序如下所示L=1000;N=L*2-1;n=1:L;x1=2*n;x2=3.^n;t0=clock;yc=conv<x1,x2>;conv_time=etime<clock,t0>t0=clock;yf=ifft<fft<x1,N>.*fft<x2,N>>;fft_time=etime<clock,t0>反正结果如下：图4.2由结果可知,长度为1000时,快速卷积所用时间较少。4.3题目三利用快速卷积原理求两个函数的卷积可以用题目二中所用的方法〔先分别对两个函数求傅里叶变换得到X<k>与H<k>,再两个函数傅里叶变换的点乘的结果y<k>,最后直接对y<k>求傅里叶反变换得到y<n>快速卷积,得到所要求的结果。因为在这次题目中与两个函数中M与N没有给出,取M=2000,N=1800时。所用的程序以及各自的输出结果如下所示：xn=0.9.^<1:20>;hn=1.^<1:16>;tic;yn=conv<xn,hn>;toc;L=pow2<nextpow2<20+16-1>>;ticxk=fft<xn,L>;hk=fft<hn,L>;yk=xk.*hk;yn=ifft<yk,L>;toc;subplot<221>,stem<xn,'.'>;ylabel<'x<n>'>;subplot<222>,stem<hn,'.'>;ylabel<'h<n>'>;subplot<212>,ny=1:L;stem<real<yn>,'.'>;ylabel<'y<n>'>;仿真结果如图4.3：图4.3由仿真结果可知,当点数较大时,快速卷积所用时间明显少于普通卷积。5.心得体会这次课程设计我做的是序列的卷积和快速卷积运算的编程实现,是利用MATLAB这个软件完成的,因为之前我们曾做MATLAB课设,平时使用MATLAB也比较多,所以这次课设做起来也相对比较简单。但是,即使这个比较简单,也要认真对待。MATLAB功能强大,尤其对于我们电子信息类的学生尤其重要,平时用到的机会比较多,认真学好很有必要。完成这次课程设计我认为收获还是很多的,不但进一步掌握了数字信号处理的基础知识及一门专业仿真软件的基本操作,还提高了自己的设计能力及动手能力,同时对于模拟滤波器来了个系统的总结。更多的是让我看清了自己,明白了凡事需要耐心,实践是检验学习的唯一标准。理论知识的不足在这次课设中表现的很明显。这将有助于我今后的学习,端正自己的学习态度,从而更加努力的学习。只有这样我们才能真正的去掌握它,而不是只懂得一点皮毛。在做的课程中,也曾遇到一些小问题,如在程序中两个数之间点成和叉乘的使用没区别好,所以我们应该认真对待每一个小细节,才能做好每件事,端正自己的态度,不要因为简单而不上心。这次课设还加深自己对知识的理解,对序列的卷积和快速卷积理解更加透彻,从理论到实践。只有都经过,知识才能更加牢固。纸上得来终觉浅,绝知此事要躬行。前人已经总结的很好,我们只有在实践中发现自己的问题,然后不断的克服,才能把知识变成自己的,更加好的锻炼