一種分段卷積快速算法的設計與實現

摘 要：常用的線性卷積方法要求兩個輸入序列的持續時間相同，但在實際工程中經常會遇到某個輸入序列具有較長持續時間的情況，從而無法達到信號“實時”處理的要求。在這種情況下，分段卷積是一種有效的解決方案。設計了一種分段卷積快速算法模塊，在FPGA中采用流水線結構進行實時處理。經檢驗該方法正確且能很好地滿足對信號進行實時處理的要求。

關鍵詞：分段卷積；實時處理；重疊相加法;FPGA

中圖分類號：TN911.72 文獻標識碼：B 文章編號：1004373X(2008)1714602

Design and Implementation of a Fast Algorithm of Partition Convolution

CHEN Yue

(College of Jincheng，Nanjing University of Aeronautics and Astronautics，Nanjing，211156，China)

Abstract：The linear convolution usually needs two finite-time input sequences，but in the actual application，one of the input sequences is very long，so linear convolution can′t process the data in a real-time.On this situation，the partition convolution is an effective solution.This paper proposes a fast algorithm of partition convolution module，using pipeline structure in FPGA to real-time operate the data.The practical results indicate that this method is correct and effective.

Keywords：partition convolution;real-time processing;overlap-add method;FPGA

1 引 言

在理論上，信號x(n)(長度為M)通過數字系統h(n)(長度為N)后得到輸出y(n)(長度為M+N－1)，其中y(n)=x(n)*h(n)。在實際工程中，這兩個輸入序列的長度可能相差很大，如NM。在這種情況下，常采用快速線性卷積的方法來完成數據的處理，該方法是先將長序列x(n)存儲完畢之后再和短序列h(n)做卷積運算^［1，2］。但是，這樣做存在以下兩個問題：

(1) 需要對短序列h(n)補充零點使其長度和長序列x(n)一致，這樣必然帶來計算機存儲量和存儲空間的增加；

(2) 需要等待長序列x(n)全部產生之后才能將其輸入系統并處理，這樣必然使得整個系統存在較大的延時，不能實現對信號進行“實時”處理的要求。

為了解決這個問題，本文設計了一種工程應用型的準實時處理快速線性卷積的方法，即采用分段卷積^［3，4］的設計思想將長序列x(n)分解成若干個較小的段，如每段長為L，得xk(n)，k=1，2，…M/L。然后對每一個輸入段xk(n)分別計算與h(n)做卷積得到的相應的輸出yk(n)，并將yk(n)按一定的規則首尾相加，即可得到完整的輸出y(n)。由于數字系統的單位抽樣響應h(n)一般比較短(如FIR數字濾波器)，這樣做即可以實現數字信號的“實時”處理要求。

根據分段方式的不同，分段卷積法分為重疊相加法(Overlap-add Method)和重疊保留法(Overlap-save Method)兩種，本文主要以前者為基礎完成設計。

2 重疊相加法的基本原理

假設x(n)的長度為M，h(n)的長度為N，且NM，將長序列x(n)按如下方式分成長度為L的連續有限長序列：

xk(n)=x(n)， kL≤n≤(k+1)L－1

0，其他 即子段之間不存在重疊。

因此，根據卷積的分配律得：y(n)=x(n)*h(n)=∑∞k=0xk(n)*h(n)

=∑∞k=0［xk(n)*h(n)］=∑∞k=0yk(n)

因此，將原始序列按不重疊分段后，x(n)和h(n)線性卷積等于各子段xk(n)和h(n)線性卷積yk(n)之和。由于xk(n)和h(n)長度分別為L和N，所以yk(n)的長度為L＋N－1。由于每一個子段的起點和后面緊鄰的子段的起點相隔L－1個點，yk(n)和yk+1(n)將有M－1個非零點重疊。因此，應該把該重疊部分加在一起才能得到正確的輸出，這也

正是重疊相加法名字的由來。

3 系統的總體結構

系統原理框圖如圖1所示，雷達信號由天線接收經微波前端折疊后，可得中頻信號x(t)，該信號經過A/D采樣后得到數字信號x(n)并緩存在FIFO中，用于后續分段卷積數據的讀取。在控制模塊的控制下，把緩存的采集數據進行分段并讀取L點數據xk(n)和干擾數據h(n)完成多次快速線性卷積，得到yk(n)，將分段卷積結果yk(n)的重疊部分相加即得x(n)直接與干擾數據h(n)卷積的結果y(n)，y(n)再經過D/A轉換為中頻干擾信號y(t)，最后經微波前端折疊后由天線發射，從而完成了一次卷積干擾。其中，虛框中為實現快速線性卷積方法的硬件平臺，其各部分功能如下：

圖1 系統原理框圖(1) 控制模塊為該系統的控制核心，它負責整個系統的邏輯控制，包括記錄x(n)的長度M，并根據M決定快速線性卷積的次數，控制重疊相加模塊進行yk(n)的疊加，實時得到y(n)等。

(2) FIFO緩沖的主要功能是把A/D采集數據進行緩沖并為后續的信號處理提供x(n)數據，適應ADC采樣時鐘和信號處理時鐘不一致性。

(3) 干擾數據h(n)是預存儲在FLASH里的被卷積數據，在實際中，使用頻域相乘的方法代替卷積，所以用Matlab^［5，6］把h(n)從時域轉換到頻域，故存儲在FLASH中為干擾數據h(n)的頻域數據，而非時域數據。

(4) 信號處理模塊的主要功能是完成原始A/D采集數據的時頻域轉換、頻域相乘和頻時域轉換操作。在實現中，基本的線性卷積采用了在頻域中相乘后轉換到時域的方法來完成快速線性卷積。該算法在硬件FPGA中實現，采用流水線式IP核來完成FFT/IFFT，頻域中把FFT結果和h(n)的頻域值相乘來完成時域上的卷積運算，達到實時處理的目的。

(5) 重疊相加模塊的主要功能是將分段卷積的重疊部分相加，即先對yk(n)進行N個周期的延時，然后每輸入一個線性卷積結果則和其N個周期前的結果相加即得最后結果y(n)。

4 分段卷積快速算法的驗證

為了驗證該分段卷積快速算法在實際應用中的正確性，可以將實際得到的結果和經Matlab計算得到的結果進行對比。首先利用FPGA的虛擬邏輯分析儀Chipscope把A/D原始數據x(n)、干擾數據h(n)和卷積結果y(n)以及部分中間結果采集到計算機里，然后利用Matlab把采集到的原始數據x(n)和干擾數據h(n)進行直接卷積得到計算結果y′(n)，最后將采集到的卷積結果y(n)與計算結果y′(n)進行比較。

序列x(n)的長度M和h(n)的長度N可在FPGA編程中預先設置，但需要滿足IP核對FFT/IFFT數據長度的要求。本文中為更好的說明問題，x(n)與h(n)的長度都較短，取M=256，N=128，但在實際工程應用上可以取NM。Chipscope采集到的256點A/D原始數據x(n)、128點干擾數據h(n)以及部分中間結果y1(n)和y2(n)的數據顯示結果如圖2所示，采集到的實際分段卷積的最終結果y(n)以及利用Matlab對x(n)和h(n)進行直接卷積的結果y′(n)如圖3所示。

圖2 采集數據顯示波形從圖3中可以看出，分段卷積后的累加結果與Matlab計算的結果是大體相同的，但數值上有所區別，這是由于采用FPGA進行頻譜變換的計算精度會遠低于計算機的計算精度，因此可以認為分段卷積快速算法的計算結果與直接卷積結果是相同的。

圖3 計算結果與采集波形比較

5 結 語

本文闡述了分段卷積快速算法的實現方案。由實際使用的效果表明，該系統能夠很好地完成兩個長度相差很大的序列進行卷積，滿足對數據進行“實時”處理的要求。

參 考 文 獻

［1］Proakis J G，Manolakis D G.Introduction to Digital Signal Processing.New York:Macmillan Publishing Company，1988.

［2］Sophocles J O.Introduction to Signal Processing.Prentice-Hall，1996.

［3］胡廣書.數字信號處理［M］.北京:清華大學出版社，2004.

［4］邵朝，陰亞芳，盧光躍.數字信號處理［M］.北京:北京郵電大學出版社，2003.

［5］劉敏，魏玲.Matlab通信仿真與應用［M］.北京:國防工業出版社，2001.

［6］張志涌.精通Matlab 6.5版［M］.北京:北京航空航天大學出版社，2003.

作者簡介 陳 悅 女，1979年出生，助教，2005年畢業于南京航空航天大學信息科學與技術學院，主要研究方向為數字信號處理。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文