Optimal Combination of Number of Taps and Coefficient Bit-Width for Low Power FIR Filter Re

Realization

Jo˜aoPortela∗

EduardoCosta†

Jos´eMonteiro‡

Abstract—Thispaperaddressestheoptimization

ofFIRfiltersforlowpower.Weproposeasearchalgorithmtofindthecombinationofthenumberoftapsandcoefficientbit-widththatleadstotheminimumnumberoftotalpartialsums,andhencetotheleastpowerconsumption.WeshowthattheminimumnumberoftapsdoesnotnecessarilyleadtotheleastpowerconsumptioninfullyparallelFIRfilterarchitectures.Thisisparticularlytrueifthereductionofthebit-widthofthecoefficientsistakenintoaccount.WeshowthatpowerisdirectlyrelatedtothetotalnumberofpartialsumsintheFIRfilter,whichinturnisdeterminedbythenumberofbitssetto1inthecoefficients.Wehavedevelopedasearchalgorithmthatachievesupto36%lesspowerconsumptionwhencomparedtoanimplementationusingtheminimumnumberoftaps.

1INTRODUCTION

Weproposeinthisworkanalgorithmtoexplorethebestcombinationofcoefficientbit-widthandnumberoftaps.Thissearchcannotbeperformedefficientlywhileestimatingpowerforeachcombi-nation.Asecondmajorcontributionofthisworkistodemonstrateempiricallythatweneedonlycomputethetotalnumberof1sinthecoefficientsofeachcombinationandusethisvaluehasthecostfunctionforoursearch.Hence,giventhattherangeforthenumberoftapsandcoefficientbit-widthislimited,itispossibletouseefficientlyasimpleexhaustivesearchmethod.Weshowthatthissearchtakesnegligibletime,evenforlargeex-amples,andthatimplementationsthatconsumecloseto36%lesspowerwhencomparedtotheleastnumberoftapscanbeobtained.2

FIRFILTERDESIGN

PowerconsumptioninVLSIdigitalsignalprocess-ingsystems(DSP)hasgainedspecialattentionmainlyduetotheproliferationofhigh-performanceportablebattery-poweredelectronicdevices,suchascellularphones,laptopcomputers,etc.InDSPapplications,oneofthemostbasicoperationsareFiniteImpulseResponse(FIR)filtercomputations.Inthispaper,weproposeanewoptimizationtech-niquetoreducepowerconsumptioninparallelFIRfilterimplementations.

Powerconsumptionisdirectlyrelatedtotheamountofcomputation.Atfirst,thismayindi-catethatforalowpowerimplementation,theleastnumberoftapsthatallowsforthedesiredfilterpre-cisionshouldbeused.Oneofthecontributionsofthisworkistoshowthatthisisnotnecessarilyso.Inanimplementationthatusesshift-addersforthemultiplications,thetotalnumberoftheseelementswilldefinethepowerconsumptionofthefilter.Inturn,thenumberofshift-addersisdeterminedbythenumberofbitssetto1inthecoefficientsofthefilter.Hence,itmayhappenthatalargernumberoftapsleadstoareductioninthetotalnumberofbitssetto1inthecoefficients.

Tocompoundthisproblem,anadditionalvari-ablethathasgreatimpactinthepowerconsump-tionofthefilteristhebit-widthofthecoefficients.

∗IST/INESC-ID,†UCPel,

Inthissectionwediscussthemainaspectsre-latedtotheimplementationofalow-passbandFIRfilter,namelyitsfrequencyresponse,architectureandcoefficientcalculation.2.1

FrequencyResponse

Lisbon,Portugal,jpop@algos.inesc.pt

Pelotas,Brazil,ecosta@ucpel.tche.br

‡IST/INESC-ID,Lisbon,Portugal,jcm@algos.inesc.pt

Thecharacteristicsofdigitalfiltersareoftenspec-ifiedinthefrequencydomain.Forfrequencyselec-tivefilters,suchaslow-passandband-passfilters,thespecificationsareoftenintheformoftoleranceschemes.Atypicalspecificationofalow-passfilterisdepictedinFigure1.IntheFigure1,thedashedhorizontallinesindicatethetolerancelimits.Inthepass-band(Ws),themagnituderesponsehasalimitdeviationofs.Thewidthofthetransitionbanddetermineshowsharpthefilteris.Themagnituderesponsede-creasesmonotonicallyfromthepass-bandtothe

FIRfilteringisachievedbyconvolvingtheinputdatasampleswiththedesiredunitimpulsere-sponseofthefilter.TheoutputY[t]ofaM-tapFIRfilterisgivenbytheweightedsumoflatestM+1inputdatasamplesX[t],asshowninEqua-tion1.

M󰀂

ciX[t+M−i](1)Y[t]=

i=0

Error Allowed1+s11-ss0-sWpWsBitWidth1011121336370.600.710.780.91Number380.610.760.850.89ofTaps390.570.610.700.86400.640.770.850.93410.580.620.740.82BitWidth1011121336132NumberofTaps373839407974817910581105991129511910712811913241738099111Table2:FilterpowerconsumptioninmWasaTable3:Totalnumberofbitssetto1inthecoef-functionofthenumberoftapsandthecoefficientficients.bit-width.

(orbit-width)usedforthecoefficients.Thebe-haviorofpowerconsumptionwiththecoefficientbit-widthismonotonic,thesmallerthebit-widththelesspowerconsumption.Naturally,astheco-efficientbit-widthisreduced,theprecisionofthefilter’sfrequencyresponsealsoreduces.

WepresentinTable2thepowerestimatesforthefilterexamplediscussedabove,thistimevary-ingboththenumberoftaps(horizontally)andthecoefficientbit-width(vertically).Theemptyslotscorrespondtocombinationsthatleadtoasolutionthatviolatesthespecifiederror,andthereforearenotconsidered.Toobtainthecoefficientswithdif-ferentbit-widths,wearesimplyusingtheKaiserwindowmethodasbeforetoobtainthecoefficients,whichwethentruncateandusethemostsignif-icantbits(thesearevaluesbetween-1and1infixed-pointrepresentation).

Wecanobservefromthetablethatforagivennumberoftapspowerdecreaseswiththebit-width.Forthisexample,thebestsolutionintermsofpowerwouldbetouse39tapsandcoefficientswith10bits.3.3

PowerperBitSetto1

servethatthelowernumberscorrespondinfacttothefiltersolutionswithlowerpowerconsumption.Notethatthisrelationisnotcompletelymonotonicandsmallerrorsmayoccur.Usingjustthetotalnumberofbitssetto1,thesolutionweobtainuses41tapsand10bitsforthecoefficients(73bitssetto1).However,wehadobservedthatthebestso-lutionintermsofpowerwouldbetouse39tapsand10bits,whichpresents74bitssetto1.Thisisanegligibleerrorasthesetwosolutionspresentaboutthesamepowerconsumption,0.58mWvs.0.57mW,especiallywhencomparedtotheoriginalvalueof0.91mW.3.4

OptimizationAlgorithm

Fromthediscussionaboveweconcludethattheoptimizationprocedureshouldtesteachcombina-tionofnumberoftapsandcoefficientbit-widthforvalidityandpowerconsumption,andselectthevalidsolutionwithlowestpower.Theproblemisthatperformingpowerestimationoneachofthesecombinationsisextremelyinefficient.

WehavecomputedforasetofFIRfilterexam-pleswithdifferentconfigurationstherelationbe-tweenpowerdissipationandthetotalnumberofbitssetto1inthecoefficients,i.e.,thepowerperbitsetto1.ThefirstgraphofFigure3showsthesevaluesforthefilterexamplebeingpresented.Wehaveobservedthatforagivenfilterthisrelationispracticallyconstant.Thisindicatesthatforouroptimizationprocedure,agoodcostfunctionisthetotalnumberofbitssetto1inthecoefficients,avalueeasytoobtain.

WepresentinTable3thetotalnumberofbitssetto1forthefilterunderconsideration.Wecanob-

Usingthetotalnumberofbitssetto1asthecostfunctiontominimize,anefficientsearchcanbeperformedforthecombinationofnumberoftapsandcoefficientbit-widthcorrespondingtotheleastpowerconsumptionimplementationoftheFIRfil-ter.

ForeachnumberoftapsM,thecoefficientsarecalculatedusingtheKaiserwindowmethod[4],ac-cordingtotheuser-definedfilterparametersandallowederror.Wethenenteraloopthatstartswiththeminimumbit-widthforthecoefficients(BWmin)andsuccessivelyincreaseit,truncatingtheleastsignificantbits.Usingthetruncatedcoef-ficientstrunccoefs,theresultingtransferfunctionistestedforvalidity,byverifyingthatitdoesnotviolatethespecifiederroratanypoint.Ifavalidtransferfunctionisfound,thenweexitthisloopsinceweknowthatanyothersolutionwithlargerbit-widthwillnecessarilyincrease(ormaintain)thetotalnumberofbitssetto1.InourexperimentswehaveusedBWmin=8sincewehavenotfoundacasewherecoefficientswiththisbit-widthwouldyieldavalidtransferfunction.BWmaxcorrespondssimplytotheuntruncatedcoefficients.

Whenexitingthisinnerloop,ifthesolutionisinvalidforallbit-widththenwesimplyincreasethenumberofcoefficients.Otherwise,thetotalnumberofbitssetto1iscomputedandifitisthelowestfoundsofar,thecurrentsolutionissaved.Notethatiftwosolutionswiththesamebestcostfunctionarefound,theonewithleastnumberof

0,0090,008Power (W) / Number of 1sPower (W) / Number of 1s0,0080,0070,0060,0050,0040,0030,0020,001036373839404126272829303132333435Number of TAPSNumber of TAPS11121314Power (W) / Number of 1s0,0080,0070,0060,0050,0040,0030,0020,001030313233343536Number of TAPS151617180,0070,0060,0050,0040,0030,0020,001010111213Figure3:Relationshipbetweenpowerdissipationandthenumberofbitssetto1inthecoefficientsforfiltersA,BandC,respectively.

Wp1.81.10.51.02.20.5Ws2.11.751.52.62.60.6s0.0250.0050.00050.0010.010.05POrig0.910.620.940.460.961.84POpt0.580.590.790.360.761.32%36.34.816.022.021.028.0Inthispaperwehaveproposedasearchalgorithmtofindthecombinationofnumberoftapsandcoef-ficientbit-widththatleadstotheleastpowercon-Table4:Parametersandpower(inmW)savingssumptioninaparallelimplementationofFIRfil-ters.Wehaveshowedthatthissearchcanbeper-fortheFIRfiltersusedasbenchmarks.

formedefficientlyusingascostfunctionthenumberofbitssetto1inthecoefficients.Theresultsshow

tapsiskeptasthiswilltypicallyleadtoabestthatsignificantpowersavingsarepossiblewhensolutionintermsofpower.comparedtoasolutionthatusestheleastnumberOneopenissueistherangetouseforthenumberoftaps.oftaps,MminandMmax.ThevalueforMdeter-minedaccordingtotheKaiserwindowmethod[4]6AcknowledgmentsgivesagoodhintonMmin.However,sincevalid

solutionscanbefoundwithlessnumberofcoeffi-ThisresearchwassupportedinpartbyCAPES-cients,westartwithMminmuchlowerthanthat.BrazilandinpartbyFCT-PortugalunderprojectGiventhatourcostfunctionistrivialtocompute,POCTI.wecanevaluateveryefficientlyhundredsofsolu-tions.Therefore,weareabletotestlargevaluesReferencesforMmax.

[1]A.ErdoganandT.Arslan.HighThroughput

FIRFilterDesignforLowPowerSOCAppli-4RESULTS

cations.In13thAnnualIEEEInternationalASIC/SOCConference,pages21–24,2000.Inthissection,wepresentresultsonasetofFIRfilterswithdifferentparametersandallowederror.

Thecharacteristicsofthesefilters,pass-band(Wp),stop-band(Ws)andallowederror(s),aregiveninthefirstcolumnsofTable4.

ThelastthreecolumnsofTable4presentstheresults,comparingthepowerconsumptionofthefilterselectedfromthesearchalgorithmproposedinthispaper(Section3.4)withthefilterthatusestheleastpossiblenumberoftapsasgivenbytheKaiserwindowmethod[4].Thepowerresultspre-sentedwereobtainedusingtheswitch-levelsimu-latorSLS[5].

Weshouldstressthatforthelargestfilter,fil-terF,eachcombinationthatistestedintheinnerloopofthealgorithmdescribedinSection3.4takes12mstorunonaAMD-Duronprocessorrunningat900MHz,thusjustifyingourclaimthatthissearch

[2]A.Nannarelli,M.Re,andG.Cardarilli.Trade-offsbetweenresiduenumbersystemandtradi-tionalFIRFilters.InIEEEInternationalSym-posiumonCircuitsandSystems,May2001.[3]A.OppenheimandR.Shafer.Discrete-Time

SignalProcessing.PrenticeHallSignalProcess-ingSeries,1989.[4]J.Kaiser.NonrecursiveDigitalFilterDesign

UsingtheIO-SinhWindowFunction.InIEEEInternationalSymposiumonCircuitsandSys-tems,pages20–23,1974.[5]A.Genderen.SLS:AnEfficientSwitch-LevelTimingSimulatorUsingMin-MaxVolt-ageWaveforms.InProceedingsoftheInterna-tionalConferenceonVeryLargeScaleIntegra-tion,pages79–88,1989.

ABCDEFcanbeperformedefficiently.5

CONCLUSION