劉志君，戚晨皓

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

0 引言

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

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

1.1 直接FFT算法

設(shè)兩有限長(zhǎng)序列x（n）、h（n）的長(zhǎng)度分別為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ù)的長(zhǎng)度為N+M-1，且兩個(gè)有限長(zhǎng)序列的互相關(guān)函數(shù)有兩個(gè)［4］，但是二者之間有明顯的關(guān)聯(lián)性，即rhx（m）=rxh（-m）。如果直接使用定義計(jì)算線性相關(guān)，其運(yùn)算量為NM次乘法，時(shí)間復(fù)雜度為O（NM）。

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 分段求和FFT算法

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

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

圖1 重疊相加和排列過(guò)程

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

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

為反映分段求和FFT算法的改進(jìn)程度，我們?cè)俣x一個(gè)比值：

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

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

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

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

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

3 結(jié)語(yǔ)

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