??? 摘 要: 在利用FPGA實(shí)現(xiàn)數(shù)字信號(hào)處理" title="數(shù)字信號(hào)處理">數(shù)字信號(hào)處理方面,分布式算法" title="分布式算法">分布式算法發(fā)揮著關(guān)鍵作用,與傳統(tǒng)的乘積-和結(jié)構(gòu)相比,具有并行處理的高效性特點(diǎn)。詳細(xì)研究了基于FPGA、采用分布式算法實(shí)現(xiàn)FIR數(shù)字濾波器" title="數(shù)字濾波器">數(shù)字濾波器的原理和方法,并通過Xilinx ISE在Modelsim下進(jìn)行了仿真。
??? 關(guān)鍵詞: 分布式算法? DALUT? FPGA??? FIR
?
??? 數(shù)字濾波器正在迅速地代替?zhèn)鹘y(tǒng)的由R、L、C元件和運(yùn)算放大器組成的模擬濾波器并且日益成為DSP的一種主要處理環(huán)節(jié)。FPGA也在逐漸取代ASIC和PDSP,用作前端數(shù)字信號(hào)處理的運(yùn)算(如:FIR濾波、CORDIC算法或FFT)。乘累加運(yùn)算是實(shí)現(xiàn)大多數(shù)DSP算法的重要途徑,而分布式算法則能夠大大提高乘累加運(yùn)算的效能。
1 傳統(tǒng)的乘累加結(jié)構(gòu)FIR數(shù)字濾波器基本理論
??? FIR濾波器被稱為有限長(zhǎng)脈沖響應(yīng)" title="脈沖響應(yīng)">脈沖響應(yīng)濾波器,與IIR數(shù)字濾波器相對(duì)應(yīng),它的單位脈沖響應(yīng)h(n)只有有限個(gè)數(shù)據(jù)點(diǎn)。輸入信號(hào)經(jīng)過線性時(shí)不變系統(tǒng)輸出的過程是一個(gè)輸入信號(hào)與單位脈沖響應(yīng)進(jìn)行線性卷積的過程,即:
???
式中,x(n)是輸入信號(hào),y(n)是卷積輸出,h(n)是系統(tǒng)的單位脈沖響應(yīng)??梢钥闯?,每次采樣y(n)需要進(jìn)行L次乘法和L-1次加法操作實(shí)現(xiàn)乘累加之和,其中L是濾波器單位脈沖響應(yīng)h(n)的長(zhǎng)度??梢园l(fā)現(xiàn),當(dāng)L很大時(shí),每計(jì)算一個(gè)點(diǎn),則需要很長(zhǎng)的延遲時(shí)間。
2 乘累加運(yùn)算的位寬分配
??? DSP算法最主要的就是進(jìn)行乘累加運(yùn)算。假設(shè)采樣信號(hào)的位寬用N來表示,則N位與N位的乘積結(jié)果需要2N位的寄存器來保存;如果兩個(gè)操作數(shù)都是有符號(hào)數(shù),則乘積只有2N-1個(gè)有效位,因?yàn)楫a(chǎn)生了兩個(gè)符號(hào)位。
??? 為了使累加器的結(jié)果不產(chǎn)生溢出,需要對(duì)累加器進(jìn)行冗余設(shè)計(jì),也就是說要在累加器2N的位寬上多設(shè)計(jì)出K位,累加器的長(zhǎng)度M計(jì)算方式如下(L為濾波器的長(zhǎng)度):
??? 對(duì)于無符號(hào)數(shù):M=2N+K=2N+log2L
????對(duì)于有符號(hào)數(shù):M=2N+K=2N+log2L-1
3 乘累加運(yùn)算的分布式算法原理分析
??? 得益于Xilinx FPGA查找表" title="查找表">查找表結(jié)構(gòu)的潛能,分布式算法在濾波器設(shè)計(jì)方面顯示出了很高的效率,自20世紀(jì)90年代初以來越來越受到人們的重視。分布式算法是基于查找表的一種計(jì)算方法,在利用FPGA實(shí)現(xiàn)數(shù)字信號(hào)處理方面發(fā)揮著重要的作用,可以大大提高信號(hào)的處理效率。它主要應(yīng)用于數(shù)字濾波、頻率轉(zhuǎn)換等數(shù)字信號(hào)處理的乘累加運(yùn)算。
??? 分布式算法推導(dǎo)如下:
??? 設(shè)Ak是已知常數(shù)(如濾波器系數(shù)、FFT中的正弦/余弦基本函數(shù)等),xk(n)是變量,可以看作是n時(shí)刻的第k個(gè)采樣輸入數(shù)據(jù),y(n)代表n時(shí)刻的系統(tǒng)響應(yīng)。那么它們的內(nèi)積為:
???
其中,xk(n)變量可以寫成下面的格式:
???
式中,B為數(shù)據(jù)格式的字長(zhǎng);xkb是變量的二進(jìn)制位,只有“0”和“1”兩種狀態(tài)。將(2)式代入(1)式得:
???
4 FPGA實(shí)現(xiàn)過程中查找表的構(gòu)造方法
??? 根據(jù)以上論述,括號(hào)中的每一乘積項(xiàng)代表著輸入變量的某一位與常量的二進(jìn)制“與”操作,加號(hào)代表著算術(shù)和操作,指數(shù)因子對(duì)括號(hào)中的值加權(quán)。如果事先構(gòu)造一個(gè)查找表,該表存儲(chǔ)著括號(hào)中所有可能的組合值,就可以通過所有輸入變量相對(duì)應(yīng)位的組合向量(xNb,x(N-1)b,…x1b)對(duì)該表進(jìn)行尋址,該查找表稱為DALUT。DALUT的構(gòu)造規(guī)則如表1所示。
?
??? 根據(jù)以上分析,可以得出FPGA實(shí)現(xiàn)分布式算法的硬件結(jié)構(gòu),如圖1所示。
?
5 采用分布式算法實(shí)現(xiàn)FIR數(shù)字濾波器
?? ?為了說明問題,以一個(gè)三個(gè)系數(shù)的FIR數(shù)字濾波器為例設(shè)計(jì)分布式算法,字寬也設(shè)置為三位。設(shè)FIR數(shù)字濾波器系數(shù)為:h(0)=5,h(1)=2,h(2)=3。相對(duì)應(yīng)的ADLUT表如表2所示。
?
??? 在進(jìn)行FPGA設(shè)計(jì)時(shí),該表以組件Component形式構(gòu)建,設(shè)置為ROM結(jié)構(gòu),提供輸入尋址端口table_in[2..0],輸出端口table_out[3..0]。FPGA算法的結(jié)構(gòu)圖如圖2所示。
?
??? 算法實(shí)現(xiàn)中的幾個(gè)關(guān)鍵問題為:
??? (1)采用狀態(tài)機(jī)實(shí)現(xiàn)分布式算法的狀態(tài)轉(zhuǎn)移
??? 狀態(tài)機(jī)的實(shí)現(xiàn)如圖3所示,設(shè)置三個(gè)狀態(tài)s0、s1、s2。狀態(tài)s0完成數(shù)據(jù)的裝入,數(shù)據(jù)寄存器需要成對(duì)出現(xiàn),一個(gè)完成數(shù)據(jù)的延遲,另一個(gè)完成數(shù)據(jù)的移位,并將狀態(tài)轉(zhuǎn)移到s1;狀態(tài)s1完成查找表功能、數(shù)據(jù)移位和分布式算法的乘累加運(yùn)算,數(shù)據(jù)移位一個(gè)數(shù)據(jù)寬度后將狀態(tài)轉(zhuǎn)移到s2;狀態(tài)s2完成數(shù)據(jù)的輸出,并將狀態(tài)轉(zhuǎn)移到s0。利用狀態(tài)機(jī)可以條理清楚地簡(jiǎn)化計(jì)算過程,在算法實(shí)現(xiàn)時(shí)發(fā)揮著關(guān)鍵的作用。
??? (2)系統(tǒng)時(shí)鐘與數(shù)據(jù)輸入時(shí)鐘的關(guān)系
??? 根據(jù)上述的狀態(tài)轉(zhuǎn)移關(guān)系,可以得出:每輸入一個(gè)數(shù)據(jù),在下一次數(shù)據(jù)輸入之前,需要在狀態(tài)s1停留一個(gè)數(shù)據(jù)寬度(三位)的時(shí)鐘時(shí)間,在s2停留一個(gè)時(shí)鐘的數(shù)據(jù)輸出時(shí)間。也就是說,系統(tǒng)時(shí)鐘頻率應(yīng)是數(shù)據(jù)輸入頻率的5倍,即fclkock=5fxin。
??? (3)分布式算法中的乘累加公式推導(dǎo)及核心代碼實(shí)現(xiàn)
?? ?設(shè)B是數(shù)據(jù)的字寬,Pn是分布式算法第n位的結(jié)果,則有:
???
??? 有了該關(guān)系式,就可以通過for...loop循環(huán),使用一條語句完成分布式乘累加算法。具體如下:
??? for n in 0 to B-1 loop
???? ??P:=P/2+tableout(n)*2B-1;
??? end loop;
6 算法仿真驗(yàn)證與結(jié)論
?? ?本文實(shí)現(xiàn)的FIR濾波器在Xilinx的集成開發(fā)環(huán)境ISE下利用ModelSim進(jìn)行了仿真。當(dāng)輸入數(shù)據(jù)為7,3,1...時(shí),仿真輸出依次為35,29,32,16...,與乘累加方式FIR濾波算法得出的結(jié)果完全一致。假設(shè)查找表和PDSP的通用乘法器延遲時(shí)間相同,分布式算法的等待時(shí)間是B?子,通用乘法器的等待時(shí)間是NI。可見,對(duì)于位寬較小的數(shù)據(jù)來說,分布式算法的執(zhí)行速度遠(yuǎn)高于乘累加運(yùn)算??梢?,利用FPGA實(shí)現(xiàn)分布式計(jì)算大大提高了計(jì)算的速度,在高速信號(hào)處理中發(fā)揮著重要作用。
參考文獻(xiàn)
1劉 偉,孟憲元.利用FPGA實(shí)現(xiàn)小型聲納的片上系統(tǒng)集成.電子技術(shù)應(yīng)用,2000;26(10)
2 盧 毅. VHDL與數(shù)字電路設(shè)計(jì).北京:科學(xué)出版社, 2002
3 褚振勇. FPGA設(shè)計(jì)與應(yīng)用. 西安:西安電子科技大學(xué)出版社,2002
4 程佩青.數(shù)字信號(hào)處理教程.北京:清華大學(xué)出版社,2000