0 引言

    有限沖激響應（FIR）濾波器具有能保證絕對穩(wěn)定和線性相位等優(yōu)點，在數(shù)字系統(tǒng)設計中應用廣泛。對于某一應用需求，F(xiàn)IR濾波器相對于無限沖激響應（IIR）濾波器往往需要更長的階數(shù)，從而在實現(xiàn)時需要更多的乘法和延時等操作，因此如何降低FIR濾波器的硬件實現(xiàn)成本一直具有實際的研究意義。近幾年一些研究者注重在確定參數(shù)階段就將最后的硬件實現(xiàn)成本（主要是加法器的個數(shù)）考慮進去，即在實現(xiàn)成本和頻率響應兩方面約束下進行濾波器的優(yōu)化設計。這些方法往往算法復雜，運行時間長，且不能保證得到最優(yōu)結果，因此進行實際應用的技術人員很難有效利用這些方法。更普遍的情況是對應具體的應用需求，應用MATLAB等數(shù)學工具已經(jīng)設計出滿足需求的有限字長固定系數(shù)FIR濾波器，其實現(xiàn)時的硬件成本是很多應用工程師關心的問題。因此本文著眼于固定系數(shù)的FIR濾波器實現(xiàn)問題，利用高效的RAG-n算法，降低加法器個數(shù)，從而有效降低FIR濾波器的硬件實現(xiàn)成本。

1 FIR濾波器多常數(shù)乘法的圖表示法

1.1 多常數(shù)乘法

    圖1為FIR濾波器的轉置型結構。

    如圖1所示，輸入信號首先與濾波器的各個常系數(shù)相乘后被送入延時單元，這種操作通常稱為多常數(shù)乘法（Multiple Constants Multiplication，MCM）問題。常數(shù)乘法可以通過無乘法（multiplierless）技術來實現(xiàn)，即用移位寄存器和加（減）法器代替乘法器。因此，加法器可以進一步分為乘法模塊（Multiplier Block，MB）的加法器和延遲單元的加法器（Structural Adders，SA）。一旦給定濾波器階數(shù)，延時單元和SA的數(shù)量就相對固定，因此，F(xiàn)IR濾波器實現(xiàn)復雜度主要決定于MB。

1.2 多常數(shù)乘法的圖表示法

    以常系數(shù)集合[1，7，16，21，33]為例，要實現(xiàn)與同一個輸入信號的乘法，可以用一個有向無環(huán)圖來集中產(chǎn)生所有系數(shù)乘法^[1]，如圖2所示。

    從圖2我們看出：

    (1)已經(jīng)產(chǎn)生的節(jié)點（Fundamentals）可以用來產(chǎn)生還未產(chǎn)生的系數(shù)，例如21可以通過7產(chǎn)生，只要再增加一個加法器就可以，否則單獨產(chǎn)生21需要兩個加法器：21=2⁴+2²+1。因此高效的圖表示法可以減少整個乘法模塊總的加法器個數(shù)。

    (2)不同的圖表示方式需要的加法器個數(shù)可能不同，圖2(a)用了4個加法器，而圖2(b)只用了3個加法器。

2 RAG-n算法

    RAG-n算法是一種非常高效的多常數(shù)乘法圖表示法，圖2(b)的結果就是由它得到的。RAG-n算法包含兩部分：最優(yōu)部分和啟發(fā)部分[1]。在算法執(zhí)行過程中需要用到兩個查找表：第一個表對應系數(shù)單獨實現(xiàn)時需要的最少加法器個數(shù)（即單個系數(shù)的最優(yōu)代價），第二個表對應系數(shù)最優(yōu)代價實現(xiàn)的具體方法，可能不止一種，如3=2+1或是3=4-1。

2.1 最優(yōu)部分算法流程

    “incomplete”集合初始為空；“graph”集合初始元素只有“1”；cost表示加法器代價，算法步驟如下。

    (1)將所有系數(shù)通過除以2（或-2）的操作得到對應的正奇數(shù)，其結果存入“incomplete”集合；

    (2)查表得到所有單個系數(shù)的最優(yōu)代價；

    (3)去掉“incomplete”集合中代價為零的系數(shù)以及重復的系數(shù)；

    (4)將“incomplete”集合中cost=1的系數(shù)移除并存入“graph”集合，例如7=8-1；

    (5)計算在有限字長范圍內(nèi)“graph”集合元素能產(chǎn)生的所有cost=0的正整數(shù)，存入“cost0”集合，然后進行兩兩相加（或減），如果得到了“incomplete”集合中的某一個系數(shù)，則將該系數(shù)從“incomplete”集合移除存入“graph”集合。

    (6)重復步驟(5)，直到?jīng)]有系數(shù)添加到“graph”集合。

    在上述步驟中，如果“incomplete”集合為空，即所有的系數(shù)都已經(jīng)被綜合，則算法結束。

    例如，原始系數(shù)集合=[1，7，16，-21，33，42，83]，算法執(zhí)行過程如下：

    (1)“incomplete”集合=[1，7，1，21，33，21，83]；

    (2)[1，7，1，21，33，21，83]的代價分別為：[0，1，0，2，1，2，3]；

    (3)“incomplete”集合=[7，21，33，83]；

    (4)“incomplete”集合=[21，83]，“graph”集合=[1，7，33]；

    (5)第一次執(zhí)行：“cost0”集合=[1，2，4，…；7，14，28，…；33，66，132，…]，21=14+7，所以“incomplete”集合=[83]，“graph”集合=[1，7，21，33]；

    (6)第二次執(zhí)行：“cost0”集合=[1，2，4，…；7，14，28，…；21，42，84，…；33，66，132，…]，83=84-1，所以“incomplete”集合=[]，“graph”集合=[1，7，21，33，83]，算法結束。

2.2 啟發(fā)部分算法流程

    延續(xù)2.1節(jié)流程，以下第(7)～(10)步驟為啟發(fā)部分算法流程。

    (7)如果有系數(shù)沒有在最優(yōu)部分被綜合，則是因為已有節(jié)點只通過一個加法器得不到該系數(shù)，表明該系數(shù)與現(xiàn)有節(jié)點的加法距離大于等于2，即distance≥2。首先搜索兩種distance=2的情況：

    ①該系數(shù)和已有節(jié)點值的差值是否存在cost=1的數(shù)；

    ②該系數(shù)和任意兩個節(jié)點值的差值是否存在cost=0的數(shù)；

    以上兩種情況都可以通過增加兩個加法器得到該系數(shù)。

    例如，若原始系數(shù)集合=[1，7，16，-21，33，42，83，341]，341在最優(yōu)部分不能被綜合，但是341-21=320，320是一個cost=1的數(shù)，則341=21+(1+4)×26；若原始系數(shù)集合=[1，7，16，-21，33，42，83，283]，283在最優(yōu)部分不能被綜合，但是283-(33+21)/2=256，256是一個cost=0的數(shù)，則283=(33+21)/2+256。

    (8)重復執(zhí)行步驟(6)和步驟(7)，直到?jīng)]有系數(shù)再被綜合。

    (9)如果達到這一步，說明存在與已有節(jié)點distance>2的系數(shù)或是步驟(7)中沒有被搜索到distance=2的情況，這時需要加入一些節(jié)點來增大搜索范圍，一般以單個系數(shù)cost值從小到大的順序產(chǎn)生，這個過程具有隨意性。

    (10)重復執(zhí)行步驟(6)至步驟(9)，直到所有的系數(shù)都被綜合。

    如果所有的系數(shù)都能在最優(yōu)部分被綜合，則得到的結果可以保證總的加法器個數(shù)是最少的，否則，剩下的系數(shù)將在啟發(fā)部分被綜合，不能保證結果最優(yōu)。啟發(fā)部分計算量大、計算時間長且具有隨意性。為了增強算法的實用性，我們通過MATLAB軟件設計實現(xiàn)了RAG-n算法的步驟(1)~步驟(8)，并對綜合系數(shù)占總系數(shù)的百分比進行了仿真，如圖3和圖4所示。濾波器系數(shù)的數(shù)目從10到80間隔10取值，字長從6到12間隔2取值，每個點隨機產(chǎn)生500組濾波器系數(shù)用RAG-n算法進行優(yōu)化，最后將百分比結果進行統(tǒng)計平均，得到一個仿真點的值，具體數(shù)值如表1所示。

    圖4和表1的仿真結果表明，一般情況下步驟(1)~步驟(8)都能夠綜合大部分或者全部的系數(shù)，42.5%的結果沒有太多實際意義，因為在字長比較大的時候，階數(shù)通常比較高。因此在實際應用中，采用最優(yōu)部分加上distance=2的啟發(fā)部分可以解決絕大多數(shù)加法器優(yōu)化問題，且運行效率較高。

3 實現(xiàn)舉例

    以文獻[2]中60階濾波器S2為例，對給定系數(shù)通過MATLAB編寫的RAG-n算法進行加法器優(yōu)化，然后采用Verilog HDL語言進行濾波器的RTL級描述，并在FPGA上進行綜合比較。S2濾波器的通帶邊界頻率為0.042π，阻帶邊界頻率為0.14π，通帶波動小于0.012，阻帶波動小于0.001。具體系數(shù)見表2。

    以上系數(shù)正奇數(shù)化并且去掉cost=0的項和重復項后，需要RAG-n算法優(yōu)化的系數(shù)集合從小到大排列為：[3，5，7，11，13，47，89，91，99，193，223，229，241，273，343，421，587]，共有17個不同的奇數(shù)，所需加法器的下限為17，通過RAG-n算法優(yōu)化得到的加法器個數(shù)也是17個，而文獻[2]中通過子項共享方法得到的加法器是19個。通過Verilog HDL語言實現(xiàn)時對應的語句如下，x_in為濾波器輸入信號：

    assign x3={x_in,1′b0}+ x_in；//3=1×2¹+1

    assign x5={x_in,2′b00}+ x_in；//5=1×2²+1

    assign x7={x_in,3′b000}- x_in；//7=1×2³-1

    assign x11={x_in,3′b000}+ x3；//11=1×2³+3

    assign x13={x3,2′b00}+ x_in；//13=3×2²+1

    assign x47={x3,4′b0000}- x_in；//47=3×2⁴-1

    assign x89={x11,3′b000}+ x_in；//89=11×2³+1

    assign x91={x3,5′b00000}-x5；//91=3×2⁵-5

    assign x99={x3,5′b00000}+x3；//99=3×2⁵+3

    assign x193={x3,6′b000000}+ x_in；//193=3×2⁶+1

    assign x223={x7,5′b00000}- x_in；//223=7×2⁵-1

    assign x229={x7,5′b00000}+x5；//229=7×2⁵+5

    assign x241={x3,4′b0000}+x193；//241=3×2⁴+193

    assign x273={x91,1′b0}+x91；//273=91×2¹+91

    assign x343={x89,2′b00}-x13；//343=89×2²-13

    assign x421={x13,5′b00000}+x5；//421=13×2⁵+5

    assign x587={x91,2′b00}+x223；//587=91×2²+223

    以上結果通過移位操作就可以得到原系數(shù)h(n)與輸入信號x_in的多常系數(shù)乘法。

4 硬件綜合結果

    FPGA硬件資源的消耗可以通過綜合后邏輯單元（Logic Element，LE）的數(shù)量來衡量。應用3種不同的方法對上例進行實現(xiàn)比較：

    (1)直接實現(xiàn)，即輸入與濾波器系數(shù)h(n)直接相乘實現(xiàn)；

    (2)子項共享實現(xiàn)，即根據(jù)文獻[2]中的子項共享結果實現(xiàn)^[3]；

    (3)RAG-n算法優(yōu)化實現(xiàn)。

    我們分別選擇Cyclone系列的EP1C12Q240C8和APEX20KE系列的 EP20K600EBC652-3兩種型號的FPGA，綜合工具選用Quartus II，結果如表3。

    從表3可以看出，RAG-n算法由于加法器個數(shù)的減少節(jié)省了FIR濾波器FPGA硬件實現(xiàn)時的成本。

5 結論

    本文通過MATLAB編程實現(xiàn)了RAG-n算法的最優(yōu)部分和distance=2的啟發(fā)部分，并對算法的優(yōu)化實例用硬件描述語言在FPGA上進行了實現(xiàn)。RAG-n算法能有效降低加法器個數(shù)，從而有效節(jié)省FIR濾波器的硬件資源消耗，對FIR濾波器的低成本設計實現(xiàn)具有應用意義。

參考文獻

[1] DEMPSTER A G，MACLEOD M D.Use of minimum-adder multiplier blocks in FIR digital filters.Circuits and Systems II：Analog and Digital Signal Processing[J].IEEE Transactions on，1995，42(9)：569-577.

[2] YU Y J，LIM Y C.Design of linear phase FIR filters in subexpression space using mixed integer linear programming[J].IEEE Trans.Circuits Syst.I，Reg.Papers，2007，54(10)：2330-2338.

[3] 徐紅，葉豐，黃朝耿.基于子項空間技術的低復雜度FIR濾波器實現(xiàn)[J].電子技術應用，2014，40(6)；33-35.