19fft_v102.pptVIP免费

CopyrigDSPC5000DSPC5000Chapter19Chapter19FastFourierTransformFastFourierTransformCopyrigSIEE,Slide2DiscreteFourierTransformDiscreteFourierTransformAllowsustocomputeanapproximationofAllowsustocomputeanapproximationoftheFourierTransformonadiscretesetoftheFourierTransformonadiscretesetoffrequenciesfromadiscretesetoftimefrequenciesfromadiscretesetoftimesamples.samples.WhereWherekkaretheindexofthediscretearetheindexofthediscretefrequenciesandfrequenciesandnntheindexofthetimesamplestheindexofthetimesamplesdtetxfXftj2)()(dtetxfXftj2)()(1,,1,0for210NkenxkXnNkjNn1,,1,0for210NkenxkXnNkjNnCopyrigSIEE,Slide3InverseDiscreteFourierTransformInverseDiscreteFourierTransformTheinverseformulaTheinverseformulais:is:Where,again,Where,again,kkaretheindexofthediscretearetheindexofthediscretefrequenciesandfrequenciesandnntheindexofthetimetheindexofthetimesamples.samples.Wehavethefollowingproperties:Wehavethefollowingproperties:DiscretetimeperiodicspectraDiscretetimeperiodicspectraPeriodictimediscretespectraPeriodictimediscretespectra1,,1,0for1210NnekXNnxnNkjNk1,,1,0for1210NnekXNnxnNkjNkCopyrigSIEE,Slide4DFTComputationDFTComputationWecanwritetheDFT:WecanwritetheDFT:Weneed:Weneed:N(N-1)N(N-1)complex‘complex‘+’+’NN22complex‘complex‘×’×’NjNneNknxkX2Nkn-N10Wwith1,,1,0forWNjNneNknxkX2Nkn-N10Wwith1,,1,0forWN+x128162561638410241047552104857640961677312016777216CopyrigSIEE,Slide5FastFourierTransform1of3FastFourierTransform1of3Cooley-Tukeyalgorithm:Cooley-Tukeyalgorithm:Basedondecimation,leadstoafactorizationofBasedondecimation,leadstoafactorizationofcomputations.computations.Letusfirstlookattheclassicalradix2Letusfirstlookattheclassicalradix2decimationintime.decimationintime.ThisparticularcaseofthealgorithmrequiresThisparticularcaseofthealgorithmrequiresthetimesequencelengtht...