0 引言

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

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

1.1 多常數(shù)乘法

    圖1為FIR濾波器的轉(zhuǎn)置型結(jié)構(gòu)。

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

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

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

    從圖2我們看出：

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

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

2 RAG-n算法

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

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

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

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

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

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

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

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

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

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

    例如，原始系數(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]的代價(jià)分別為：[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]，算法結(jié)束。

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)現(xiàn)舉例

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

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

    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

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

4 硬件綜合結(jié)果

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

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

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

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

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

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

5 結(jié)論

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

參考文獻(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] 徐紅，葉豐，黃朝耿.基于子項(xiàng)空間技術(shù)的低復(fù)雜度FIR濾波器實(shí)現(xiàn)[J].電子技術(shù)應(yīng)用，2014，40(6)；33-35.