FFT的verilog实现详解

1ImplementationofFastFourierTransform(FFT)onFPGAusingVerilogHDLAnAdvanced-VLSI-Design-Lab(AVDL)Term-Project,VLSIEngineeringCourse,Autumn2004-05,Deptt.OfElectronics&ElectricalCommunication,IndianInstituteofTechnologyKharagpurUndertheguidanceofProf.SwapnaBanerjeeDeptt.OfElectronics&ElectricalCommunicationEngg.IndianInstituteofTechnologyKharagpur.SubmittedbyAbhishekKesh(02EC1014)ChintanS.Thakkar(02EC3010)RachitGupta(02EC3012)SiddharthS.Seth(02EC1032)T.Anish(02EC3014)2ACKNOWLEDGEMENTSItiswithgreatreverencethatwewishtoexpressourdeepgratitudetowardsourVLSIEngineeringProfessorandFacultyAdvisor,Prof.SwapnaBanerjee,DepartmentofElectronics&ElectricalCommunication,IndianInstituteofTechnologyKharagpur,underwhosesupervisionwecompletedourwork.Herastuteguidance,invaluablesuggestions,enlighteningcommentsandconstructivecriticismalwayskeptourspiritsupduringourwork.WewouldbeaccusedofingratitudeifwefailedtomentiontheconsistentencouragementandhelpextendedbyMr.KailashChandraRay,GraduateResearchAssistant,duringourTerm-Projectwork.ThebrainstormingsessionsatAVDLspentdiscussingvariouspossiblearchitecturesfortheFFTwereveryeducativeforusnoviceVLSIstudents.Ourexperienceinworkingtogetherhasbeenwonderful.Wehopethattheknowledge,practicalandtheoretical,thatwehavegainedthroughthistermprojectwillhelpusinourfutureendeavoursinthefieldofVLSI.AbhishekKeshChintanS.ThakkarRachitGuptaSiddharthS.SethT.Anish31.FASTFOURIERTRANSFORMSThenumberofcomplexmultiplicationandadditionoperationsrequiredbythesimpleformsboththeDiscreteFourierTransform(DFT)andInverseDiscreteFourierTransform(IDFT)isoforderN2asthereareNdatapointstocalculate,eachofwhichrequiresNcomplexarithmeticoperations.Forlengthninputvectorx,theDFTisalengthnvectorX,withnelements:Incomputersciencejargon,wemaysaytheyhavealgorithmiccomplexityO(N2)andhenceisnotaveryefficientmethod.Ifwecan'tdoanybetterthanthisthentheDFTwillnotbeveryusefulforthemajorityofpracticalDSPapplications.However,thereareanumberofdifferent'FastFourierTransform'(FFT)algorithmsthatenablethecalculationtheFouriertransformofasignalmuchfasterthanaDFT.Asthenamesuggests,FFTsarealgorithmsforquickcalculationofdiscreteFouriertransformofadatavector.TheFFTisaDFTalgorithmwhichreducesthenumberofcomputationsneededforNpointsfromO(N2)toO(NlogN)wherelogisthebase-2logarithm.Ifthefunctiontobetransformedisnotharmonicallyrelatedtothesamplingfrequency,theresponseofanFFTlookslikea‘sinc’function(sinx)/xThe'Radix2'algorithmsareusefulifNisaregularpowerof2(N=2p).Ifweassumethatalgorithmiccomplexityprovidesadirectmeasureofexecutiontimeandthattherelevantlogarithmbaseis2thenasshowninFig.1.1,ratioofexecutiontimesforthe(DFT)vs.(Radix2FFT)(denotedas‘SpeedImprovementFactor’)increasestremendouslywithincreaseinN.Theterm'FFT'isactuallyslightlyambiguous,becausethereareseveralcommonlyused'FFT'algorithms.TherearetwodifferentRadix2algorithms,theso-called'DecimationinTime'(DIT)and'DecimationinFrequency'(DIF)algorithms.BothoftheserelyontherecursivedecompositionofanNpointtransforminto2(N/2)pointtransforms.Thisdecompositionprocesscanbeappliedtoanycomposite(nonprime)N.ThemethodisparticularlysimpleifNisdivisibleby2andifNisaregularpowerof2,thedecompositioncanbeappliedrepeatedlyuntilthetrivial'1point'transformisreached.4Fig.1.1:ComparisonofExecutionTimes,DFT&Radix–2FFTTheradix-2decimation-in-frequencyFFTisanimportantalgorithmobtainedbythedivide-and-conquerapproach.TheFig.1.2belowshowsthefirststageofthe8-pointDIFalgorithm.Fig.1.2:FirstStageof8pointDecimationinFrequencyAlgorithm.Thedecimation,however,causesshufflingindata.Theentireprocessinvolvesv=log2Nstagesofdecimation,whereeachstageinvolvesN/2butterfliesofthetypeshownintheFig.1.3.Fig.1.3:ButterflyScheme.5HereWN=e–j2Π/N,istheTwiddlefactor.Consequently,thecomputationofN-pointDFTviathisalgorithmrequires(N/2)log2Ncomplexmultiplications.Forillustrativepurposes,theeight-pointdecimation-infrequencyalgorithmisshownintheFigurebelow.Weobserve,aspreviouslystated,thattheoutputsequenceoccursinbit-reversedorderwithrespecttotheinput.Furthermore,ifweabandontherequirementthatthecomputationsoccurinplace,itisalsopossibletohaveboththeinputandoutputinnormalorder.Fig.1.4:8pointDecimationinFrequencyAlgorithm62.ARCHITECTURE2.1ComparativeStudyOurVerilogHDLcodeimplementsan8pointdecimation-in-frequencyalgorithmusingthebutterflystructure.Thenumberofstagesvinthestructureshallbev=log2N.Inourcase,N=8andhence,thenumberofstagesisequalto3.Therearevariouswaystoimplementthesethreestages.Someofthemare,A)IterativeArchitecture-Usingonlyonestageiterativelythreetimes,onceforeverydecimationThisisahardwareefficientcircuitasthereisonlyonesetof12-bitaddersandsubtractors.Thefirststagerequiresonly2CORDICs.ThecomputationofeachCORDICtakes8clockpulses.ThesecondandthirdstagesdonotrequireanyCORDIC,althoughinthisstructuretheywillrequiretorotatedataby0oor-90ousingtheCORDIC,whichwilltake16(8forthesecondand8forthirdstage)clockpulses.Theentireprocessofrotationby0oor-90ocanratherbeeasilyachievedby2’scomplementandBUSexchangewhichwouldrequiremuchlesshardware.Besides,whileonesetofdataisbein