0 引言

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

1 FIR濾波器多常數乘法的圖表示法

1.1 多常數乘法

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

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

1.2 多常數乘法的圖表示法

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

    從圖2我們看出：

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

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

2 RAG-n算法

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

2.1 最優部分算法流程

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

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

    (2)查表得到所有單個系數的最優代價；

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

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

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

    (6)重復步驟(5)，直到沒有系數添加到“graph”集合。

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

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

    (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)第一次執行：“cost0”集合=[1，2，4，…；7，14，28，…；33，66，132，…]，21=14+7，所以“incomplete”集合=[83]，“graph”集合=[1，7，21，33]；

    (6)第二次執行：“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 啟發部分算法流程

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

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

    ①該系數和已有節點值的差值是否存在cost=1的數；

    ②該系數和任意兩個節點值的差值是否存在cost=0的數；

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

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

    (8)重復執行步驟(6)和步驟(7)，直到沒有系數再被綜合。

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

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

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

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

3 實現舉例

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

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

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

4 硬件綜合結果

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

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

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

    (3)RAG-n算法優化實現。

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

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

5 結論

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

參考文獻

[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濾波器實現[J].電子技術應用，2014，40(6)；33-35.