基于線性相關(guān)的不同點循環(huán)相關(guān)計算方法

張鵬舉 戚晨皓

(東南大學(xué) 信息科學(xué)與工程學(xué)院， 南京 210096)

在“數(shù)字信號處理”課程中，相關(guān)計算占據(jù)重要地位，它在雷達(dá)、聲吶和地震波分析等信號處理中的應(yīng)用尤其廣泛[1]。它的定義類似于卷積計算，在課程教學(xué)中，線性卷積與循環(huán)卷積之間的轉(zhuǎn)化關(guān)系以及基于線性卷積的循環(huán)卷積計算方法已經(jīng)得到充分研究[2]。而相關(guān)文獻(xiàn)對于線性相關(guān)和循環(huán)相關(guān)的轉(zhuǎn)化關(guān)系以及計算方法的研究甚少，所以有必要結(jié)合相關(guān)計算和卷積計算的關(guān)系[3-4]，對其作一些探討和研究，以期達(dá)到激發(fā)學(xué)生興趣，引導(dǎo)學(xué)生對已學(xué)知識進(jìn)行延拓的目的。

首先介紹了已知的線性卷積和循環(huán)卷積的轉(zhuǎn)化關(guān)系以及基于線性卷積的循環(huán)卷積計算方法，隨后引入了線性相關(guān)和循環(huán)相關(guān)的定義[5]，并研究了循環(huán)相關(guān)、周期相關(guān)與線性相關(guān)之間的轉(zhuǎn)化關(guān)系，提出了基于線性相關(guān)的不同點數(shù)循環(huán)相關(guān)快速計算方法。最后通過Matlab實例，驗證了相比于直接根據(jù)定義計算循環(huán)相關(guān)的方法，提出的方法是有效的并且能顯著提高計算效率。

1 循環(huán)相關(guān)與線性相關(guān)之間的轉(zhuǎn)化關(guān)系

設(shè)兩個有限長序列x1(n)、x2(n)的長度分別為N1、N2，則x1(n)和x2(n)之間的線性卷積的定義為

(1)

x1(n)和x2(n)之間的循環(huán)卷積的定義為

yc(n)=x1(n)x2(n)

(2)

式(2)中，((n))L表示n對L求余數(shù)，RL(n)為矩形序列

(3)

即

(4)

(5)

則周期卷積為

(6)

從式(6)中可以看出，周期卷積是循環(huán)卷積的周期延拓，而循環(huán)卷積又是周期卷積的主值序列，因此可以通過線性卷積的計算結(jié)果得到循環(huán)卷積結(jié)果，將線性卷積進(jìn)行周期為L的周期延拓并取其主值區(qū)間0≤n≤L-1，這樣就可以得到循環(huán)卷積的結(jié)果。

受到循環(huán)卷積與線性卷積之間轉(zhuǎn)化關(guān)系的啟發(fā)，現(xiàn)推導(dǎo)循環(huán)相關(guān)與線性相關(guān)之間的轉(zhuǎn)化關(guān)系。

有限長序列x1(n)和x2(n)之間的線性相關(guān)的定義為

(7)

它反映了兩個有限長序列x1(n)和x2(n)的相似程度，式(7)表示將x1(n)右移相乘相加，n代表移位的樣本個數(shù)。線性相關(guān)包括移位、相加和相乘三種基本運算[6]。它和線性卷積運算是相似的，但是沒有線性卷積中圍繞縱軸折疊的過程。另外線性相關(guān)是不滿足交換律的，rx1x2(n)=rx1x2(-n)，當(dāng)x1(n)=x2(n)，計算得到的相關(guān)函數(shù)為自相關(guān)函數(shù)，即rx1x1(n)。

x1(n)和x2(n)之間的循環(huán)相關(guān)的定義為

(8)

周期相關(guān)的定義為

(9)

從式(9)中可以看出，與卷積相同，周期相關(guān)同樣可以看做是線性相關(guān)的周期延拓，而循環(huán)相關(guān)又是周期相關(guān)的主值序列，因此可以考慮通過線性相關(guān)計算結(jié)果得到循環(huán)相關(guān)結(jié)果。

對比線性相關(guān)和循環(huán)相關(guān)的定義式(7)和(8)可以看出，循環(huán)相關(guān)計算所涉及的移位運算是循環(huán)移位，而不是線性移位；循環(huán)相關(guān)計算中的求和是由固定的L個部分相加而成，而線性相關(guān)中的疊加項數(shù)隨序列x2(n)的長度N2而變化；循環(huán)相關(guān)必須首先確定周期L，假設(shè)兩個序列的長度分別為N1、N2，則L必須滿足L≥max{N1,N2}。如果序列長度小于L，則必須通過補零將序列長度統(tǒng)一擴展到L；循環(huán)相關(guān)的結(jié)果的長度為L，而線性相關(guān)的結(jié)果的長度為N1+N2-1，如果L≥N1+N2-1，那么線性相關(guān)和循環(huán)相關(guān)的結(jié)果相同；線性相關(guān)計算結(jié)果的下標(biāo)范圍為[0,N1+N2-2]，循環(huán)相關(guān)計算結(jié)果的下標(biāo)范圍是關(guān)于縱軸對稱的，為[-N1+1,N2-1]。

2 基于線性相關(guān)的循環(huán)相關(guān)計算方法

經(jīng)過式(9)的推導(dǎo)，在計算循環(huán)相關(guān)時，可以利用線性相關(guān)的周期延拓來計算周期相關(guān)，再取周期相關(guān)的主值區(qū)間就可以得到循環(huán)相關(guān)結(jié)果。

算法1 基于線性相關(guān)的不同點數(shù)循環(huán)相關(guān)快速計算方法輸入:rx1x2(n),L將rx1x2(n)向右或向左平移L位后的序列與rx1x2(n)相疊加得到取的主值區(qū)間[0,L-1]的數(shù)據(jù)得到L點循環(huán)卷積結(jié)果rcx1x2(n)輸出:rcx1x2(n)

(10)

3 Matlab實例

圖1 x1 (n)和x2 (n)的線性相關(guān)和循環(huán)相關(guān)的仿真示例1

圖2 x1(n)和x2(n)的線性相關(guān)和循環(huán)相關(guān)的仿真示例2

在以上兩種仿真情景下，考慮計算出滿足max{N1,N2}≤L≤N1+N2-1條件的所有點數(shù)循環(huán)相關(guān)，將根據(jù)循環(huán)卷積的定義直接計算的方法和本文提出的計算方法的運算時間進(jìn)行比較(表1)，仿真基于Matlab R2018b軟件，仿真環(huán)境為帶有3.4 GHz AMD Ryzen 5 2600的6核CPU和16 GB內(nèi)存的臺式電腦。從表1中可以看出，本文提出的方法能顯著提高計算效率。

表1 不同循環(huán)卷積計算方法的仿真運行時間對比(ms)

4 結(jié)語

“數(shù)字信號處理”課程通常只介紹線性卷積與循環(huán)卷積的等價關(guān)系的理論部分，并未涉及線性相關(guān)和循環(huán)相關(guān)，由于比較抽象，學(xué)生掌握時具有一定難度。首先引入線性卷積和循環(huán)卷積的轉(zhuǎn)化關(guān)系，通過卷積和相關(guān)的聯(lián)系，進(jìn)一步推導(dǎo)出了線性相關(guān)和卷積相關(guān)的轉(zhuǎn)化關(guān)系，并提出了基于線性相關(guān)的不同點數(shù)循環(huán)相關(guān)快速計算方法，結(jié)果表明，該算法能顯著提高計算效率。

在未來的教學(xué)研究工作中，將結(jié)合具體的應(yīng)用場景進(jìn)一步研究線性相關(guān)、循環(huán)相關(guān)、線性卷積、循環(huán)卷積的快速計算方法，充分發(fā)掘快速傅里葉變換的優(yōu)勢，提高計算效率，降低存儲量，減少運算時間。