基于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开发板上实现了一系列8阶到256阶的串行和并行结构FIR滤滤波器。利用ISE101在XilinxXc2vp30-波器。实验结果表明，该方法有效地减少了系统的资源消耗，提高了系统的时序性能。关键词：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）滤波器是数字信号处理系统的重要组成部分，基于

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单但这种方法增加了系统元及移位寄存单元优化了LUT结构，6OBC，Less实现的复杂度；Choi等人改进了DA-提出LUT-DA-OBC，但是这种方法的资源消耗量仍然太大；Meher等89将DA算法与Systonic结构结合，一定程度上降低了系人统功耗，提高了系统运行速度，但是资源消耗情况仍不理想。随着技术的发展需要，传统串行DA已经不能满足

8、实时要求，10朱武等人研究了并行DA在FIR滤波器设计中的应用，但这种方法是以消耗更多资源来换取速度的。采用现有分布式算法有许多优点，但还存在着两个问题：一是DA结构中LUT的规模与滤波器阶数N成指数关系，高且滤波时延和资源消耗阶时利用查找表很难实现全字运算，也将随之迅速增长；二是资源消耗和运行速度之间存在矛盾，已有并行DA能较好地解决速度问题，但必须以大量额外资本文提出一种低资源高速FIR滤波器源消耗为代价。为此，的FPGA实现方法，通过设计新的DA结构，综合采用多相分能提高系统运行速度，降低系统资源解结构及流水线等技术，消耗。1传统分布式算法N阶FIR滤波器输入输出关系为：时域中，y（n）

9、=h（k）x（nk）k=0N1（1）y（n）分别为输入输出序列；h（k）为冲击响应其中：x（n）、收稿日期：20100707；修回日期：20100904。基金项目：国家自然科学基金资助项目（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规模的目的，如图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滤波器的传统DA结构如图1所示。2基于MA型DA结构为解决LUT规模与滤波器阶数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结构更具有资源优势，两种结构消耗的面积（晶体管数量）对比情况如表1所示，表中B和m分别代表原始LUT。6表1中两个函数的定义如下：C（a，b）=42（bi）+i=a（b12ba+1）（6）（7）D（a，b，c）=2ba+1c图1传统DA结构寄存器单元和移位累加单元在表中没，因两种DA结构中，这两部分是相。由式（6）（7）易知，当滤波器阶数较（低于8阶）时，图2所示的DA结构消但MA型的DA结构，N的增大，基于图2所示DA结构消耗的资源增长迅速，而使用基于MA型DA结构消耗资源增长较慢。这样实现选用提出的DA

14、结的滤波器阶数N越高，构带来的资源优势越明显。3高阶FIR滤波器的FPGA实现阶数N增大时，滤波时延迅速加大，LUT的规模也将随之呈指数倍增长，为此，综合采用多相分解和流水线技术，把高阶FIR滤波器降阶为一系列并行低阶子滤波器之和的形式，然后采用基于MA型DA结构实现子滤波器。Z域中FIR滤波器系统函数为：图2改进输入输出单元的DA结构输入寄存部分：采用RAM资源来实现移位寄存功能，可11以节省一部分资源。移位累加器：查找表中输出值与寄存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输入时，功耗性能最优。明，k的每个字为实现速度最优，可采用全并行DA结构，即xDn+z（D1）h（nD+D1）（z1）=zDEk（z1）=kDEk（z1）（9）D1n=0Q1n0节中的各位被同时接收，这样速度可以成倍提高，设计结构如图6所示。但采用该种结构，需要的LUT、寄

16、存器和加法器也将成倍增加，这样提高速度的代价是比较昂贵的。如果系数N的数则比较好。为了达到面积最优，用图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结构使用流水线技时，术前后系统的运行速度进行了对比，结果如表4所示。从表2数据可以看出，本文方法图3LUT的DA结构基于23-降低了系统资源消耗的同时，提高了系统的处理速度，而且滤波器阶数越速度提幅越

18、大。高节省资源数目越多，1216例如相对魏灵等人提出的DA，LUT分别减少阶FIR消耗的Slice、24、10，而到256阶时，该数目达到了697、762；相对王法栋等人13提出的DA，16阶FIR速度提高了93%，128阶速度提幅达到了120%。由表3可以看出，在并行DA中本文方法在资源消耗方面优势更明显，例如16阶的FIR消耗的Slice、图4基于MA型DA结构LUT、FFs分别降低216%、233%、142%，而256阶时，该比例达到了389%、200%、408%。由此看来，利用二输入开关和加法器对结构实现LUT功能，有效地降低了系统资源消而且阶数越高资源优势越明显。耗，从表4数据可以看

19、出，使用流水系统运行速度受阶数的影线技术前，响非常大，特别是64阶以后，采用流Fmax随着阶数N的增加水线技术前，迅速降低，而使用流水线技术后，系统运行速度大大提高，平均运行速度达到了原来的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实现方法：首先采用多相分解结构、流水线等技术，把其降阶为一系列并行低阶子降低了系统运算量，提高了系统运行速度；然滤波器之和的形式，后利用提出的基于MA型DA结构实现子滤波器，解决了LUT与阶数N之间的矛盾，进一步节省了资源消耗