摘要： 針對在FPGA中實現(xiàn)FIR濾波器的關(guān)鍵--乘法運算的高效實現(xiàn)進行了研究，給了了將乘法化為查表的DA算法，并采用這一算法設(shè)計了FIR濾波器。通過FPGA仿零點驗證，證明了這一方法是可行和高效的，其實現(xiàn)的濾波器的性能優(yōu)于用DSP和傳統(tǒng)方法實現(xiàn)FIR濾波器。最后介紹整數(shù)的CSD表示和還處于研究階段的根據(jù)FPGA實現(xiàn)的要求改進的最優(yōu)表示。

關(guān)鍵詞： FPGA DA FIR濾波器 CSD

數(shù)字濾波器是語音與圖像處理、模式識別、雷達信號處理、頻譜分析等應用中的一種基本的處理部件，它能滿足波器對幅度和相位特性的嚴格要求，避免模擬乙波器所無法克服的電壓漂移、溫度漂移和噪聲等問題。有限沖激響應(FIR)濾波器能在設(shè)計任意幅頻特性的同時保證嚴格的線性相位特性。

目前FIR濾波器的實現(xiàn)方法有三種：利用單片通用數(shù)字濾波器集成電路、DSP器件和可編程邏輯器件實現(xiàn)。單片通用數(shù)字濾波器使用方便，但由于字長和階數(shù)的規(guī)格較少，不能完全滿足實際需要。使用DSP器件實現(xiàn)雖然簡單，但由于程序順序執(zhí)行，執(zhí)行速度必然不快。FPGA有著規(guī)整的內(nèi)部邏輯陣列和豐富的連線資源，特別適合于數(shù)字信號處理任務，相對于串行運算為主導的通用DSP芯片來說，其并行性和可擴展性更好。但長期以來，F(xiàn)PGA一直被用于系統(tǒng)邏輯或時序控制上，很少有信號處理方面的應用，其原因主要是因為在FPGA中缺乏實現(xiàn)乘法運算的有效結(jié)構(gòu)?，F(xiàn)在這個問題得到了解決，使FPGA在數(shù)字信號處理方面有了長足的發(fā)展。

圖1

1 分布式運算原理

分布式算法(DA)早在1973年就已經(jīng)被Croisier提出來了，但是直到FPGA出現(xiàn)以后，才被廣泛地應用在FPGA中計算乘積和。

一個線性時不變網(wǎng)絡(luò)的輸出可以用下式表示：

=c[0]x[0]+c[1]x[1]+…+c[N-1]x[N-1]

假設(shè)系數(shù)c[n]是已知常數(shù)，x[n]是變量，在有符號DA系統(tǒng)中假設(shè)變量x[n]的表達式如下：

式中，xb[n]表示z[叫的第b位，而x[n]也就是x的第n次采樣。于是，內(nèi)積y可以表示為：

重新分別求和（也就是分布式算法的由來），其結(jié)果如下：

從(1)式可以發(fā)現(xiàn)，分布式算法是一種以實現(xiàn)乘加運算為目的的運算方法。它與傳統(tǒng)算法實現(xiàn)乘加運算的不同在于執(zhí)行部分積運算的先后順序不同。分布式算法在實現(xiàn)乘加功能時，是通過將各輸入數(shù)據(jù)的每一對應位產(chǎn)生的部分積預先進行相加形成相應的部分積，然后再對各個部分積累加形成最終結(jié)果的，而傳統(tǒng)算法是等到所有乘積已經(jīng)產(chǎn)生之后再來相加完成乘加運算的。與傳統(tǒng)串行算法相比，分布式算法可極大地減少硬件電路的規(guī)模，提高電路的執(zhí)行速度。它的實現(xiàn)框圖如圖1(虛線為流水線寄存器)所示。

圖2

2 用分布式原理實現(xiàn)FIR濾波器

2．1 串行方式

當系統(tǒng)對速度的要求不高時，可以采用串行的設(shè)計方法，即采用一個DA表、一個并行累加器和少量的寄存器就可以了。

在用LUT實現(xiàn)串行分布式算法的時候，假設(shè)系數(shù)為8位，則DA表的規(guī)模為2N×8位。可以看到如果抽頭系數(shù)N過多，則DA表的規(guī)模將十分龐大。這是因為LUT的規(guī)模隨著地址空間的變化(也就是N的增加)而呈指數(shù)增加。例如EPFl0K20包含1152個LC，而一個27×7位的表就需要394個LC。當N過大時，一個FPGA器件就不夠用了。

為了減小規(guī)模，可以利用部分表計算，然后將結(jié)果相加。假定長度為LN的內(nèi)積為：

將和分配到L個獨立的N階并行DA的LUT之中結(jié)果如下：

如圖2所示，實現(xiàn)一個4N的DA設(shè)計需要3個次輔助加法器。表格的規(guī)模從一個2 N×B位的LUT降到4個2 N×B的位表。

如果再加上流水線寄存器，由于EPFl0K20每個LC后面都跟有一個寄存器，所以并沒有增加電路規(guī)模，而速度卻得到了提高。

2．2 并行方式

采用并行方式的好處是處理速度得到了提高。由于數(shù)據(jù)是并行輸入，所以計算速度要比串行方式快，但它的代價是硬件規(guī)模更大了。下面舉出全并行的例子。

設(shè) sum[0]=c[0]x0+[0]+c[1]x0[1]+…+c[N-1]x0[N-1]

sum[B-1]=c[B-1]xB-1[0]+c[1]xB-1[1]+…c[N-1]+xB-1[N-1]

可將(1)式改寫成如下形式

y=sum[0]+sum[1]2 1+sum[2] 2+…+sum[B-1]2 B-1 (2)

利用式(2)可得一種直觀的加法器樹，如圖3所示。

雖然硬件規(guī)模加大了，但是如果把系數(shù)的個數(shù)限制在4個或8個，再加上流水線寄存器，這個代價還是值得的。而且每張表都是相同的，不用為每個采樣都設(shè)計一張表，減小了設(shè)計量。

DA算法的主要特點，是巧妙地利用ROM查找表將固定系數(shù)的MAC運算轉(zhuǎn)化為查表操作，其運算速度不隨系數(shù)和輸入數(shù)據(jù)位數(shù)的增加而降低，而且相對直接實現(xiàn)乘法器而言在硬件規(guī)模上得到了極大的改善。利用ALTERA的FLEXl0K實現(xiàn)的16階8位系數(shù)的并行FIR濾波器，其時鐘頻率可以達到101MHz，而實現(xiàn)的16階8位系數(shù)的串行FIR濾波器，其時鐘頻率可以達到63MHz，每9個時鐘周期可完成一次計算。但是其系數(shù)是傳統(tǒng)二進制的，造成了很大的冗余(對于用逐位相加法實現(xiàn)的乘法器，當系數(shù)有一位為零時不用相加，零位越多，冗余越大)，而且查找表的大小隨著濾波器階數(shù)的增加成指數(shù)增加，雖然可以采用將大查找表分解為小查找表，但是無法從根本上解決這一問題，這些都是DA方法的缺點。后面將對FIR濾波器實現(xiàn)給出新的設(shè)計方法，進一步降低邏輯資源的消耗。

3 CSD碼及最優(yōu)化方法

一個整數(shù)X與另一整數(shù)Y的乘積的二進制表示可以寫成：

對于標準二進制，由于sn=0時的對應項Y2n并不參與累加運算，所以可以用另一種表示方法使非零元素的數(shù)量降低，從而使加法器的數(shù)目減少，降低硬件規(guī)模。有符號數(shù)字量(SD)有三重值{0，-1，+1}，如果任意兩個非零位均不相鄰，即為標準有符號數(shù)字量(CSD)。

可以證明CSD表示對給定數(shù)是唯一的并且是最少非零位的。CSD表示相對于標準二進制表示的改進在于引入了負的符號位，從而降低了非零位個數(shù)，大大降低了邏輯資源的占用(大約平均降低33％的邏輯資源)。

當用硬件實現(xiàn)時，常常限制系數(shù)位數(shù)，即每個系數(shù)與N個正(負)2的冪次之和近似。標準二進制數(shù)在整數(shù)軸上是緊密和均勻分布的，而CSD碼是非均勻分布的，其對實系數(shù)的量化誤差比標準二進制大，雖然增加N可以減小量化誤差，但是會增大邏輯資源的消耗；而且CSD表示無法應用流水線結(jié)構(gòu)，從而降低處理速度。

還可采用優(yōu)化的方法將系數(shù)先拆分成幾個因子，再實現(xiàn)具體因子。這就是最優(yōu)化的代碼。例如對系數(shù)93，93=10111012=1100101CSD。用最優(yōu)化法，系數(shù)93可以表示成93=3·31，每個因子需要一個加法器，如圖4所示。

圖4

從圖中可以看出，CSD碼需要三個加法器，而最優(yōu)法只需要兩個加法器；CSD碼的重要缺陷在于每一級加法都需要初節(jié)點參與，而最優(yōu)表示僅依賴上一級加法的結(jié)果，因此也就更適合流水線處理。Dempster等人提出了需要1到4個加法器的所有可能配置表。利用這張表，就可以合成成本在0與4個加法器之間的所有8位二進制整數(shù)。

本文首先給出了一種巧妙利用FPGA的查找表，將乘法轉(zhuǎn)化為查找表運算的DA算法，并用ALTERA的FLEXlOK器件分別實現(xiàn)了一個8位16階的串行與并行FIR濾波器，系統(tǒng)頻率分別達到63MHz與101MHz，采樣速度分別達到7MSPS與101MSPS。而DSP實現(xiàn)的FIR濾波器只能達到5MSPS，明顯低于FPGA。用傳統(tǒng)的位串行方法實現(xiàn)的一個8階8位FIR濾波器，也只能達到5MSPS，明顯低于串行式DA方法；接著，針對系數(shù)的二進制表示非零位不是最少(即實現(xiàn)系數(shù)乘法的加法器不是最少)的問題，介紹了整數(shù)的CSD表示以及最優(yōu)表示，它們可以用較小的代價和與加法器級數(shù)無關(guān)的處理速度實現(xiàn)整數(shù)乘法運算，能比DA方法用更少的邏輯資源實現(xiàn)FIR濾波器。這些算法都不同于傳統(tǒng)的設(shè)計觀念，為基于FPGA的DSP設(shè)計提出了新的思路，必將在高速FIR濾波器設(shè)計、高速FFT設(shè)計中得到廣泛的應用。隨著FPCA集成規(guī)模的不斷提高，許多復雜的數(shù)學運算已經(jīng)可以用FPCA來實現(xiàn)，利用單片F(xiàn)PGA實現(xiàn)系統(tǒng)的設(shè)想即將變?yōu)楝F(xiàn)實。

?