基于FPGA分布式算法實(shí)現(xiàn)的研究

【摘 要】目前使用分布式算法是FPGA設(shè)計(jì)FIR數(shù)字濾波器常用的結(jié)構(gòu)，本文主要對(duì)基于FPGA分布式算法的三種常用實(shí)現(xiàn)結(jié)構(gòu)進(jìn)行了深入的分析與研究，在此基礎(chǔ)上，針對(duì)三種結(jié)構(gòu)存在的缺陷與不足，提出了優(yōu)化改進(jìn)方案，并分析了改進(jìn)方案的優(yōu)勢(shì)，對(duì)設(shè)計(jì)數(shù)字濾波器具有一定參考意義和實(shí)用價(jià)值。

【關(guān)鍵詞】FPGA 分布式算法（DA） 查找表 數(shù)字濾波器

一、引言

分布式算法（distributed arithmetic，DA）是在上個(gè)世紀(jì)70年代初被首次提出的，但直到Xilinx公司發(fā)明FPGA（現(xiàn)場(chǎng)可編程門(mén)陣列，F(xiàn)ield Programmable Gate Array）的查找表結(jié)構(gòu)以后，DA算法才廣泛應(yīng)用在計(jì)算乘積和之中。與傳統(tǒng)算法相比，分布式算法可以極大地減少硬件電路規(guī)模，很容易實(shí)現(xiàn)流水線處理，提高電路的執(zhí)行速度。這種方法是目前比較常用的基于FPGA設(shè)計(jì)FIR濾波器的方法。

分布式算法與傳統(tǒng)的乘法器結(jié)構(gòu)相比，因巧妙的利用ROM查找表將固定系數(shù)的乘累加運(yùn)算轉(zhuǎn)化為查表操作，消除了消耗資源的乘法器，因此，當(dāng)數(shù)據(jù)的位寬比較小時(shí)，就實(shí)現(xiàn)FIR濾波器的速度而言，DA算法要明顯比乘累加運(yùn)算快。但對(duì)于分布式算法的三種常用實(shí)現(xiàn)結(jié)構(gòu)，不論是串行的、串并結(jié)合，還是全并行流水結(jié)構(gòu)來(lái)實(shí)現(xiàn)基于DA算法的濾波器，當(dāng)階N很大時(shí)，需要的硬件資源很多，有時(shí)是不可能實(shí)現(xiàn)的，所以需要尋找一種改進(jìn)的實(shí)現(xiàn)結(jié)構(gòu)來(lái)降低硬件資源的消耗。

二、分布式算法實(shí)現(xiàn)結(jié)構(gòu)分析

DA算法能用多種的結(jié)構(gòu)來(lái)實(shí)現(xiàn)，最簡(jiǎn)單、直觀的方法如圖1所示。

下面，仔細(xì)分析一下分布式算法的性能：首先，從圖1中可以看出基于DA算法的濾波器，不需要通用乘法器。其次，基于此種結(jié)構(gòu)，由B為輸入數(shù)據(jù)的位寬，完成一次濾波需要B次累加，也即需要B個(gè)時(shí)鐘周期來(lái)完成一次運(yùn)算，所以這種結(jié)構(gòu)的濾波器對(duì)處理B較小的系統(tǒng)有比較明顯的優(yōu)勢(shì)。最后，因?yàn)榇朔N結(jié)構(gòu)的濾波器的查找表的大小有階數(shù)N決定，共需個(gè)LUT單元，又每個(gè)單元的位寬由系數(shù)的量化位寬決定，設(shè)系數(shù)量化位寬是，所以每個(gè)單元位寬為（），則共需要（）*2N字節(jié)的查找表單元，也即當(dāng)N較大時(shí)，消耗太多的LUT單元，所以這種結(jié)構(gòu)的不適合N比較大的情況。下面再分析全并行（即速度最優(yōu)化）DA算法的實(shí)現(xiàn)，其實(shí)質(zhì)是圖1的一種變換形式，即將基于DA算法的LUT復(fù)制B份，而每一份的內(nèi)容相同，這樣就可以同時(shí)對(duì)B份LUT進(jìn)行查找，同時(shí)得到B個(gè)中間結(jié)果，再對(duì)這B個(gè)結(jié)果采用加法器樹(shù)相加，就構(gòu)成了如圖2結(jié)構(gòu)的濾波器。

這種結(jié)構(gòu)的DA算法完成濾波只需要一個(gè)時(shí)鐘周期，然而，它必須消耗更多的硬件資源，如設(shè)計(jì)N階濾波器，輸入變量為B個(gè)字節(jié)，則共需（）**B字節(jié)的RAM資源，當(dāng)N更大時(shí)，消耗更多，且還要增加額外的寄存器和加法器，所以我們可知，此種結(jié)構(gòu)是以消耗硬件資源來(lái)?yè)Q取高速度，顯然是很不經(jīng)濟(jì)的做法。

基于上圖還有一種變換形式是介于上述兩種實(shí)現(xiàn)結(jié)構(gòu)之間，也即串并結(jié)合的實(shí)現(xiàn)結(jié)構(gòu)，這種結(jié)構(gòu)是把DA算法的LUT復(fù)制C份，且2<=C

綜上所述，不論是串行的、串并結(jié)合的還是全并行流水結(jié)構(gòu)來(lái)實(shí)現(xiàn)基于DA算法的濾波器，它們的每個(gè)查找樹(shù)的大小均需（）*字節(jié)的RAM，并且都有各自的缺點(diǎn)，即當(dāng)N很大時(shí)，需要的硬件資源很多，有時(shí)是不可能實(shí)現(xiàn)的。所以需要尋找一種改進(jìn)的實(shí)現(xiàn)結(jié)構(gòu)來(lái)降低硬件資源的消耗。

三、 改進(jìn)的DA解決方案

如果系數(shù)N過(guò)大，則可把系數(shù)進(jìn)行分組，再利用部分查找表并將結(jié)果相加，假設(shè)在加上流水線寄存器，顯然在沒(méi)有降低速度的情況下，卻可以極大地減少設(shè)計(jì)規(guī)模，因?yàn)椴檎冶韱卧S著濾波器系數(shù)N的增加而呈指數(shù)增加。

假設(shè)長(zhǎng)度為L(zhǎng)N，則：

可用一個(gè)DA單元結(jié)構(gòu)實(shí)現(xiàn)，且將和分配到L個(gè)獨(dú)立的N階并行DA的查找表單元中，如下式：

舉例如下，設(shè)L=4，即設(shè)計(jì)一個(gè)4N的濾波器，則需3額外的加法器，結(jié)構(gòu)如圖3：

如圖3可知，將輸入數(shù)據(jù)按階數(shù)分組，分解成L個(gè)小濾波器，顯然對(duì)于一個(gè)固定N系數(shù)的濾波器有多種不同的分組方法，即N=L×n，因此每組可有n（小濾波器的階數(shù)）個(gè)數(shù)據(jù)，分成L組，則共需要的LUT單元數(shù)為L(zhǎng)×個(gè)。分析可知，分的組數(shù)越多，所需的LUT單元數(shù)越少，但是，同時(shí)所需的加法器也增加。所以，在實(shí)際應(yīng)用中，劃分的組數(shù)要依據(jù)實(shí)際的情況來(lái)分析，節(jié)省資源是我們必須考慮的總原則。

四、結(jié)束語(yǔ)

對(duì)基于FPGA分布式算法實(shí)現(xiàn)結(jié)構(gòu)的分析和改進(jìn)，理論上可以大大提高資源的利用率，為進(jìn)一步優(yōu)化FIR數(shù)字濾波器的設(shè)計(jì)提供了新的思路。下一步可根據(jù)改進(jìn)的DA方案進(jìn)行仿真和設(shè)計(jì)，但由于濾波器本身的復(fù)雜性，其實(shí)際效果還與許多因素有關(guān)，還有待進(jìn)一步的檢驗(yàn)。

參考文獻(xiàn)：

[1]Macpherson，K N，Stewart，R W Low FPGA area multiplier blocks for full parallel FIR filters[J].Field-Programmable Technology，2004 IEEE International Conference on 2004 Page（s）

[2]王傳旭，劉云.FIR低通數(shù)字濾波器設(shè)計(jì)[J].電子測(cè)量技術(shù)，2003{4}

[3]Huang W，Krighnan V，Allred D.Design analysis of a distributed arithmetic adaptive FIR filter on an FPGA[J].U.S.Signals， SsytemsComputers， 2003， Vol.1；

[4]徐年，張劍英.基于FPGA的FIR數(shù)字濾波器的實(shí)現(xiàn)[J].煤炭工程，2007，4：