BMIE_DSP_Chap4

2013/9/291Chapter4FastFourierTransformLishengXU2013/9/292Chap4FastFourierTransform(FFT)4.1Outline4.3Radix-2decimation-in-frequency(DIF)FFT4.2Radix-2decimation-in-time(DIT)FFT4.4Measurestoreducecomputation4.5Split-radixmethods210()()NjnkNnXkxneπ−−==∑2013/9/293000001210242(_1)012(1)(1)(1)NNNNNN−−−−−Review:DFTNW0,1,...,1nN=−10()()NnkNnXkxnW−==∑0,1,...,1kN=−matrixNN×(0)(1)(2)(1)XXXXN=−(0)(1)(2)(1)xxxxN−4.1Outline2013/9/294000001210242(_1)012(1)(1)(1)NNNNNN−−−−−(0)(1)(2)(1)XXXXN=−(0)(1)(2)(1)xxxxN−ItneedsN2timescomplexmultiplicationandN(N-1)timescomplexaddition!2421,212():10241048576():512,262144!xnNNxnnNNN===＝，＝4.1Outline2013/9/295CooleyJW,TukeyJW.AnalgorithmforthemachinecomputationofcomplexFourierseries.MathematicsofComputation,1965,pp297~301hugeamountofcalculationslowspeedofcomputersDFTisanessentialtoolinDSP!!FindfastalgorithmFastFourierTransform4.1Outline2013/9/296FastFourierTransform(FFT)•ThemultiplicationcalculatedamountreducesfromN2toe.g.WhenN=1024,themultiplicationcalculatedamountis5120,just4.88%oftheoriginal.2log2NNUsefullinksonFFT://sep://momonga.t.u-tokyo.ac.jp/~ooura/fft.html（or）~ooura/fftlinks.html•FFTisanotheralgorithmofDFT,isnotanewtransform!2013/9/297DFT:10)()0,1,1NnknXkxnWkN−===−∑（2/jNWeπ−＝PrincipleofFFTReview----Euler'sfocormsusinlajejθθθ=[phone]......jjjjjeejeejeππππ===−=−=30424111......NNNNWWjWWjW==−=−==2013/9/29810)()0,1,1NnknXkxnWkN−===−∑（PrincipleofFFTDFT:nkNW2()()symmetry:periodicity:NnknkNNnkNknNnkNNN=−==SomanyrepetitiveoperationinDFT.Thepropertiesabovecanbeusedtosimplifythecalculation22kkNNWW=2013/9/299111111(0)111111(2)(1)1)11(13WxWxWxWx−=−−−−−4-pointDFT11111111(0)11(1)(2)1111(3)11xWWxxxWW−−=−−−−0000012302460369(0)(0)(1)(1)(2)(2)(3)(3)=2013/9/291011(0)[(0)(2)][(1)(3)](1)[(0)(2)][(1)(3)](2)[(0)(2)][(1)(3)](3)[(0)(2)][(1)(3)]XxxxxXxxxxWXxxxxXxxxxW=+++=−+−=+−+=−−−1−1−(0)(2)xx(1)(3)xx(0)(1)XX(2)(3)XX1−1−(0)(2)xx+(0)(2)xx−(1)(3)xx+(1)(3)xx−11111111(0)(0)(1)11(2)(2)(1)1111(3)(3)11XxXWWxXxXxWW−−=−−−−11(0)[(0)(2)][(1)(3)](1)[(0)(2)][(1)(3)](2)[(0)(2)][(1)(3)](3)[(0)(2)][(1)(3)]XxxxxXxxxxXxxxxXxxxxWW=+++=−+−=+−+=−−−2013/9/29114.2Radix-2DITalgorithmN-pointDFTN/2-pointDFTN/4-pointDFT2-pointDFT1sequence2sequences4sequencesN/2sequencesDecimation-in-timealgorithms(DIT)Decimation-in-frequencyalgorithms(DIF）Decimationmethods2013/9/2912Forexample,N=8x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)x(0)x(4)x(2)x(6)x(3)x(7)x(1)x(5)x(1)x(0)x(5)x(6)x(4)x(7)x(2)x(3)0thstage1ststage2ndstage4.2Radix-2DITalgorithm2013/9/291310/21/212(21)00)()(2)(21)NnknNNrkrkNNrrXkxnWxrWxrW−=−−+====++∑∑∑（Given：0,1,,21rN=−21nr=+2nr=/21/21/2/200(2)(21)NNrkkrkNNNrrxrWWxrW−−===++∑∑4.2Radix-2DITalgorithm2013/9/2914()()()0,1,,122kNNNXkAkWBkk+=−=−/21/21/2/200)(2)(21)NNrkkrkNNNrrXkxrxr−−===++∑∑(()Bk0,1,/21kN=−()Ak()Xk()Ak()BkkNW1−()2NXk+()()()0,1,,12kNNXkAkWBkk=+=−4.2Radix-2DITalgorithm2013/9/29154.2Radix-2DITalgorithm2013/9/2916X(4)~X(7)Doityourself!4-pointDFTx(0)x(2)x(4)x(6)4-pointDFTx(1)x(3)x(5)x(7)08W18W28W38WX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)Evensequence0112812823128128(0)(0)(0)(1)(1)(1)(2)(2)(2)(3)(3)(3)XXXWXXXWXXXWXXXW=+=+=+=+eg.x1(r)x2(r)SignalFlowGraphOddsequence2013/9/2917(),()AkBkarebothN/2-pointDFT,theycanalsobedividedintoN/4-pointDFT.Repeatthisprocesstillthe2-pointDFTappears.The2-pointDFThasnocomplexmultiplication./41/412(21)/2/200()(4)(42)NNlklkNNllAkxlWxlW−−+===++∑∑/41/41/4/2/400(4)(42)NNlkklkNNNllxlWWxlW−−===++∑∑(0)(0)(1)(1)(0)(1)XxxXxx=+=−ForN=2M,thesequencecanbedividedMtimes.4.2Radix-2DITalgorithm2013/9/2918()mxp()mxqrNW1−1()mxp+1()mxq+EachstagehasN/2butterflyunitslikethis.(0,1,,1)mM=−11()()()()()()rNmmmrNmmmxpxpxqWxqxpxqW++=+=−•Only1complexmultiplicationand2complexaddition.•Onlyformedbytwopoints(p&q).Andthesetwopointshavenorelationshipwithotherbutterflyunits.(In-placecomputation)4.2Radix-2DITalgorithm(0)(4)xx(2)(6)xx(1)(5)xx(3)(7)xx(0)(1)XX(2)(3)XX(4)(5)XX(6)(7)XX1−1−0(0)x1−1−0(1)x0(2)x0(3)x0(4)x0(5)x0(6)x0(7)x0m=1(0)x1(1)x1(2)x1(3)x1(4)x1(5)x1(6)x1(7)x1−1−28W1−1−28W08W08W1m=2(0)x2(1)x2(2)x2(3)x2(4)x2(5)x2(6)x2(7)x1−1−1−1−2m=18W28W38W08W3(0)x3(1)x3(2)x3(3)x3(4)x3(5)x3(6)x3(7)x4.2Radix-2DITalgorithm2013/9/2920(0)(1)XX(2)(3)XX(4)(5)XX(6)(7)XXInorderOutoforder(000)(100)(010)(110)(001)(101)(011)(111)xxxxxxxxbinary(0)(4)xx(2)(6)xx(1)(5)xx(3)(7)xxFeaturesofFFT2013/9/2921•Togettheorderofx(n)2log22NNLN=(000)(001)(010)(011)(100)(101)(110)(111)xxxxxxxx(000)(100)(010)(110)(001)(101)(011)(111)xxxxxxxx(0)(4)(2)(6)(1)(5)(3)(7)xxxxxxxx2logNLNN=•Calculatedamount：–Complexmultiplication：–Complexaddition：FeaturesofFFT2013/9/29224.3Radix-2DIFalgori