文獻標識碼: A
DOI:10.16157/j.issn.0258-7998.2016.05.009
中文引用格式: 徐紅,葉豐,黃朝耿. 基于RAG-n算法的低成本FIR濾波器實現[J].電子技術應用,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.
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=24+22+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×21+1
assign x5={x_in,2′b00}+ x_in;//5=1×22+1
assign x7={x_in,3′b000}- x_in;//7=1×23-1
assign x11={x_in,3′b000}+ x3;//11=1×23+3
assign x13={x3,2′b00}+ x_in;//13=3×22+1
assign x47={x3,4′b0000}- x_in;//47=3×24-1
assign x89={x11,3′b000}+ x_in;//89=11×23+1
assign x91={x3,5′b00000}-x5;//91=3×25-5
assign x99={x3,5′b00000}+x3;//99=3×25+3
assign x193={x3,6′b000000}+ x_in;//193=3×26+1
assign x223={x7,5′b00000}- x_in;//223=7×25-1
assign x229={x7,5′b00000}+x5;//229=7×25+5
assign x241={x3,4′b0000}+x193;//241=3×24+193
assign x273={x91,1′b0}+x91;//273=91×21+91
assign x343={x89,2′b00}-x13;//343=89×22-13
assign x421={x13,5′b00000}+x5;//421=13×25+5
assign x587={x91,2′b00}+x223;//587=91×22+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.