基于RAG-n算法的低成本FIR濾波器實(shí)現(xiàn)*

徐　紅，葉　豐，黃朝耿

（1.浙江工業(yè)大學(xué) 信息工程學(xué)院，浙江 杭州 310023；2.杭州國芯科技股份有限公司，浙江 杭州310012；3.浙江財經(jīng)大學(xué) 信息學(xué)院，浙江 杭州 310018）

基于RAG-n算法的低成本FIR濾波器實(shí)現(xiàn)*

徐紅1，葉豐2，黃朝耿3

（1.浙江工業(yè)大學(xué) 信息工程學(xué)院，浙江 杭州 310023；2.杭州國芯科技股份有限公司，浙江 杭州310012；3.浙江財經(jīng)大學(xué) 信息學(xué)院，浙江 杭州 310018）

基于FIR數(shù)字濾波器多常數(shù)乘法的圖表示法，利用MATLAB對RAG-n算法進(jìn)行了實(shí)現(xiàn)。通過仿真該算法在大多數(shù)情況下都可以高效地解決加法器優(yōu)化問題，有效降低了FIR濾波器常系數(shù)乘法的復(fù)雜度。在FPGA上用Verilog HDL語言對優(yōu)化實(shí)例進(jìn)行了實(shí)現(xiàn)，其綜合結(jié)果表明，該方法可以有效減少邏輯單元的消耗，適用于低成本數(shù)字系統(tǒng)設(shè)計。

FIR數(shù)字濾波器；乘法器的圖表示法；RAG-n算法；FPGA

0　引言

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

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

1.1多常數(shù)乘法

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

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

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

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

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

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

從圖2我們看出：

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

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

2　RAG-n算法

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

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

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

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

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

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

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

(5)計算在有限字長范圍內(nèi)“graph”集合元素能產(chǎn)生的所有 cost=0的正整數(shù)，存入“cost0”集合，然后進(jìn)行兩兩相加（或減），如果得到了“incomplete”集合中的某一個系數(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]的代價分別為：[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)只通過一個加法器得不到該系數(shù)，表明該系數(shù)與現(xiàn)有節(jié)點(diǎn)的加法距離大于等于 2，即distance≥2。首先搜索兩種distance=2的情況：

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

②該系數(shù)和任意兩個節(jié)點(diǎn)值的差值是否存在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)重復(fù)執(zhí)行步驟(6)和步驟(7)，直到?jīng)]有系數(shù)再被綜合。

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

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

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

圖3　步驟(1)～步驟(6)（即最優(yōu)部分）綜合系數(shù)的百分比曲線

圖4　步驟(1)～步驟(8)綜合系數(shù)的百分比曲線

表1　綜合系數(shù)的百分比仿真數(shù)據(jù)

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

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

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

表2　濾波器S2的系數(shù)，h(n)=h(59-n)，30≤n≤59；通帶增益=10 945.336 1

以上系數(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個不同的奇數(shù)，所需加法器的下限為17，通過RAG-n算法優(yōu)化得到的加法器個數(shù)也是17個，而文獻(xiàn)[2]中通過子項(xiàng)共享方法得到的加法器是19個。通過 Verilog HDL語言實(shí)現(xiàn)時對應(yīng)的語句如下，x_in為濾波器輸入信號：

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

4　硬件綜合結(jié)果

FPGA硬件資源的消耗可以通過綜合后邏輯單元（Logic Element，LE）的數(shù)量來衡量。應(yīng)用3種不同的方法對上例進(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兩種型號的FPGA，綜合工具選用Quartus II，結(jié)果如表3。

表3　FPGA綜合結(jié)果比較

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

5　結(jié)論

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

Implementation of low-cost FIR digital filters based on RAG-n algorithm

Xu Hong1，Ye Feng2，Huang Chaogeng3
（1.College of Information Engineering，Zhejiang University of Technology，Hangzhou 310023，China；2.Hangzhou Nationalchip Science&Technology Co.Ltd.，Hangzhou 310012，China；3.School of Information，Zhejiang University of Finance&Economics，Hangzhou 310018，China）

Based on graph representation of multiple constants multiplication,RAG-n algorithm is implemented by MATLAB.RAG-n algorithm can solve optimization problem of adder number in most cases efficiently,and reduce the complexity of FIR filter constant coefficient multiplication.The results of FPGA hardware synthesis show that this method can greatly reduce the number of logic elements applicable to low-cost design of digital systems.

FIR digital filter；graph representation of multipliers；n-dimensional reduced adder graph algorithm；FPGA

TN713

A

10.16157/j.issn.0258-7998.2016.05.009

浙江省自然科學(xué)基金（LY16F030057），國家科技支撐計劃課題（2013BAF07B00）

2015-10-08)

徐紅(1978-)，女，工學(xué)碩士，講師，主要研究方向：數(shù)字濾波器設(shè)計、FPGA及 ASIC開發(fā)技術(shù)。

葉豐(1975-)，男，技術(shù)總監(jiān)，主要研究方向：數(shù)字電視技術(shù)、集成電路設(shè)計。

中文引用格式：徐紅，葉豐，黃朝耿.基于 RAG-n算法的低成本 FIR濾波器實(shí)現(xiàn)[J].電子技術(shù)應(yīng)用，2016，42(5)：32-35.

英文引用格式：Xu Hong，Ye Feng，Huang Chaogeng.Implementation of low-cost FIR digital filters based on RAG-n algorithm[J]. Application of Electronic Technique，2016，42(5)：32-35.