李廣，蘇建元

（河海大學(xué) 能源與電氣學(xué)院，江蘇 南京 211100）

圓周卷積算法的改進(jìn)與實(shí)現(xiàn)

李廣，蘇建元

（河海大學(xué) 能源與電氣學(xué)院，江蘇 南京 211100）

離散卷積是數(shù)字信號(hào)處理課程中的一種最基本的運(yùn)算。該算法是在圓周卷積的傳統(tǒng)算法上進(jìn)行研究的，以離散線性卷積和圓周卷積為基本理論基礎(chǔ)，引入主值序列矩陣概念。對(duì)序列進(jìn)行補(bǔ)零，將得到的序列依次循環(huán)右移，構(gòu)建主值序列矩陣求解圓周卷積。通過(guò)實(shí)際算例驗(yàn)證了該算法極大地簡(jiǎn)化了圓周卷積的運(yùn)算；在Matlab中，新算法所得的仿真結(jié)果與FFT和IFFT實(shí)現(xiàn)的仿真結(jié)果一致，進(jìn)一步驗(yàn)證了該方法的有效性和優(yōu)越性。

數(shù)字信號(hào)處理；Matlab；離散卷積；FFT；IFFT

在數(shù)字信號(hào)處理課程中，線性卷積和圓周卷積是最基本的運(yùn)算。文獻(xiàn)[1]中的方法在學(xué)習(xí)、計(jì)算中，過(guò)程較為繁瑣，且浪費(fèi)時(shí)間。而文獻(xiàn)[2]中的算法也有局限，為了簡(jiǎn)潔、快速、有效的解決問(wèn)題，提出此改進(jìn)算法。

1 離散卷積的基礎(chǔ)知識(shí)

1.1 線性卷積的基礎(chǔ)理論

設(shè)兩序列為x(n)和h(n)，則求解線性卷積的公式[1]定義為：

線性卷積的求解過(guò)程可分為：翻褶、移位、相乘和相加等4個(gè)步驟[1]：

1)翻褶：先在變量坐標(biāo)m上作出x(m)和h(m)，將h(m)以m=0的垂直軸為對(duì)稱(chēng)軸翻褶成h(-m)。

2)移位：將h(-m)移位n，即得到h(n-m)。當(dāng)n為正整數(shù)時(shí)，右移n位；當(dāng)n為負(fù)整數(shù)時(shí)，左移n位。

3)相乘：再將h(n-m)和x(m)的相同m值得對(duì)應(yīng)點(diǎn)值相乘。

4)相加：把以上所有對(duì)應(yīng)點(diǎn)的乘積疊加起來(lái)，即得有y (n)值。

1.2 圓周卷積的基礎(chǔ)理論

設(shè)x1(n)是N1點(diǎn)的有限長(zhǎng)序列(0≤n≤N1-1)，x2(n)是N2點(diǎn)的有限長(zhǎng)序列（0≤n≤N2-1）。設(shè)y(n)=x1(n)?x2(n)是兩個(gè)序列的L點(diǎn)圓周卷積，先在x1(n)中補(bǔ)上L-N1個(gè)零值點(diǎn)，在x2(n)中補(bǔ)上L-N2個(gè)零值點(diǎn)，則圓周卷積的公式定義[1]為：

其中，若L≥N1+N2-1，則L點(diǎn)圓周卷積能代表線性卷積。

2 圓周卷積算法的改進(jìn)與分析

2.1 圓周卷積算法的改進(jìn)

設(shè)x1(n)是N1點(diǎn)的有限長(zhǎng)序列{μ1，μ2，…，μn},0≤n≤N1-1，要求 L點(diǎn)圓周卷積，則序列x1(n)經(jīng)過(guò)補(bǔ)零得到序列[μ1，μ2，…μL]，并將此序列依次循環(huán)右移1位，共右移L-1次，構(gòu)建主值序列矩陣：

其中，主值序列矩陣A是一個(gè)L階的矩陣。

根據(jù)主值序列矩陣A求解L點(diǎn)圓周卷積的公式為：

其中，A和x2(n)的維數(shù)一致。

2.2 算法分析

例：兩個(gè)序列分別為x={5,4,3,2,1},h(n)={1,1,1},求其5點(diǎn)圓周卷積。

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

第二種算法：：根據(jù)文獻(xiàn)[2]，可得y5(n)=A*h(n)T=[8 10 12 9 6]，0≤n≤4。

同理可得，x(n)和h(n)的6點(diǎn)圓周卷積y6(n)=x(n)?h(n) {6,9,12,9,6,3}，0≤n≤5。x(n)和h(n)的7點(diǎn)圓周卷積y7(n)=x(n)?h(n)={5,9,12,9,6,3,1}，0≤n≤6。x(n)和h(n)的8點(diǎn)圓周卷積y8(n)=x(n)?h(n)={5,9,12,9,6,3,1}，0≤n≤7。通過(guò)上述計(jì)算，我們發(fā)現(xiàn)兩個(gè)長(zhǎng)度分別為N1和N2的有限長(zhǎng)序列x1(n)和x2(n)，當(dāng)計(jì)算它們的L點(diǎn)圓周卷積時(shí)，若L≥N1+N2-1，這時(shí)圓周卷積結(jié)果與線性卷積結(jié)果相同。

2.3 改進(jìn)算法的Matlab實(shí)現(xiàn)

運(yùn)用matlab實(shí)現(xiàn)上述例子的程序如下：

實(shí)驗(yàn)仿真圖如圖1和圖2所示。

圖1 圓周卷積的實(shí)驗(yàn)仿真圖Fig.1 The simulation diagram of circular convolution

2.4 FFT和IFFT實(shí)現(xiàn)卷積

根據(jù)文獻(xiàn)[3]和文獻(xiàn)[4]，利用FFT和IFFT在matlab中實(shí)現(xiàn)上述例題，得到的實(shí)驗(yàn)仿真圖如圖3。

經(jīng)分析，圖2和圖3的仿真結(jié)果一致，即FFT和IFFT在Matlab中的仿真的結(jié)果與本文所提出的方法在matlab中的仿真結(jié)果一致，上述例題所采用的三種計(jì)算方法的計(jì)算結(jié)果也一致。第一種算法[1]是圓周卷積的傳統(tǒng)算法，其計(jì)算的過(guò)程比較復(fù)雜；第二種算法[2]，是對(duì)補(bǔ)零后的序列進(jìn)行周期延拓，翻褶、移位后，再對(duì)主值區(qū)間內(nèi)的主值序列循環(huán)移位構(gòu)建矩陣，并對(duì)該矩陣轉(zhuǎn)置后再求解圓周卷積，運(yùn)算過(guò)程較第一種方法相對(duì)簡(jiǎn)單一些；本文提出的改進(jìn)算法（即第三種算法），只需對(duì)補(bǔ)零后的序列循環(huán)移位構(gòu)建主值序列矩陣計(jì)算結(jié)果，運(yùn)算和實(shí)現(xiàn)過(guò)程較第二種方法更簡(jiǎn)便。

圖2 不同條件L下的實(shí)驗(yàn)仿真圖Fig.2 The simulation diagram in different conditions of L

圖3 fft與ifft實(shí)現(xiàn)的卷積仿真圖Fig.3 The convolution simulation diagram of fft and ifft

3 結(jié)束語(yǔ)

本文通過(guò)把編程、仿真軟件與圓周卷積的算法研究相結(jié)合，提出通過(guò)構(gòu)建主值序列矩陣求解圓周卷積，經(jīng)過(guò)實(shí)驗(yàn)仿真和算例驗(yàn)證，改進(jìn)的算法減少了運(yùn)算量，提高了運(yùn)算效率和準(zhǔn)確性，方便學(xué)生理解、掌握，為學(xué)習(xí)、計(jì)算圓周卷積提供了一個(gè)新思路。

[1]程佩青.數(shù)字信號(hào)處理教程[M].3版.北京:清華大學(xué)出版社,2007.

[2]劉冰茹.利用FFT計(jì)算線性卷積的實(shí)現(xiàn)方法[J].廣東工業(yè)大學(xué)學(xué)報(bào),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]胡廣書(shū).數(shù)字信號(hào)處理：理論、算法與實(shí)現(xiàn)[M].北京:清華大學(xué)出版社,1997.

[4]朱仁峰.精通Matlab 7[M].北京:清華大學(xué)出版社,2006.

[5]張登奇,陳佳.離散卷積的算法分析及MATLAB實(shí)現(xiàn)[J].湖南理工學(xué)院學(xué)報(bào),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].現(xiàn)代電子技術(shù),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的線性卷積及其快速實(shí)現(xiàn)方法 [J].電腦與信息技術(shù),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 稿件編號(hào)：201407221

李 廣(1987—)，男，江蘇宿遷人，碩士研究生。研究方向：Android垃圾短信過(guò)濾系統(tǒng)。