有限長序列線性相關(guān)的快速算法研究

劉志君，戚晨皓

（1.東南大學(xué) 吳健雄學(xué)院，江蘇 南京211189；2.東南大學(xué) 信息科學(xué)與工程學(xué)院，江蘇 南京211189）

0 引言

在“數(shù)字信號處理”中，相關(guān)是一個十分重要的信號分析與處理的工具，在時延估計、隨機(jī)信號的統(tǒng)計特性分析以及隨機(jī)信號的功率譜估計等方面有著重要的應(yīng)用［1］，例如平穩(wěn)隨機(jī)信號的功率譜密度就是其自相關(guān)函數(shù)的傅里葉變換［2］。因此計算兩個有限長序列的線性相關(guān)是十分重要的內(nèi)容，而相關(guān)文獻(xiàn)對于線性相關(guān)的FFT算法研究甚少，所以有必要對其快速運(yùn)算作一些探討和研究，特別是長序列數(shù)字信號處理的快速算法，以期達(dá)到實(shí)時性的目的［3］。本文首先介紹了已有的直接FFT算法快速計算線性相關(guān)，而當(dāng)兩序列長度相差較大時，直接FFT算法的快速性不夠明顯，因此本文重點(diǎn)研究了如何利用分段求和FFT算法來計算線性相關(guān)，該算法相比于直接FFT算法顯著減少了運(yùn)算量。

1 直接FFT算法計算線性相關(guān)

1.1 直接FFT算法

設(shè)兩有限長序列x（n）、h（n）的長度分別為N、M，則x（n）與h（n）之間的線性相關(guān)的結(jié)果（又稱互相關(guān)函數(shù)）rxh（m）和rhx（m）定義為：

觀察式（1）和（2）我們可以發(fā)現(xiàn)兩種不同互相關(guān)函數(shù)之間的關(guān)系：

根據(jù)定義可以發(fā)現(xiàn)，互相關(guān)函數(shù)的長度為N+M-1，且兩個有限長序列的互相關(guān)函數(shù)有兩個［4］，但是二者之間有明顯的關(guān)聯(lián)性，即rhx（m）=rxh（-m）。如果直接使用定義計算線性相關(guān)，其運(yùn)算量為NM次乘法，時間復(fù)雜度為O（NM）。

為了利用FFT快速計算線性相關(guān)，我們需要用到線性卷積的相關(guān)內(nèi)容［2］，將rxh（m）的公式與線性卷積的公式相比較，可以得到二者的時域關(guān)系為：

根據(jù)式（4），我們就可以利用線性卷積的FFT算法［1］快速計算線性相關(guān)。這里我們還需要用到循環(huán)相關(guān)的概念，對于長度分別為N和M的有限長序列x（n）、h（n），其L點(diǎn)循環(huán)相關(guān)的結(jié)果（L≥max｛N，M｝）定義為：

式（5）中：（（·））L表示對L求余數(shù)，RL（n）為矩形序列，X（k）與Y（k）均為L點(diǎn)FFT的結(jié)果。

循環(huán)相關(guān)和線性相關(guān)的等價關(guān)系［1］為L≥N+M-1，故直接FFT算法計算線性相關(guān)的過程如下：①取L=N+M-1；②對x（n）和h（n）做L點(diǎn)FFT得到X（k）與H（k）；③然后將X*（k）與H（k）相乘得到Rxh；④對R做L點(diǎn)IFFT得到。

從上述過程來看需要3次FFT運(yùn)算，但是在實(shí)際運(yùn)用中，h（n）是設(shè)計好的參數(shù)，在設(shè)計時直接給出H（k），因此只需要2次FFT計算和第三步的L次乘法，因此得到直接FFT算法的運(yùn)算量為（Llog2L+L）次乘法［1］，時間復(fù)雜度為O（Llog2L）。

1.2 直接FFT算法運(yùn)算量的改進(jìn)

前文討論線性相關(guān)的運(yùn)算時并沒有考慮到N和M的關(guān)系對于直接FFT算法改進(jìn)程度的影響。因此需要定義一個比值

通過式（6）來討論N和M的關(guān)系對于直接FFT算法改進(jìn)程度的影響［3］。根據(jù)已經(jīng)得到的運(yùn)算量的結(jié)果我們可以得到：

當(dāng)N≈M時，可近似認(rèn)為L=N+M-1≈2N，將兩種算法的運(yùn)算量進(jìn)行比較（表1）。

表1 N與M接近時運(yùn)算量的比較

從表1中可以看出，當(dāng)N=M時，N越大，直接FFT算法的運(yùn)算量改善效果越好，在N=M≥16時，直接FFT算法的運(yùn)算量就已經(jīng)明顯小于使用定義計算的運(yùn)算量。

但是在實(shí)際的信號處理中，兩序列的長度相差較大，一般數(shù)字信號處理的單位沖激響應(yīng)h（n）較短，而數(shù)字信號x（n）的長度較長。如果使用直接FFT算法進(jìn)行計算，h（n）必須補(bǔ)很多個零值點(diǎn)，這樣一來很不經(jīng)濟(jì)，二來快速性不明顯［3］。在式（7）中，如果N?M，可以近似認(rèn)為L=N+M-1≈N，此時，如果M不變，隨著N增加到大于2M，R1值反而會增大到超過1，這意味著直接FFT算法不僅沒有起到顯著減少運(yùn)算量的作用，反而會在N大于2M時增加運(yùn)算量，這是我們所不期望的，因此需要改善FFT算法，這就是以下將重點(diǎn)介紹的分段求和FFT算法。

2 分段求和FFT算法計算線性相關(guān)

2.1 分段求和FFT算法

對于FFT算法來說，先分段計算最后求和是一種很典型的改進(jìn)計算量的方法［1］，其核心就在于將一部分乘法變?yōu)榧臃ǎ瑥亩_(dá)到減小計算量的目的，因此我們考慮設(shè)計分段求和FFT算法來快速計算長度相差較大的兩序列的互相關(guān)函數(shù)。

之后利用直接FFT算法分別計算xi（n）與h（n）的互相關(guān)函數(shù)rxih（n），但是每個rxih（n）的長度都為2M-1，而最后需要得到的結(jié)果rxh（m）長度為N+M-1，如果計算補(bǔ)零后的長度則為+M-1=（k+1）M-1，因此在最后求和時，相鄰兩個rxih（n）必然有（M-1）個點(diǎn)的值要重疊相加。

圖1 重疊相加和排列過程

根據(jù)求解過程可以得到分段求和FFT算法總的運(yùn)算量為k（W log2W+W）次乘法，其中W?2M-1，時間復(fù)雜度為O（N log2M）。

2.2 分段求和FFT算法運(yùn)算量的改進(jìn)

為反映分段求和FFT算法的改進(jìn)程度，我們再定義一個比值：

根據(jù)已經(jīng)得到的運(yùn)算量的結(jié)果我們可以得到：

當(dāng)N?M時，可近似認(rèn)為L≈N，N≈=kM，將兩種算法的運(yùn)算量進(jìn)行比較（表2）。

從表2中可以看出，當(dāng)N?M時，如果M不變，N越大，分段求和FFT算法的改善效果越好。在N=7，M=2，即x（n）長度約為h（n）長度的4倍時，分段求和FFT算法的運(yùn)算量與直接FFT算法的運(yùn)算量相當(dāng)。

在N=15，M=2，即x（n）長度約為h（n）長度的8倍時，分段求和FFT算法的運(yùn)算量就已經(jīng)明顯小于直接FFT算法的運(yùn)算量。

表2 N遠(yuǎn)大于M時運(yùn)算量的比較

3 結(jié)語

本文重點(diǎn)研究了如何利用FFT快速計算兩個有限長序列的線性相關(guān)，介紹了直接FFT算法及其運(yùn)算量的改進(jìn)，以及當(dāng)兩個序列長度相差較大時分段求和FFT算法及其運(yùn)算量的改進(jìn)，并綜合比較了兩種算法的運(yùn)算量。結(jié)果表明，相比于根據(jù)定義直接計算線性相關(guān)，直接FFT算法顯著減少了運(yùn)算量，且序列長度越長，改善效果越明顯；若參與線性相關(guān)的兩個序列長度相差較大，則相比于直接FFT算法，分段求和FFT算法具有更小的運(yùn)算量，且序列長度差距越大，改善效果越好。