圆周卷积算法的改进与实现

李广，苏建元

（河海大学 能源与电气学院，江苏 南京 211100）

圆周卷积算法的改进与实现

李广，苏建元

（河海大学 能源与电气学院，江苏 南京 211100）

离散卷积是数字信号处理课程中的一种最基本的运算。该算法是在圆周卷积的传统算法上进行研究的，以离散线性卷积和圆周卷积为基本理论基础，引入主值序列矩阵概念。对序列进行补零，将得到的序列依次循环右移，构建主值序列矩阵求解圆周卷积。通过实际算例验证了该算法极大地简化了圆周卷积的运算；在Matlab中，新算法所得的仿真结果与FFT和IFFT实现的仿真结果一致，进一步验证了该方法的有效性和优越性。

数字信号处理；Matlab；离散卷积；FFT；IFFT

在数字信号处理课程中，线性卷积和圆周卷积是最基本的运算。文献[1]中的方法在学习、计算中，过程较为繁琐，且浪费时间。而文献[2]中的算法也有局限，为了简洁、快速、有效的解决问题，提出此改进算法。

1 离散卷积的基础知识

1.1 线性卷积的基础理论

设两序列为x(n)和h(n)，则求解线性卷积的公式[1]定义为：

线性卷积的求解过程可分为：翻褶、移位、相乘和相加等4个步骤[1]：

1)翻褶：先在变量坐标m上作出x(m)和h(m)，将h(m)以m=0的垂直轴为对称轴翻褶成h(-m)。

2)移位：将h(-m)移位n，即得到h(n-m)。当n为正整数时，右移n位；当n为负整数时，左移n位。

3)相乘：再将h(n-m)和x(m)的相同m值得对应点值相乘。

4)相加：把以上所有对应点的乘积叠加起来，即得有y (n)值。

1.2 圆周卷积的基础理论

设x1(n)是N1点的有限长序列(0≤n≤N1-1)，x2(n)是N2点的有限长序列（0≤n≤N2-1）。设y(n)=x1(n)⊗x2(n)是两个序列的L点圆周卷积，先在x1(n)中补上L-N1个零值点，在x2(n)中补上L-N2个零值点，则圆周卷积的公式定义[1]为：

其中，若L≥N1+N2-1，则L点圆周卷积能代表线性卷积。

2 圆周卷积算法的改进与分析

2.1 圆周卷积算法的改进

设x1(n)是N1点的有限长序列{μ1，μ2，…，μn},0≤n≤N1-1，要求 L点圆周卷积，则序列x1(n)经过补零得到序列[μ1，μ2，…μL]，并将此序列依次循环右移1位，共右移L-1次，构建主值序列矩阵：

其中，主值序列矩阵A是一个L阶的矩阵。

根据主值序列矩阵A求解L点圆周卷积的公式为：

其中，A和x2(n)的维数一致。

2.2 算法分析

例：两个序列分别为x={5,4,3,2,1},h(n)={1,1,1},求其5点圆周卷积。

第一种算法：根据公式(1)和公式(2)可得y5(n)={8,10,12,9,6}, 0≤n≤4。

第二种算法：：根据文献[2]，可得y5(n)=A*h(n)T=[8 10 12 9 6]，0≤n≤4。

同理可得，x(n)和h(n)的6点圆周卷积y6(n)=x(n)⊗h(n) {6,9,12,9,6,3}，0≤n≤5。x(n)和h(n)的7点圆周卷积y7(n)=x(n)⊗h(n)={5,9,12,9,6,3,1}，0≤n≤6。x(n)和h(n)的8点圆周卷积y8(n)=x(n)⊗h(n)={5,9,12,9,6,3,1}，0≤n≤7。通过上述计算，我们发现两个长度分别为N1和N2的有限长序列x1(n)和x2(n)，当计算它们的L点圆周卷积时，若L≥N1+N2-1，这时圆周卷积结果与线性卷积结果相同。

2.3 改进算法的Matlab实现

运用matlab实现上述例子的程序如下：

实验仿真图如图1和图2所示。

图1 圆周卷积的实验仿真图Fig.1 The simulation diagram of circular convolution

2.4 FFT和IFFT实现卷积

根据文献[3]和文献[4]，利用FFT和IFFT在matlab中实现上述例题，得到的实验仿真图如图3。

经分析，图2和图3的仿真结果一致，即FFT和IFFT在Matlab中的仿真的结果与本文所提出的方法在matlab中的仿真结果一致，上述例题所采用的三种计算方法的计算结果也一致。第一种算法[1]是圆周卷积的传统算法，其计算的过程比较复杂；第二种算法[2]，是对补零后的序列进行周期延拓，翻褶、移位后，再对主值区间内的主值序列循环移位构建矩阵，并对该矩阵转置后再求解圆周卷积，运算过程较第一种方法相对简单一些；本文提出的改进算法（即第三种算法），只需对补零后的序列循环移位构建主值序列矩阵计算结果，运算和实现过程较第二种方法更简便。

图2 不同条件L下的实验仿真图Fig.2 The simulation diagram in different conditions of L

图3 fft与ifft实现的卷积仿真图Fig.3 The convolution simulation diagram of fft and ifft

3 结束语

本文通过把编程、仿真软件与圆周卷积的算法研究相结合，提出通过构建主值序列矩阵求解圆周卷积，经过实验仿真和算例验证，改进的算法减少了运算量，提高了运算效率和准确性，方便学生理解、掌握，为学习、计算圆周卷积提供了一个新思路。

[1]程佩青.数字信号处理教程[M].3版.北京:清华大学出版社,2007.

[2]刘冰茹.利用FFT计算线性卷积的实现方法[J].广东工业大学学报,1999,16(3):14-18. LIU Bing-ru.The realization of calculating the linear convolution by FFT method[J].Journal of Guangdong University of Technology,1999(3):14-18.

[3]胡广书.数字信号处理：理论、算法与实现[M].北京:清华大学出版社,1997.

[4]朱仁峰.精通Matlab 7[M].北京:清华大学出版社,2006.

[5]张登奇,陈佳.离散卷积的算法分析及MATLAB实现[J].湖南理工学院学报,2013,26(2):48-52. ZHANG Deng-qi,CHEN Jia.Algorithm analysis and MATLAB realization of discrete convolution[J].Hunan Institute of Technology,2013,26(2):48-52.

[6]徐莉,罗新民,徐燕红.卷积码的Matlab仿真及其性能研究[J].现代电子技术,2006,29(11):64-66. XU Li,LUO Xin-min,XU Yan-hong.Matlab simulation and performance study of convolutional code [J]Modern Electronic Technology,2006,29(11):64-66.

[7]陈琳.基于MATLAB的线性卷积及其快速实现方法 [J].电脑与信息技术,2013,21(4):29-31. CHEN Lin.The linear convolution and its fast implementation method based on MATLAB [J].Computer and Information Technology,2013,21(4):29-31.

Improvement and implementation of circular convolution algorithm

LI Guang,SU Jian-yuan
（College of energy and electrical engineering,Hohai University,Nanjing 211100,China）

The discrete convolution is one of the most basic operation in the course of digital signal processing.The improved algorithm based on the traditional algorithm of circular convolution was a improved research,the paper used the discrete linear convolution and circular convolution as the basic theoretical foundation,introduce the concept of main value sequence matrix. First,rotated right the sequence obtained by zero padding in turn to construct the main value sequence matrix,and then to solve the circular convolution.This new algorithm verified by an example,greatly simplifies the circular convolution operation;in Matlab,the simulation results gained by new method are consistent with?the implementation of FFT and IFFT,which further verify the effectiveness and superiority of this method.

digital signal processing;Matlab;discrete convolution;FFT;IFFT

TN911.72

A

1674－6236（2015）07-0090-03

2014-07-29 稿件编号：201407221

李 广(1987—)，男，江苏宿迁人，硕士研究生。研究方向：Android垃圾短信过滤系统。