基于MA型分布式算法的高階FIR濾波器設(shè)計及其FPGA實現(xiàn)

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

2、波器摘進行降階處理，然后采用提出的基于二輸入開關(guān)和加法器對的分布式算法結(jié)構(gòu)（MA型DA結(jié)構(gòu)）實現(xiàn)降階后的FIR7ff896FPGA開發(fā)板上實現(xiàn)了一系列8階到256階的串行和并行結(jié)構(gòu)FIR濾濾波器。利用ISE101在XilinxXc2vp30-波器。實驗結(jié)果表明，該方法有效地減少了系統(tǒng)的資源消耗，提高了系統(tǒng)的時序性能。關(guān)鍵詞：FIR濾波器；MA型分布式算法；多相分解；流水線；現(xiàn)場可編程門陣列中圖分類號：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，F(xiàn)IR）濾波器是數(shù)字信號處理系統(tǒng)的重要組成部分，基于

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

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

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

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

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

11、能ROM解碼器兩種結(jié)構(gòu)消耗面積對比基于MA型DA結(jié)構(gòu)006mB(m1)30B以B位二進制補碼來表示輸入數(shù)據(jù)：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結(jié)構(gòu)C(1，m)D(1，m，B)002f（h（k）x（k）bb=0（4）ROM數(shù)據(jù)21MUX加法器f（h（k）xb（k）=其中，h（k）x（k）。bk=0N1DA通過查找表、移位累加實現(xiàn)f（h（k）xb（k），其結(jié)

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

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

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

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

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

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

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

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

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

21、術(shù)前后的最大工作頻率對比王法棟等人提出的DA13流水線前流水線后117613371013424371130012841292本文串行DA流水線前12871005423373流水線后1501143014381442并行DA結(jié)構(gòu)MHz朱武等人的并行DA10SliceLUTFFs240573112421944110121114167241382252445831035334489217593376640519094濾波器階數(shù)N3264128256魏靈等人提出的DA12流水線前流水線后1341172510724253711636165615445結(jié)語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朱武，張佳民，張智明基于并行結(jié)構(gòu)分布式算法的FIR濾波器設(shè)計J電子測量與儀器學報，2007，21(4):879211LONGAP，MIRIAArea-efficientFIRfilterdesignonFPGAsu-singdistributedarithme

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