基于MA型分布式算法的高階FIR濾波器設計及其FPGA實現

1、第31卷第2期2011年2月文章編號：10019081（2011）02053304計算機應用JournalofComputerApplicationsVol31No2Feb2011doi：103724/SPJ1087201100533基于MA型分布式算法的高階FIR濾波器設計及其FPGA實現李飛，曾以成，安超群，余云霞(lifei_0924126com)（湘潭大學光電工程系，湖南湘潭411105）要：針對利用現有分布式算法在FPGA上實現高階FIR濾波器時，存在資源消耗量過大和運行速度慢等問題，提出一種新型高階FIR濾波器的FPGA實現方法。首先綜合采用多相分解結構、流水線等技術對高階FIR濾

2、波器摘進行降階處理，然后采用提出的基于二輸入開關和加法器對的分布式算法結構（MA型DA結構）實現降階后的FIR7ff896FPGA開發(fā)板上實現了一系列8階到256階的串行和并行結構FIR濾濾波器。利用ISE101在XilinxXc2vp30-波器。實驗結果表明，該方法有效地減少了系統(tǒng)的資源消耗，提高了系統(tǒng)的時序性能。關鍵詞：FIR濾波器；MA型分布式算法；多相分解；流水線；現場可編程門陣列中圖分類號：TP302文獻標志碼：AHigh-orderFIRfilterdesignonFPGAusingMAdistributedalgorithmLIFei，ZENGYi-cheng，ANChao-qu

3、n，YUYun-xia(DepartmentofPhotoelectricEngineering，XiangtanUniversity，XiangtanHunan411105，China)Abstract:Concerningtheproblemsoftoomuchresourceconsumptionandtoolowprocessingspeed，anewhigh-orderFIRfiltertargetedFieldProgrammableGateArray(FPGA)wasproposedFirstly，polyphasedecompositionarchitectureandpipe

4、linetechnologywereadoptedtodecomposehigh-orderFIRfilterintolow-orderones，andthentheproposedMAdistributedalgorithmarchitecturewasusedtoimplementthedecomposedfiltersinthemethodAseriesofserialandparallelFIRfilterswhichorderfrom8to256wereimplementedbyISE101targetedXilinxXc2vp30-7ff896FPGAdeviceTheexperi

5、mentalresultsshowthattheproposedmethodeffectivelyreducesthesystemresourceconsumptionandimprovesthetimingperformanceofthesystemKeywords:FIRfilter;MAdistributedalgorithm;polyphasedecomposition;pipelinetechnology;FieldProgrammableGateArray(FPGA)0引言有限沖激響應（FiniteImpulseResponse，FIR）濾波器是數字信號處理系統(tǒng)的重要組成部分，基于

6、MAC結構的FIR濾波器的現場可編程門陣列（FieldProgrammableGateArray，FPGA）實現，只需乘法器、加法器和移位寄存器即可，但直接而且還會影使用FPGA上的硬件乘法器不但造成資源浪費，1響濾波器的性能和速度，為此，近年來人們提出了幾種無23。按對濾波器系數的操作處理，乘法器結構這些方法可以分為兩類：一是把系數轉換為比普通二進制碼更有效的硬件碼制（如最常用CSD編碼），即把濾波器系數轉換為CSD23；二是把系數所有的可碼，通過移位和求和實現乘法操作能組合存入查找表中，然后根據采樣值確定濾波器的輸出，最具有代表性的就是分布式算法（DistributedArithmetic

7、，DA）49。Croisie等人4提出的DA，是一種利用查找表（LookUpTable，LUT）代替乘法器的算法，特別適合于以LUT為基本單元的FPGA結構。此后，許多學者對DA在濾波器設計中的White等人5提出DA-OBC法，應用進行了研究，利用XOR單但這種方法增加了系統(tǒng)元及移位寄存單元優(yōu)化了LUT結構，6OBC，Less實現的復雜度；Choi等人改進了DA-提出LUT-DA-OBC，但是這種方法的資源消耗量仍然太大；Meher等89將DA算法與Systonic結構結合，一定程度上降低了系人統(tǒng)功耗，提高了系統(tǒng)運行速度，但是資源消耗情況仍不理想。隨著技術的發(fā)展需要，傳統(tǒng)串行DA已經不能滿足

8、實時要求，10朱武等人研究了并行DA在FIR濾波器設計中的應用，但這種方法是以消耗更多資源來換取速度的。采用現有分布式算法有許多優(yōu)點，但還存在著兩個問題：一是DA結構中LUT的規(guī)模與濾波器階數N成指數關系，高且濾波時延和資源消耗階時利用查找表很難實現全字運算，也將隨之迅速增長；二是資源消耗和運行速度之間存在矛盾，已有并行DA能較好地解決速度問題，但必須以大量額外資本文提出一種低資源高速FIR濾波器源消耗為代價。為此，的FPGA實現方法，通過設計新的DA結構，綜合采用多相分能提高系統(tǒng)運行速度，降低系統(tǒng)資源解結構及流水線等技術，消耗。1傳統(tǒng)分布式算法N階FIR濾波器輸入輸出關系為：時域中，y（n）

9、=h（k）x（nk）k=0N1（1）y（n）分別為輸入輸出序列；h（k）為沖擊響應其中：x（n）、收稿日期：20100707；修回日期：20100904?；痦椖浚簢易匀豢茖W基金資助項目（60972147）；湘潭大學自然科學基金資助項目（09XZX06）。作者簡介：李飛（1984），男，山東日照人，碩士研究生，主要研究方向：信號處理與VLSI設計；曾以成（1962）男，湖南漣源人，教授，博士生導師，博士，主要研究方向：信號處理；安超群（1986），女，湖北襄樊人，碩士研究生，主要研究方向：集成電路CAD與專用電路設計；余云霞（1976），女，湖南耒陽人，講師，碩士，主要研究方向：信號處理。5

10、34計算機應用1第31卷在時間序號k時的系數。對于設計好的濾波器，h（k）是一系列已知常數，因此式（1）可表示為：y（n）=h（k）x（k）k=0N1（2）B2并將相加后的結果存器值左移一位（乘以2）后的數值相加，入寄存器。首先計算高位（高位MSB先出），再計算低位，即可進一步減少資源消累加器的值要先左移1位再相加，11耗。當b=B1時做減法運算，其余的b做加法運算。從圖2這樣的結構可以看出LUT的下半部分（即b3=1時）可由LUT的上半部分（即b3=0時）與系數h（3）的和組又可以用一個二輸入開關和一個加法器對來替代成。因此，這部分LUT，從而達到降低LUT規(guī)模的目的，如圖3所示。表1邏輯功

11、能ROM解碼器兩種結構消耗面積對比基于MA型DA結構006mB(m1)30B以B位二進制補碼來表示輸入數據：x（k）=2B1xB1（k）+x（k）2bb=0b（3）1。把式（3）xb（k）0，其中：xb（k）表示x（k）的第b位，代入式（2），得：y（n）=h（k）（2k=0B2bN1B1xB1（k）+xb（k）2bb=0B2）=2B1f（h（k）xB1（k）+改進輸入輸出單元的DA結構C(1，m)D(1，m，B)002f（h（k）x（k）bb=0（4）ROM數據21MUX加法器f（h（k）xb（k）=其中，h（k）x（k）。bk=0N1DA通過查找表、移位累加實現f（h（k）xb（k），其結

12、構LUT查找表、移位累加器單主要分為3部分：移位寄存單元、元。4階FIR濾波器的傳統(tǒng)DA結構如圖1所示。2基于MA型DA結構為解決LUT規(guī)模與濾波器階數N之間的矛盾，以及階數N帶來的時延問題，結合FPGA內部構造，可以如下設計DA結構。改進輸入寄存單元和移位累加單元，調整采樣值的計算可以得到如圖2所示的更高效DA結構。順序，圖3所示DA結構與圖2所示DA結構的LUT具有如下對稱關系：LUT（1，bk2，b1，b0）=LUT（0，bk2，b1，b0）+bk1（5）其中：k表示與LUT相連的地址線的數目。根據式（5），用上述方法反復迭代，整個LUT單元可完全可得到基于MA型DA結構，被二輸入開關和

13、加法器所代替，如圖4所示。根據FPGA內部結構分析，基于MA型的DA結構比圖2所示的DA結構更具有資源優(yōu)勢，兩種結構消耗的面積（晶體管數量）對比情況如表1所示，表中B和m分別代表原始LUT。6表1中兩個函數的定義如下：C（a，b）=42（bi）+i=a（b12ba+1）（6）（7）D（a，b，c）=2ba+1c圖1傳統(tǒng)DA結構寄存器單元和移位累加單元在表中沒，因兩種DA結構中，這兩部分是相。由式（6）（7）易知，當濾波器階數較（低于8階）時，圖2所示的DA結構消但MA型的DA結構，N的增大，基于圖2所示DA結構消耗的資源增長迅速，而使用基于MA型DA結構消耗資源增長較慢。這樣實現選用提出的DA

14、結的濾波器階數N越高，構帶來的資源優(yōu)勢越明顯。3高階FIR濾波器的FPGA實現階數N增大時，濾波時延迅速加大，LUT的規(guī)模也將隨之呈指數倍增長，為此，綜合采用多相分解和流水線技術，把高階FIR濾波器降階為一系列并行低階子濾波器之和的形式，然后采用基于MA型DA結構實現子濾波器。Z域中FIR濾波器系統(tǒng)函數為：圖2改進輸入輸出單元的DA結構輸入寄存部分：采用RAM資源來實現移位寄存功能，可11以節(jié)省一部分資源。移位累加器：查找表中輸出值與寄存H（z1）=h（k）zk=0N1k1（8）FIR濾Q是大于1的正整數，設滿足N=DQ，這里D、第2期波器的多相表示為：H（z1）=李飛等：基于MA型分布式算法

15、的高階FIR濾波器設計及其FPGA實現535h（nD+0）（zn=0Q1n=0Q1Q1D1）n+z1h（nD+1）（zn=0Q1D1）n+本文中設計濾波器為低階時Q取4，高階時Q取4的倍然后利用LUT分塊技術把其分解成4輸入LUT之和。這數，是因為FPGA里面大多數LUT為4輸入的，大量實驗研究表FPGA的資源、當LUT為4輸入時，功耗性能最優(yōu)。明，k的每個字為實現速度最優(yōu)，可采用全并行DA結構，即xDn+z（D1）h（nD+D1）（z1）=zDEk（z1）=kDEk（z1）（9）D1n=0Q1n0節(jié)中的各位被同時接收，這樣速度可以成倍提高，設計結構如圖6所示。但采用該種結構，需要的LUT、寄

16、存器和加法器也將成倍增加，這樣提高速度的代價是比較昂貴的。如果系數N的數則比較好。為了達到面積最優(yōu)，用圖4結量限制在4或8之內，構中的二輸入開關和加法器對結構代替圖6所示結構中的四輸可得到基于MA型并行DA結構。入LUT，h（nD+k）（z）n1，2，D1。其中：k=0，N階FIR濾波器被分解成D由式（9）知，經過多相分解，個子濾波器。時域中，濾波器輸出為：y（n）=Q1D14（10）實驗分析x（nD+k）h（nD+k）n=0k=0對各子濾波器采用提出的DA結構，結合加法樹流水線實現濾波輸出，設計結構如圖5所示，圖中虛線部分表技術，為了驗證本文方法的有效性，設計了一系列8階到256階的FIR濾

17、波器，分別采用串行和并行DA結構，通過ModelSimXEIII63c仿真驗證，調用ISE101綜合實現，把代7ff896FPGA上，利用Chipscope在線調試，碼下載到Xc2vp30-最后完成FPGA設計。在采用串行12DA時，與當前最先進的魏靈等人13提出的DA和王法棟等人提出的DA比較，結果如表2所示。采用并行10DA時，與朱武等人的并行DA比較，結果如表3所示。采用串行結構還對3種DA結構使用流水線技時，術前后系統(tǒng)的運行速度進行了對比，結果如表4所示。從表2數據可以看出，本文方法圖3LUT的DA結構基于23-降低了系統(tǒng)資源消耗的同時，提高了系統(tǒng)的處理速度，而且濾波器階數越速度提幅越

18、大。高節(jié)省資源數目越多，1216例如相對魏靈等人提出的DA，LUT分別減少階FIR消耗的Slice、24、10，而到256階時，該數目達到了697、762；相對王法棟等人13提出的DA，16階FIR速度提高了93%，128階速度提幅達到了120%。由表3可以看出，在并行DA中本文方法在資源消耗方面優(yōu)勢更明顯，例如16階的FIR消耗的Slice、圖4基于MA型DA結構LUT、FFs分別降低216%、233%、142%，而256階時，該比例達到了389%、200%、408%。由此看來，利用二輸入開關和加法器對結構實現LUT功能，有效地降低了系統(tǒng)資源消而且階數越高資源優(yōu)勢越明顯。耗，從表4數據可以看

19、出，使用流水系統(tǒng)運行速度受階數的影線技術前，響非常大，特別是64階以后，采用流Fmax隨著階數N的增加水線技術前，迅速降低，而使用流水線技術后，系統(tǒng)運行速度大大提高，平均運行速度達到了原來的239倍，處理速度受階數圖5高階FIR濾波器的MA型DA結構N的消極影響基本消除，滿足了工程應用中高實時性的要求。536計算機應用第31卷表2濾波器階數N8163264128256表3濾波器階數N8163264128256串行DA間資源消耗和最大工作頻率對比王法棟等人提出的DA13Fmax/MHzSliceLUT127230389794151831071191964088841603340614791338

20、1337130012841292本文串行DAFmax/MHzLUT11320129466814283041216014621501143014381442魏靈等人提出的DA12Fmax/MHzSliceLUT15124145794717923497189211563103719633803170417151725163616561544Slice12521732168013812800并行DA算法間資源消耗對比本文并行DASliceLUTFFs196449916157830247402312555110620153600828530976515132666514411308圖6表4使用流水線技

21、術前后的最大工作頻率對比王法棟等人提出的DA13流水線前流水線后117613371013424371130012841292本文串行DA流水線前12871005423373流水線后1501143014381442并行DA結構MHz朱武等人的并行DA10SliceLUTFFs240573112421944110121114167241382252445831035334489217593376640519094濾波器階數N3264128256魏靈等人提出的DA12流水線前流水線后1341172510724253711636165615445結語freepatentsonlinecom/37771

22、30html5WHITESApplicationofdistributedarithmetictodigitalsignalpro-cessing:AtutorialreviewJIEEETransactionsonAcoustics，SpeechandSignalProcessingMagazine，1989，6(3):4196CHOIJP，SHINSC，CHUNGJGEfficientROMsizereductionfordistributedarithmeticC/IEEEISCASWashington，DC:IEEEComputerSociety，2000，2:61647MEHERPK

23、Hardeware-efficientsystolizationofDA-basedcalcula-tionoffinitedigitalconvolutionJIEEETransactionsonCircuits-8:Expressbriefs，2006，53(8):707711MEHERPK，CHANDRASEKARANS，AMIRAAFPGArealiza-tionofFIRfiltersbyefficientandflexiblesystolizationusingdistrib-utedarithmeticJIEEETransactionsonSignalProcessing，200

24、8，56(7):300930179MOHANTYBK，MWTERPKNovelflexiblesystolicmesharchi-tectureforparrallelVLSLimplementationoffinitedigitalconvolutionJIETEJournalofResearch，1988，44(6):26126610朱武，張佳民，張智明基于并行結構分布式算法的FIR濾波器設計J電子測量與儀器學報，2007，21(4):879211LONGAP，MIRIAArea-efficientFIRfilterdesignonFPGAsu-singdistributedarithme

25、ticC/IEEEInternationalSymposiumonSignalProcessingandInformationTechnology，2006:24825212魏靈，楊日杰，崔旭濤基于分布式算法的數字濾波器設計J儀器儀表學報，2008，29(10):2101210413王法棟，劉宇高階數字濾波器分布式算法結構比較J聲學技術，2009，28(3):30731114WANGSEN，TANGBIN，ZHUJUNDistributedarithmeticforFIRfilterdesignonFPGAJCommunications，CircuitsandSystems，2007，13(11):62062315郭振威，彭安金多速率DAFIR濾波器的實現方法研究J現代電子技術，2006，29(5):4244本文提出了一種高階FIR濾波器的FPGA實現方法：首先采用多相分解結構、流水線等技術，把其降階為一系列并行低階子降低了系統(tǒng)運算量，提高了系統(tǒng)運行速度；然濾波器之和的形式，后利用提出的基于MA型DA結構實現子濾波器，解決了LUT與階數N之間的矛盾，進一步節(jié)省了資源消耗