基于改進(jìn)分布式算法的FIR濾波器設(shè)計

王 健 冉 全 李俊俊

(武漢工程大學(xué)計算機(jī)科學(xué)與工程學(xué)院 湖北 武漢 430205)

0 引 言

FIR濾波器由于具有線性相位和設(shè)計靈活的特點，被廣泛應(yīng)用于移動通信、語音識別和醫(yī)療儀器等領(lǐng)域。隨著集成電路的不斷發(fā)展，越來越多的FIR濾波器選用現(xiàn)場可編程邏輯陣列(FPGA)作為核心器件。

傳統(tǒng)算法實現(xiàn)高階FIR濾波器要進(jìn)行大量的乘累加操作，會綜合出較多的乘法器與加法器，這些運算單元會消耗較多的邏輯資源[1]。為了降低FPGA的資源消耗，Croisier等[2]首先引入了分布式算法(DA),它是一種將部分乘累加結(jié)果預(yù)先存儲在查找表(LUT)來代替乘法器結(jié)構(gòu)的算法。Peled等[3]DA獲得了進(jìn)一步的發(fā)展，Yiu[4]通過對符號數(shù)的研究使DA的適用范圍更廣,Kammeyer[5]和Taylor[6]研究了在系統(tǒng)中DA的量化能力。Partrick等[7]在DA的結(jié)構(gòu)上進(jìn)行了分析，串行結(jié)構(gòu)DA占用較少資源，但處理速度較慢，很難達(dá)到濾波器高速實時性的要求，并行結(jié)構(gòu)DA具有高速處理信息的能力，但會消耗更多的資源[8-9]。FPGA中查找表規(guī)模大小會隨著濾波器階數(shù)大小呈指數(shù)增長，查找表規(guī)模增大也會增大濾波延時，這是不可避免的，在高階濾波器中怎樣減小LUT規(guī)模成為分布式算法的主要難題。為此提出一種新的改進(jìn)型分布式算法，能實現(xiàn)任意階數(shù)的濾波器，并能有效減小查找表的規(guī)模，使系統(tǒng)占用更少的硬件資源。

1 分布式算法

1.1 分布式算法原理與結(jié)構(gòu)

分布式算法的主要目的是簡化乘法運算[10]。它與傳統(tǒng)濾波器卷積相乘的不同在于將乘法運算進(jìn)行了分解轉(zhuǎn)化，該算法將乘法運算分解為若干加法運算和移位操作。具體來說，分布式算法將各輸入數(shù)據(jù)的二進(jìn)制格式的每一位與濾波系數(shù)相乘，會產(chǎn)生兩種已知部分積，然后根據(jù)每位二進(jìn)制數(shù)的權(quán)重對部分積進(jìn)行移位操作，累加移位后的部分積就可得到最終結(jié)果。與直接相乘相比，F(xiàn)PGA通過分布式算法綜合出來的電路中沒有使用任何的乘法器，大大降低了資源占用，運算速度也得到了提高。

一個N抽頭的FIR濾波器線性卷積方程如下：

(1)

式中：h(n)表示濾波系數(shù)為已知常量；x(n)為輸入數(shù)據(jù)。x(n)的二進(jìn)制補(bǔ)碼形式為：

(2)

式中：xb(n)為x(n)的第b位。將式(2)代入式(1)可得：

(3)

由于x(n)為有限位數(shù)據(jù)，且每位二進(jìn)制數(shù)的取值只有0、1兩種，故x(n)有2N種不同的取值，又因為濾波系數(shù)h(n)已知，所以可以通過查找表來實現(xiàn)∑h(n)xb(n)，該查找表的規(guī)模大小取決于N值。再通過不同的移位操作后進(jìn)行累加，最終得到卷積相乘的結(jié)果y。分布式算法結(jié)構(gòu)如圖1所示，該結(jié)構(gòu)由移位寄存器、查找表和移位累加模塊組成，當(dāng)?shù)刂废蛄康淖罡叻栁粸锽時，發(fā)生了溢出，此時ctrl信號為高電平，累加器的值經(jīng)過移位操作后與查找表輸出的值做相減運算。

圖1 分布式算法結(jié)構(gòu)

分布式算法可簡單概括為將每個輸入數(shù)據(jù)進(jìn)行分解，得到多個一位二進(jìn)制數(shù)，然后將所有數(shù)據(jù)的相同位進(jìn)行重組后得到查找表的地址，通過查詢查找表得到該位數(shù)據(jù)與濾波系數(shù)的乘累加結(jié)果，最后將每位數(shù)據(jù)的乘累加結(jié)果通過移位寄存器進(jìn)行二次冪加權(quán)后累加便可得到最后結(jié)果。

1.2 傳統(tǒng)優(yōu)化算法

查找表的規(guī)模會隨著N的增大而呈現(xiàn)指數(shù)級的增長，通過對查找表進(jìn)行分割，可以有效地減小查找表的規(guī)模。

假定一個N×L階濾波器，該查找表的規(guī)模大小為2NL,將查找表分割為L組，每組對應(yīng)一個大小為2N的查找表，查找表的規(guī)模就由原來的2NL減小為L×2N。由此可得：

(4)

取L=4，對應(yīng)的四分割查找表結(jié)構(gòu)如圖2所示。

圖2 分割查找表結(jié)構(gòu)

對一個N×L階的濾波器來說，分割查找表的基本思路就是將濾波器系數(shù)h(n)和輸入數(shù)據(jù)xb(n)分為L份，每份濾波系數(shù)和輸入數(shù)據(jù)乘累加后形成新的N階查找表，再將所有N階查找表進(jìn)行相加后便可得到最終結(jié)果。

2 改進(jìn)分布式算法

分割查找表雖然能大大降低查找表的規(guī)模，但當(dāng)FIR濾波器的階數(shù)為質(zhì)數(shù)時，查找表就不能直接分割了，通過遞歸的思路將一個N階的查找表進(jìn)行小幅度的降階，當(dāng)階數(shù)合適時再對查找表進(jìn)行分割。

以一個4抽頭FIR濾波器為例，根據(jù)圖1可得到如表1所示的四輸入串行結(jié)構(gòu)查找表，其中b3b2b1b0是查找表的地址向量，其值是4個二進(jìn)制數(shù)的某一相同位。

表1 四輸入串行結(jié)構(gòu)查找表

續(xù)表1

可以看出，由于查找表地址的每一位只有0和1兩種取值，查找表下半部分的值由查找表上半部分的值與濾波系數(shù)h(3)的和組成。用數(shù)學(xué)公式表示如下：

LUT(1,b2,b1,b0)=LUT(0,b2,b1,b0)+h(3)

因此該四階查找表可由一個二選一選擇器和一個三階的查找表構(gòu)成，查找表的規(guī)模縮小了一半，結(jié)構(gòu)如圖3所示。

圖3 查找表減半結(jié)構(gòu)

以此類推可以不斷地減小查找表的規(guī)模，甚至最終可以全部用全加器來代替，實現(xiàn)無查找表結(jié)構(gòu)，但這樣一來信號通過全加器逐級傳播會產(chǎn)生較大的延時，對濾波器的性能會產(chǎn)生影響，加法器的過多使用也會消耗較多的硬件資源。先對查找表進(jìn)行若干級的降級處理，然后再對查找表進(jìn)行分割能達(dá)到最好的效果，在消耗資源少的同時也有良好的濾波效果。

3 FIR濾波器設(shè)計

3.1 設(shè)置濾波器參數(shù)

通過調(diào)用MATLAB中的FDATool工具可以方便快捷地得到濾波器系數(shù)，F(xiàn)DATool中可以設(shè)置濾波器階數(shù)、采樣頻率和截止頻率等。這里選擇濾波器的響應(yīng)類型為低通濾波器，采用窗函數(shù)中的海明窗來設(shè)計濾波器，濾波器的階數(shù)為31階，此時抽頭系數(shù)為32個，采樣頻率設(shè)置為10 MHz，截止頻率設(shè)置為200 kHz。低通濾波器的參數(shù)設(shè)置如圖4所示。

圖4 FIR濾波器參數(shù)設(shè)置

設(shè)置好濾波系數(shù)后，F(xiàn)DA會直接生成相應(yīng)的濾波系數(shù)，但此時導(dǎo)出的濾波系數(shù)精度比較高，會以浮點數(shù)的形式來表示，F(xiàn)PGA只能對定點數(shù)進(jìn)行運算，所以在導(dǎo)出濾波系數(shù)之前需要對濾波系數(shù)進(jìn)行依次量化，在滿足設(shè)計的前提下，選擇16位的量化位寬，通過對濾波系數(shù)放大取整最終得到量化后的濾波系數(shù)。

3.2 濾波器仿真

仿真平臺采用Quantus和ModelSim,用Verilog語言進(jìn)行自頂向下的設(shè)計。用DDS產(chǎn)生兩路正旋波100 kHz和1 MHz的相加波形作為源波形，通過FIR濾波器將高于截止頻率的1 MHz波形過濾掉。將輸出結(jié)果設(shè)置為波形輸出，仿真結(jié)果如圖5所示。FIR_IN為濾波前的100 kHz和1 MHz的源波形，F(xiàn)IR_OUT為濾波后的信號。從仿真結(jié)果可以看出濾波效果還是非常理想的，濾波的速度也比較快。

圖5 FIR濾波器仿真結(jié)果

4 實驗結(jié)果分析

為了比較改進(jìn)后的分布式算法與傳統(tǒng)分布式算法在硬件邏輯資源上差別，分別設(shè)計了不同階數(shù)的濾波器并在Quartus中實現(xiàn)，編譯成功后顯示出的資源消耗如表2所示。

表2 不同抽頭數(shù)FIR濾波器資源消耗情況和最壞路徑延時

續(xù)表2

實驗結(jié)果表明對于不同抽頭數(shù)的FIR濾波器，分割DA相較于傳統(tǒng)DA在邏輯單元(LE)和內(nèi)存資源(Memory)上的占用顯著減小，并且抽頭數(shù)越大，減小得越明顯。對于8抽頭的內(nèi)存資源占用情況，主要是查找表規(guī)模較小，分割查找表產(chǎn)生了額外的內(nèi)存資源開銷。對于59抽頭濾波器，查找表無法進(jìn)行直接分割，所以完全分割DA在該項數(shù)據(jù)缺失。完全分割DA和改進(jìn)DA在資源的使用情況上大致相同，但改進(jìn)DA可以適用于任意抽頭數(shù)的濾波器。因此，對于抽頭數(shù)目小的濾波器，實現(xiàn)電路簡單，分割查找表對資源占用的影響不大，可以直接使用傳統(tǒng)的查找表；對于抽頭數(shù)目大的濾波器，電路結(jié)構(gòu)十分復(fù)雜，傳統(tǒng)的DA就會占用較多的硬件資源，這時就可以采用改進(jìn)分割查找表算法。

另外從表2顯示的最壞路徑延時(Slack)可以看出，傳統(tǒng)分布式算法與完全分割查找表算法的最壞路徑延時基本上相差不大，但在改進(jìn)分布式算法中的59、95和150抽頭的最壞路徑延時明顯增大，這主要由于在改進(jìn)分布式算法中使用了更多的選擇器和加法器，產(chǎn)生了更多的組合邏輯，最壞路徑延時與系統(tǒng)的最大運行時鐘頻率有很大關(guān)系，這直接影響到系統(tǒng)的性能。

5 結(jié) 語

提出一種改進(jìn)的分布式算法，能適用于任意階數(shù)的濾波器，基于該算法進(jìn)行了不同階數(shù)的濾波器仿真設(shè)計，仿真實驗結(jié)果表明濾波效果達(dá)到了預(yù)期，與傳統(tǒng)的分布式算法相比，顯著減少了邏輯單元和內(nèi)存資源的占用，但產(chǎn)生的最壞路徑延時較大，未來可通過時序約束或插入寄存器減少組合邏輯等來減小最壞路徑延時。