循環(huán)卷積的快速算法研究

沈君鳳，劉延松

（1.湖北大學(xué)計算機(jī)與信息工程學(xué)院，湖北 武漢430062；2.武漢中原電子集團(tuán)有限公司，湖北 武漢430205）

0 引言

在信號分析與處理領(lǐng)域，卷積是一個極其重要的內(nèi)容，卷積分為線性卷積與循環(huán)卷積［1］.對于數(shù)字（離散）信號，目前計算卷積有幾種途徑：圖解法、豎式法、直接卷積法等.圖解法是畫出有限或無限長序列，通過其變換疊加而得出結(jié)果，其特點(diǎn)是直觀明了；豎式法是將兩個序列寫成豎式相乘的形式，再進(jìn)行相乘與相加運(yùn)算，特點(diǎn)是運(yùn)算簡便且不易出錯；直接卷積法是套用公式進(jìn)行卷積計算，其優(yōu)點(diǎn)是思路清晰［2－3］.

針對循環(huán)卷積計算過程復(fù)雜的問題，目前也有一些新的算法提出，譬如桂林電子科技大學(xué)的陳輝金老師提出的圓周卷積（循環(huán)卷積）的豎式法求解分析，該算法簡單且不易出錯［4］.本文中找出一種更為便捷快速的計算方法，即先通過對位相乘法計算出兩個有限長序列的線性卷積，然后通過循環(huán)卷積與線性卷積之間的關(guān)系，直接求出循環(huán)卷積，該方法簡單快捷、運(yùn)算量小.

1 卷積

1.1 線性卷積 線性卷積本質(zhì)上是多項式系數(shù)乘法：設(shè)a序列的長度是M，b序列的長度是N，則a序列卷積b序列的長度是M＋N－1.

設(shè)x1（n）是N1點(diǎn)的有限長序列，0≤n≤N1－1，x2（n）是N2點(diǎn)的有限長序列，0≤n≤N2－1，則它們的線性卷積為x1（m）的非零區(qū)間為0≤m≤N1－1，x2（n－m）的非零區(qū)間為0≤n－m≤N2－1，將兩個不等式相加，得到

在上述區(qū)間外，顯然有yl（n）＝0，所以yl（n）是（N1＋N2－1）點(diǎn)有限長序列，其序列長度為參與卷積的兩序列的點(diǎn)數(shù)之和減1［5－6］.

1.2 循環(huán)卷積 設(shè)x1（n）和x2（n）都是點(diǎn)數(shù)為N 的有限長序列（0≤n≤N－1）［6－8］

2 基于線性卷積的循環(huán)卷積求解

2.1 線性卷積與循環(huán)卷積比較 給出兩個序列x1（n）＝｛1，2，3，4，5｝，0≤n≤4，x2（n）＝｛1，1，1｝，0≤n≤2，如圖1所示.

圖1 （b） 序列x2（n）

圖1 （a） 序列x1（n）

采用對位相乘法計算出兩個序列的線性卷積，

得到結(jié)果如圖2所示.

圖2 序列x1（n）和x2（n）的線性卷積結(jié)果

圖3 （a） 序列x1（n）和x2（n）5點(diǎn)循環(huán)卷積的結(jié)果

圖3 （b） 序列x1（n）和x2（n）6點(diǎn)循環(huán)卷積的結(jié)果

圖3 （c） 序列x1（n）和x2（n）7點(diǎn)循環(huán)卷積的結(jié)果

圖3 （d） 序列x1（n）和x2（n）8點(diǎn)循環(huán)卷積的結(jié)果

然后依次計算序列x1（n）和x2（n）的5點(diǎn)、6點(diǎn)、7點(diǎn)和8點(diǎn)的循環(huán)卷積，得到結(jié)果如圖3所示.

2.2 線性卷積與循環(huán)卷積的關(guān)系 研究分析得知，當(dāng)循環(huán)卷積的點(diǎn)數(shù)大于或等于兩序列的長度和減1時，循環(huán)卷積的結(jié)果與線性卷積的結(jié)果相同，如上述兩序列的長度分別為5點(diǎn)和3點(diǎn)，其線性卷積的結(jié)果為一個7點(diǎn)的序列，所以7點(diǎn)循環(huán)卷積與線性卷積的結(jié)果完全一樣，而8點(diǎn)循環(huán)卷積的結(jié)果只需要在線性卷積結(jié)果后面補(bǔ)一個零即可；當(dāng)循環(huán)卷積的點(diǎn)數(shù)小于兩序列的長度和減1時，循環(huán)卷積的結(jié)果等于線性卷積取循環(huán)卷積點(diǎn)數(shù)的前幾位，其余項與這幾項依次疊加，如這兩個序列的5點(diǎn)循環(huán)卷積，可先將這兩個序列的線性卷積結(jié)果取前5項，然后將剩余的兩項疊加到第一和第二項上，如下式所示：

這兩個序列的6點(diǎn)循環(huán)卷積則是將它們線性卷積的結(jié)果取前6位，然后將剩余的一項疊加到第一項上，如下式所示：

該計算方法只需將兩個有限長序列的線性卷積通過對位相乘法求出，然后取值疊加即可，與循環(huán)卷積的公式法、圖解法、表格法等常用解法相比，運(yùn)算量極小、速度快、準(zhǔn)確率高.

3 Matlab仿真

基于以上原理進(jìn)行分析，可以設(shè)計程序，利用Matlab軟件進(jìn)行仿真［7－11］，實(shí)現(xiàn)基于重疊相加法的循環(huán)卷積，對提出的循環(huán)卷積新求解方法進(jìn)行驗(yàn)證.

3.1 程序設(shè)計思路 已知兩個有限長序列

1）編制一個計算兩個線性卷積的通用程序，計算x（n）＊h（n）.

2）編制一個計算循環(huán)卷積的通用程序，計算上述8點(diǎn)、7點(diǎn)、6點(diǎn)、5點(diǎn)4種情況下兩個序列x（n）與h（n）的循環(huán)卷積.

3）將仿真結(jié)果與預(yù)計的結(jié)果比較，驗(yàn)證正確性.

仿真結(jié)果如圖4所示.

3.2 利用線性卷積計算循環(huán)卷積 通過以上仿真結(jié)果可知，兩序列的線性卷積結(jié)果是一定的，而其各點(diǎn)的循環(huán)卷積是不同的，各點(diǎn)的循環(huán)卷積結(jié)果和線性卷積的結(jié)果有密切的聯(lián)系.7點(diǎn)的循環(huán)卷積與線性卷積的結(jié)果一樣，6點(diǎn)的循環(huán)卷積結(jié)果為一個6點(diǎn)序列，其結(jié)果為線性卷積結(jié)果保留前6位，最后一位疊加到第一位上所得，5點(diǎn)的循環(huán)卷積結(jié)果為一個5點(diǎn)序列，可以將線性卷積的前5位保留，最后兩位疊加到第一項和第二項即可.以上結(jié)果表明，可以采用線性卷積的結(jié)果來快速計算各點(diǎn)的循環(huán)卷積.

圖4 線性卷積與循環(huán)卷積仿真圖

4 結(jié)論

利用循環(huán)卷積與線性卷積之間的關(guān)系，當(dāng)有限長序列x（n）和h（n）的長度分別為N1和N2，當(dāng)N＝N1＋N2－1時，循環(huán)卷積等于線性卷積；當(dāng)N＞N1＋N2－1時，線性卷積結(jié)果后補(bǔ)上N－N1－N2＋1個零，得到其循環(huán)卷積；當(dāng)N＜N1＋N2－1時，循環(huán)卷積等于線性卷積所得結(jié)果的圓周疊合累加值.在以上分析中，我們分別在N≥N1＋N2－1和N＜N1＋N2－1的兩種不同條件下，分析兩個序列的線性卷積與循環(huán)卷積各自的結(jié)果，對比在兩種不同的情況下時，兩個序列循環(huán)卷積與線性卷積的結(jié)果，研究歸納它們的相同點(diǎn)與不同點(diǎn)，總結(jié)出兩者之間的相對變換關(guān)系，結(jié)合不同點(diǎn)數(shù)的循環(huán)卷積，并且經(jīng)過Matlab軟件的仿真實(shí)現(xiàn)，驗(yàn)證了采用線性卷積快速求解兩個有限長序列的循環(huán)卷積的正確性.

［1］程佩青.數(shù)字信號處理教程［M］.北京：清華大學(xué)出版社，2008.

［2］劉泉，闕大順，郭志強(qiáng).數(shù)字信號處理［M］.北京：電子工業(yè)出版社，2009.

［3］周建興，豈興明.MATLAB從入門到精通［M］.北京：人民郵電出版社，2008.

［4］陳輝金，黃喜軍.圓周卷積的豎式法求解分析［J］.電氣電子教學(xué)學(xué)報，2012，34（3）：19－20.

［5］黃順吉.數(shù)字信號處理及其應(yīng)用［M］.北京：國防工業(yè)出版社，1982.

［6］鄒理和.數(shù)字信號處理［M］.北京：國防工業(yè)出版社，1985.

［7］陳永彬.數(shù)字信號處理［M］.南京：南京工學(xué)院出版社，1987.

［8］何振亞.數(shù)字信號處理的理論與應(yīng)用［M］.北京：人民郵電出版社，1983.

［9］王世一.數(shù)字信號處理［M］.北京：北京理工大學(xué)出版社，1997.

［10］徐金明，張孟喜，丁濤.Matlab實(shí)用教程［M］.北京：清華大學(xué)出版社，2007.

［11］李正周.MATLAB數(shù)字信號處理與應(yīng)用［M］.北京：清華大學(xué)出版社，2008.