圓周卷積算法的改進與實現

李廣，蘇建元

（河海大學 能源與電氣學院，江蘇 南京 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垃圾短信過濾系統。