《電子技術應用》
您所在的位置:首頁 > 可編程邏輯 > 設計應用 > 基于RAG-n算法的低成本FIR濾波器實現
基于RAG-n算法的低成本FIR濾波器實現
2016年電子技術應用第5期
徐 紅1,葉 豐2,黃朝耿3
1.浙江工業大學 信息工程學院,浙江 杭州310023; 2.杭州國芯科技股份有限公司,浙江 杭州310012;3.浙江財經大學 信息學院,浙江 杭州310018
摘要: 基于FIR數字濾波器多常數乘法的圖表示法,利用MATLAB對RAG-n算法進行了實現。通過仿真該算法在大多數情況下都可以高效地解決加法器優化問題,有效降低了FIR濾波器常系數乘法的復雜度。在FPGA上用Verilog HDL語言對優化實例進行了實現,其綜合結果表明,該方法可以有效減少邏輯單元的消耗,適用于低成本數字系統設計。
中圖分類號: TN713
文獻標識碼: 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.
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
Abstract: 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.
Key words : FIR digital filter;graph representation of multipliers;n-dimensional reduced adder graph algorithm;FPGA

0 引言

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

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

1.1 多常數乘法

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

wdz2-t1.gif

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

1.2 多常數乘法的圖表示法

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

wdz2-t2.gif

    從圖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所示。

wdz2-t3.gif

wdz2-t4.gif

wdz2-b1.gif

    圖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。

wdz2-b2.gif

    以上系數正奇數化并且去掉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。

wdz2-b3.gif

    從表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.

此內容為AET網站原創,未經授權禁止轉載。
主站蜘蛛池模板: 高清免费国产在线观看 | 国产在线一区精品对白麻豆 | 手机看片国产免费 | 五月天丁香婷婷综合 | 四虎影视4hutv最新地址在线 | www.丁香.com| 国产青草视频免费观看97 | 高清国产性色视频在线 | www.久久99| 狠狠亚洲狠狠欧洲2019 | 女人精69xxxxx免费视频 | 久久久国产成人精品 | 国产高清在线免费观看 | 天天五月天丁香婷婷深爱综合 | 免费羞羞视频网站 | 国产二三区 | 久久精品不卡 | 日日操人人 | 精品久久久久亚洲 | 国产一级爱片 | 久草精品在线观看 | 精品一区二区三区在线播放 | 欧美中文字幕在线观看 | 王色视频在线观看免费网站 | 欧美激情精品久久久久久久九九九 | 精品在线观看国产 | 免费视频专区一国产盗摄 | 她来自台北 | 四虎com| 国产成人aa在线观看视频 | 四虎精品在线视频 | 亚洲国产成人久久精品影视 | 免费小视频在线观看 | 久久这里精品青草免费 | 国产91九色刺激露脸对白 | 成人精品视频一区二区三区 | 免费一看一级毛片全播放 | 99在线免费视频 | 一级毛片完整免费版 | 免费国产成人高清无线看软件 | 亚洲国产日韩综合久久精品 |