數(shù)字信號處理英文版課件：Chap.6 Computation of The Discrete Fourier Transform

Chap.6ComputationofTheDiscreteFourierTransform

復(fù)習(xí)1一、EfficientcomputationofDFT21.ThedirectcomputationofDFTN

ComplexmultiplicationComplexadditionsRealmultiplicationRealadditionsoneX[k]N-pointDFTN-1N(N-1)4N

2N+2(N-1)=4N-24realmultiplication2realadditions32)Complexconjugatesymmetry:

1)Periodicityinnandk:

3)

Reducibility

可約性:4)others2、Propertiesof4二、Decimation-in-timeFFTAlgorithms(DIT)51.Principal

CalculateN-DFTusingDivideNpoints

intotwo

pointssequenceLet,6ButterflyComputation:1complexmultiplication+2complexaddition——ButterflyComputation

inDIT-FFT72.N=8DIT-FFT8Stagem=0m=1m=2group421Coefficient93、Computation:Complexmultiplication:Complexaddition:DFT+:N(N-1)

104、PropertiesofDIT1)In-PlaceComputations(原位運算、同址運算)Theoutputofeverystagecanbestoredintheregisterswhichstoringtheinputdata.SoNregistersarenecessary.112、Bit-reversedorder(倒位序)Input:bit-reversedorder.Output:normalordernormalorderbinarydigits(n2n1n0)bit-reservedbinarydigits(n0n1n2)bit-reservedorder0000000010011004201001023011110641000011510110156110011371111117123）Distancebetweentwosourcenodesofonebutterfly

Stagem=0m=1m=2Distance12413三、Decimation-in-frequencyFFTAlgorithms

(DIF)141.Principal

CalculateN-DFTusing15——ButterflyComputation

inDIF-FFT2complexaddition+1complexmultiplication162.8-pointDIF-FFT:17Stagem=0m=1m=2group124Coefficient183.Computation:Complexmultiplication:Complexaddition:DFT+:N(N-1)

194.PropertiesofDIF1）In-PlaceComputations(原位運算、同址運算)2）Bit-reversedorder(倒位序)Output:bit-reversedorder.Input:normalorder203）Distancebetweentwosourcenodesofonebutterfly

Stagem=0m=1m=2Distance42121四、ComparisonofDIT-FFTandDIF-FFT221.IdeaDIT-FFT:

dividetheinputsequencex[n]intosmallerandsmallersubsequencesDIF-FFT:

dividetheoutputsequenceX[k]intosmallerandsmallersubsequences232.ButterflycomputationisdifferentDIT-FFT:

DIF-FFT:

(fig.9.11)

(fig.9.21)

243.Structuresaretransposedeachother