一種分段卷積快速算法的設(shè)計與實現(xiàn)

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

關(guān)鍵詞：分段卷積；實時處理；重疊相加法;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)通過數(shù)字系統(tǒng)h(n)(長度為N)后得到輸出y(n)(長度為M+N－1)，其中y(n)=x(n)*h(n)。在實際工程中，這兩個輸入序列的長度可能相差很大，如NM。在這種情況下，常采用快速線性卷積的方法來完成數(shù)據(jù)的處理，該方法是先將長序列x(n)存儲完畢之后再和短序列h(n)做卷積運算^{［1，2］}。但是，這樣做存在以下兩個問題：

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

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

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

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

2 重疊相加法的基本原理

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

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

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

因此，根據(jù)卷積的分配律得：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個非零點重疊。因此，應(yīng)該把該重疊部分加在一起才能得到正確的輸出，這也

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

3 系統(tǒng)的總體結(jié)構(gòu)

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

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

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

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

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

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

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

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

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

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

圖3 計算結(jié)果與采集波形比較

5 結(jié) 語

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

參 考 文 獻

［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］胡廣書.數(shù)字信號處理［M］.北京:清華大學(xué)出版社，2004.

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

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

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

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

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