有限長序列循環(huán)卷積的求解

任蕾

(上海海事大學(xué)信息工程學(xué)院，上海 201306)

1 引言

線性卷積和循環(huán)卷積是信號(hào)處理類課程教學(xué)的重要知識(shí)點(diǎn)。二者的定義、常用性質(zhì)、計(jì)算方法和異同點(diǎn)也是教學(xué)的難點(diǎn)之一。離散線性時(shí)不變系統(tǒng)的零狀態(tài)響應(yīng)可通過激勵(lì)序列與系統(tǒng)的單位脈沖響應(yīng)卷積求得。

陳輝金在文獻(xiàn)1中提出了圓周卷積的豎式求解方法，該方法的本質(zhì)是在線性卷積的對(duì)位相乘法基礎(chǔ)上拓展而來的，利用了圓周卷積是線性卷積的周期延拓這一結(jié)論，該方法簡單易學(xué)，便于學(xué)生理解圓周卷積的本質(zhì)[1]。文獻(xiàn)2 在分析循環(huán)卷積與線性卷積關(guān)系的基礎(chǔ)上提出了一種基于序號(hào)和匹配的簡單循環(huán)卷積求解方法[2]，該方法與文獻(xiàn)1的方法本質(zhì)是一致的，充分利用了參與卷積的序列之間的關(guān)系。文獻(xiàn)3 則從線性卷積和循環(huán)卷積的基本概念入手，探討了其運(yùn)算規(guī)則和等價(jià)條件，并提出了一種利用線性卷積快速計(jì)算循環(huán)卷積的方法[3]。此外，與科研相結(jié)合的循環(huán)卷積的教學(xué)探討也有相關(guān)報(bào)道。戚晨皓等結(jié)合通信中的正交頻分復(fù)用技術(shù)，介紹了循環(huán)卷積的應(yīng)用[4]。文獻(xiàn)5 結(jié)合水聲通信領(lǐng)域的應(yīng)用，介紹了基于線性卷積的循環(huán)卷積計(jì)算方法及其在該領(lǐng)域的應(yīng)用[5]。

目前常用的循環(huán)卷積計(jì)算方法主要包括定義法、圖解法、列表法、對(duì)位相乘法、變換域方法、矩陣矢量相乘法、Matlab 求解等。特別的有限長序列的卷積是實(shí)際數(shù)字系統(tǒng)中常見的運(yùn)算，其卷積結(jié)果仍是有限長序列。本文首先介紹線性卷積和循環(huán)卷積的基本定義，進(jìn)而針對(duì)有限長序列的循環(huán)卷積的計(jì)算進(jìn)行方法總結(jié)和梳理，并結(jié)合實(shí)際例子說明各類方法的應(yīng)用過程。

2 線性卷積與循環(huán)卷積

2.1 有限長序列的線性卷積與循環(huán)卷積

有限長序列x1(n)(0≤n≤N1-1) 和x2(n)(0≤n≤N2-1)的線性卷積[6]yl(n)為：

即兩個(gè)有限長序列的線性卷積，其序列長度不會(huì)超過N1+N2-1。

上述兩有限長序列的L點(diǎn)循環(huán)卷積[6]yc(n)定義為：

則兩有限長序列的循環(huán)卷積與線性卷積的關(guān)系[6]為：

即循環(huán)卷積是線性卷積以L為周期進(jìn)行延拓后構(gòu)成序列的主值序列。當(dāng)滿足L≥N1+N2-1時(shí)，循環(huán)卷積和線性卷積一致，否則，部分時(shí)刻的卷積和序列會(huì)混疊。

2.2 循環(huán)卷積各類計(jì)算方法總結(jié)及對(duì)比

考慮到循環(huán)卷積與線性卷積的聯(lián)系，有限長序列的循環(huán)卷積可借鑒線性卷積的方法實(shí)現(xiàn)，包括定義法、圖解法、對(duì)位相乘法、矩陣矢量相乘法、變換域方法和利用Matlab的求解方法等。表1 總結(jié)了目前有限長序列循環(huán)卷積的主要求解方法[1-3,6]，并對(duì)其進(jìn)行簡要介紹。

表1 有限長序列循環(huán)卷積求解方法總結(jié)表

上述方法中基于定義式的計(jì)算方法直接從定義出發(fā)，是最基本的一類方法，過程較為煩瑣。對(duì)位相乘法、豎式計(jì)算法、序號(hào)和匹配法以及圖解法等這類方法均是基于循環(huán)卷積的基本定義，對(duì)參與卷積的序列進(jìn)行適當(dāng)?shù)呐判?、移位、相乘和疊加來進(jìn)行的，其本質(zhì)是一致的，只是在序列的排列和計(jì)算順序上有所區(qū)別。其中，基于線性卷積和循環(huán)卷積關(guān)系的對(duì)位相乘法最直觀簡便，可以直接從線性卷積的結(jié)果進(jìn)行適當(dāng)?shù)难h(huán)移位及疊加后得到循環(huán)卷積結(jié)果。

矩陣與矢量相乘法，其關(guān)鍵是構(gòu)建循環(huán)卷積矩陣[6]，由式(2)定義循環(huán)卷積矩陣：

則循環(huán)卷積得到的序列yc(n)可由矩陣C與x1(n)構(gòu)成的列矢量相乘求得：

同理，由交換律，也可由序列x1(n) 構(gòu)造相應(yīng)的循環(huán)卷積矩陣來實(shí)現(xiàn)計(jì)算。

變換域方法，則首先計(jì)算補(bǔ)零后的x1(n)和x2(n)的L點(diǎn)DFT，分別為X1(k)和X2(k)，其結(jié)果逐點(diǎn)相乘并進(jìn)行逆變換求解循環(huán)卷積序列，該方法可借助快速傅里葉變換實(shí)現(xiàn)。

最后，應(yīng)用Matlab 軟件也是求解循環(huán)卷積的常用方法，根據(jù)是否直接調(diào)用內(nèi)部函數(shù)可以細(xì)分為直接調(diào)用方法、矩陣矢量相乘法、變換域?qū)崿F(xiàn)方法等。Matlab 中的循環(huán)卷積內(nèi)部函數(shù)為：cconv(a,b,n)，其中a和b是參與循環(huán)卷積運(yùn)算的序列矢量，n是循環(huán)卷積的點(diǎn)數(shù)。其他兩類情況則需要編寫相關(guān)的程序?qū)崿F(xiàn)，詳見文獻(xiàn)6的相關(guān)章節(jié)[6]。

3 有限長序列的循環(huán)卷積求解舉例

本節(jié)給出典型例題，并詳細(xì)介紹幾類循環(huán)卷積的求解方法。

例題1：已知序列x1(n)=和x2(n)=，計(jì)算4點(diǎn)循環(huán)卷積y(n)=x1(n)?x2(n)。

解：由于文獻(xiàn)1-3涉及的方法有類似之處，僅給出文獻(xiàn)1的方法以及其他部分方法的求解過程。

1)定義法

4點(diǎn)循環(huán)卷積的每一點(diǎn)由下式給出：

2)對(duì)位相乘法

這里的對(duì)位相乘法是在有限長序列的對(duì)位相乘法基礎(chǔ)上增加了序列的周期化得到的，即文獻(xiàn)1 中所述的豎式計(jì)算法，本題的演示過程如圖1所示。首先將兩序列右側(cè)對(duì)齊，第二個(gè)序列的每個(gè)序列值逐個(gè)與第一個(gè)序列相乘、移位并求和得到線性卷積的結(jié)果，進(jìn)而根據(jù)題意求4 點(diǎn)的循環(huán)卷積，則需要將線性卷積結(jié)果以4 為周期進(jìn)行周期化，疊加后的序列選取其0～3時(shí)間區(qū)間內(nèi)的結(jié)果就是循環(huán)卷積結(jié)果。從下列過程也可以看出，該方法直觀、簡便，同時(shí)清晰地顯示出線性卷積和循環(huán)卷積的關(guān)系。

圖1 例題1的對(duì)位相乘法計(jì)算過程

3)矩陣矢量相乘法

矩陣與矢量相乘的方法核心問題是構(gòu)造循環(huán)卷積矩陣，由式(4)可得本題中的循環(huán)卷積矩陣為：

4)變換域方法

變換域方法求解循環(huán)卷積時(shí)，首先需要求解兩序列的4點(diǎn)DFT，分別為：

將k=0,1,2,3代入，可得：

對(duì)上述序列進(jìn)行逐點(diǎn)相乘有：

Y(k)=，因此對(duì)其進(jìn)行逆變換得序列：

5)Matlab求解方法

Matlab 中的循環(huán)卷積的計(jì)算函數(shù)為cconv(a,b,n)，設(shè)置輸入?yún)?shù)可以直接求解，本例中兩序列、線性卷積和循環(huán)卷積的波形如圖2所示。

圖2 循環(huán)卷積的Matlab求解波形圖

其次，該例題也可通過變換域方法實(shí)現(xiàn)，即分別計(jì)算兩序列的DFT，在變換域中頻譜相乘，再進(jìn)行逆變換，兩信號(hào)及循環(huán)卷積的序列時(shí)域和幅度譜如圖3所示。

圖3 利用DFT求解循環(huán)卷積的波形圖

再次，在Matlab中也可利用矩陣矢量相乘的方法實(shí)現(xiàn)循環(huán)卷積的求解，可利用toeplitz函數(shù)構(gòu)造循環(huán)卷積矩陣實(shí)現(xiàn)。循環(huán)卷積實(shí)現(xiàn)的程序如下[6]：

輸入已知序列后，應(yīng)用上述程序也可得到同樣的卷積結(jié)果。

例題 2：已知序列x1(n)=和x2(n)=，計(jì)算8點(diǎn)循環(huán)卷積y(n)=x1(n)?x2(n)。

解：由于本例中的序列x1(n)和x2(n)的線性卷積序列長度不超過8，因此本例中的循環(huán)卷積和線性卷積的結(jié)果一致，可借鑒線性卷積的各類方法來求解。

1)列表法

由于列表法是線性卷積的常用方法[6]，按照翻轉(zhuǎn)、移位、相乘、疊加的步驟進(jìn)行卷積運(yùn)算，下面給出列表法的計(jì)算過程：

表2 例題2的列表法求解

2)對(duì)位相乘法

將兩序列右邊對(duì)齊，依次相乘、移位、疊加，此例題中線性卷積和循環(huán)卷積的結(jié)果一致。

圖4 例題2的對(duì)位相乘法計(jì)算過程

3)Matlab求解方法

由于本題的特殊性，除直接調(diào)用conv(a,b,n)函數(shù)實(shí)現(xiàn)該例題的卷積運(yùn)算外，也可通過變換域方法實(shí)現(xiàn)，其程序如下所示：

輸入序列x1(n)和x2(n)后，應(yīng)用上述程序可得：y(n)=。該題目中各序列的波形如圖5所示：

圖5 例題2中序列和卷積結(jié)果的波形圖

上述例題的求解過程再次驗(yàn)證了線性卷積和循環(huán)卷積的關(guān)系，以及此類運(yùn)算的本質(zhì)。對(duì)應(yīng)不同的求解思路，在Matlab中也有相應(yīng)的實(shí)現(xiàn)方法，即可直接調(diào)用內(nèi)部函數(shù)，也可通過變換域方法、矩陣矢量相乘的方法來求解。若循環(huán)卷積的點(diǎn)數(shù)大于等于線性卷積的長度時(shí)，則可應(yīng)用線性卷積的方法直接計(jì)算獲得。

4 結(jié)束語

循環(huán)卷積是數(shù)字信號(hào)處理課程中的重要知識(shí)點(diǎn)，也是本課程學(xué)習(xí)的難點(diǎn)之一，循環(huán)卷積與線性卷積有密切聯(lián)系，當(dāng)循環(huán)卷積的點(diǎn)數(shù)大于等于線性卷積長度時(shí)，二者結(jié)果一致，否則會(huì)發(fā)生混疊，因此利用循環(huán)卷積求解線性卷積時(shí)，需注意點(diǎn)數(shù)的選擇。利用循環(huán)卷積的定義及其與線性卷積的關(guān)系，本文梳理并總結(jié)了已有的有限長序列循環(huán)卷積的各類求解方法，并給出了相關(guān)例題，以幫助學(xué)生掌握并理解循環(huán)卷積的基本特點(diǎn)和求解思路。涉及到的方法也是信號(hào)處理課程中各類信號(hào)和系統(tǒng)分析的常用思路，包括時(shí)域和變換域等，此類方法總結(jié)也有利于學(xué)生融會(huì)貫通，從整體上更好地掌握所學(xué)知識(shí)。