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

武汉理工大学《信号分析与处理》课程设计说明书

1 Matlab软件介绍

Matlab (Matrix Laboratory，矩阵实验室)软件最初是作为“矩阵理论”和“数据分析”等课程的计算工具，经过十几年的发展和完善，目前已成为世界各国在科学分析和计算领域的主流软件，并被IEEE评述为国际公认的最优秀的科技应用软件。它的主要特点是：

（1） Matlab可以用来解线性方程组、进行矩阵变换与运算、数据插值运算等，能使用户从繁杂的数学运算分析中解脱出来。

（2） Matlab中有许多高级的绘图函数，包括二维、三维、专用图形函数、图形句柄、用户图形界面工具等，利用这些函数可以轻松地完成各种图形的绘制和编辑工作，实现计算结果和编程的可视化。

（3） 友好的用户界面及接近数学表达式的自然化语言，使学习者易于学习和掌握。 （4） 功能丰富的应用工具箱(如信号处理工具箱，通信工具箱，控制系统工具箱等)为用户提供了大量方便实用的处理工具。

Matlab的上述特点，使它深受工程技术人员及科技专家的欢迎，并很快成为应用学科计算机辅助分析、设计、仿真、教学等领域不可缺少的基础软件。目前，国内很多理工院校已经或者正在把该软件作为学生必须掌握的一种软件。

1

武汉理工大学《信号分析与处理》课程设计说明书

2 原理简介

2.1 离散傅里叶变换（DFT）和快速傅里叶变换（FFT）

离散傅里叶变换，是连续傅里叶变换在时域和频域上都离散的形式，将时域信号的采样变换为在离散时间傅里叶变换频域的采样。在形式上，变换两端（时域和频域上）的序列是有限长的，而实际上这两组序列都应当被认为是离散周期信号的主值序列。即使对有限长的离散信号作DFT，也应当将其看作经过周期延拓成为周期信号在做变换。在实际应用中通常采用快速傅里叶变换（FFT）高效计算DFT。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。

2.2 序列的卷积和快速卷积运算

卷积是数字信号处理中最常见的，也是最重要的运算之一。利用卷积可以实现相关计

算和FIR滤波等等，正因为卷积如此重要，所以半个世纪以来，学者们提出了多种不同卷积实现结构，这些结构各有优点，针对不同应用可以灵活选择，而其中快速卷积无疑是重要的卷积方法之一。顾名思义，快速卷积重点在一个“快”，如果对卷积速度要求较高，快速卷积无疑是理想的工具。当然，为了提高速度，就要牺牲面积和功耗。在此，我们是利用快速傅里叶变换实现快速卷积运算。

2.3 快速傅里叶变换和快速卷积

在此，我们是利用快速傅里叶变换实现快速卷积运算。同时在进行Matlab编程时也是利用快速傅里叶变换来得到快速卷积的结果。（具体方法将在分析中详细介绍）

3 Matlab程序设计

3.1 程序设计

题目1：已知线性非移变系统的h(n)=[6,2,3,4,2]，输入为x(n)=[1,2,3,4,5]；

（1） 用人工计算系统输出y(n)； （2） 编写程序输出y(n)，并作图。 程序1：

h=[6,2,3,6,4,2]; x=[1,2,3,4,5]; y=conv(h,x); stem(y)

2

武汉理工大学《信号分析与处理》课程设计说明书

题目2：用函数conv和FFT计算长为1000序列的卷积，比较其计算时间。

程序2： 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)

题目3：用快速卷积法计算x(n)?0.9nRM(n)和h(n)?RN(n)两个序列的卷积；并测试直接卷积和快速卷积的时间。

程序3：

xn=0.9*(1:20); hn=1*(1:16); tic;

yn=conv(xn,hn); toc;

L=pow2(nextpow2(20+16-1)); tic

xk=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)');

3.2程序仿真

题目1：

（1） 用人工计算系统输出y(n)： 先分别画出x(n)和h(n)的序列

3

武汉理工大学《信号分析与处理》课程设计说明书

3.3 运行结果及分析

4