Chap.6ComputationofTheDiscreteFourierTransformcontents§6.1EfficientcomputationofDFT§6.2Decimation-in-timeFFTalgorithms(DIT)§6.3Decimation-in-frequencyFFTalgorithms(DIF)

§6.4FastIDFTalgorithms§6.1EfficientcomputationofDFT一、ThecomputationofDFT1.CompareDFTwithIDFT

2.ThedirectcomputationofDFTN

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

2N+2(N-1)=4N-24realmultiplication2realadditionse.g.N:

Complexmultiplication:

8

64

1024

1048576Theamountofcomputation(thecomputationtime)requiredtocomputetheDFTbythedirectmethodbecomesverylargeforlargeN.

Forthisreason,weareinterestedincomputationalproceduresthatreducethenumberofmultiplicationsandadditions.2)Complexconjugatesymmetry:

1)Periodicityinnandk:

3)

Reducibility

可約性:CanreducethecomputationofDFTbyusingtheseProperties.4)others二、Propertiesof【BasicideasforFFTalgorithm】Dividealongsequenceintoseveralshortsequences.UsingallpropertiesoftocombineSomeitems

InDFT

Example:N=8,By

'decimation'Decimation-In-TimeFFT(DIT-FFT)Decimation-In-FrequencyFFT(DIF-FFT)radix-2FFT

hybrid-radixFFT

split-radixFFTradix-4FFTBy'radix'FFTalgorithmsTheothers

CTZ§6.2Decimation-in-timeFFTAlgorithms(DIT)(Coolkey-Tukey)Let

——radix-2FFT0123456789101112131415nx(n)If,padzerosto16points.

一、Principal

CalculateN-DFTusingDivideNpoints

intotwo

pointssequenceLet,AnotherhalfofX[k]:

So,ButterflyComputation:

AN-pointDFTisdecomposedintotwoN/2-pointDFTs1complexmultiplication+2complexaddition——ButterflyComputation

inDIT-FFTplex×

:complex+:

Computation=twoN/2-pointDFTs+N/2butterflies計(jì)算量減少大約一半+:N(N-1)DFT2.The2nddecomposition:Similarly,Then,aN-pointDFTisdecomposedintofourN/4-pointDFTs.計(jì)算量進(jìn)一步減少大約一半e.g.Computation=4N/4-pointDFTs+2

stagesbutterflies3.Furtherdecompositionuntil2-pointDFTsareleftbutterflye.g.The8-pointDIT-FFTStagem=0m=1m=2group421Coefficient4、Computation:Complexmultiplication:Complexaddition:DFT+:N(N-1)

ComparisonofthecomputationofDFTandDIT-FFT

DFTDIT-FFTRatio

DFTDIT-FFTRatioNN2

L

NN2

L2414.01281638444836.641644.025665536102464.0864125.45122621442304113.816256328.0102410485765120204.83210288012.82048419430411264372.464404919221.4

二、PropertiesofDIT1.In-PlaceComputations(原位運(yùn)算、同址運(yùn)算)Theoutputofeverystagecanbestoredintheregisterswhichstoringtheinputdata.SoNregistersarenecessary.2、Bit-reversedorder(倒位序)Input:bit-reversedorder.Output:normalordernormalorderbinarydigits(n2n1n0)bit-reservedbinarydigits(n0n1n2)bit-reservedorder00000000100110042010010230111106410000115101101561100113711111173.

Distancebetweentwosourcenodesofonebutterfly

Stagem=0m=1m=2Distance124三、AlternativeFormsinputinnormalorder,outputinbit-reserved

orderbothinputandoutputinnormalorderinputinbit-reservedorder,outputinnormalorder,withthesamegeometryforeachstage§6.3Decimation-in-frequencyFFTAlgorithms

(DIF)一、Principal

CalculateN-DFTusing——ButterflyComputation

inDIF-FFTSo,2complexaddition+1complexmultiplicationLetcompareThen

plex×

:complex+:

Computation=twoN/2-pointDFTs+N/2butterflies計(jì)算量減少大約一半+:N(N-1)DFT2.The2nddecomposition:e.g.Computation=2

stagesbutterflies+FourN/4-pointDFTs3.Furtherdecompositionuntil2-pointDFTsareleftbutterflye.g.The8-pointDIF-FFT8-pointDIF-FFT:compareStagem=0m=1m=2group124Coefficient4、Computation:Complexmultiplication:Complexaddition:DFT+:N(N-1)

二、PropertiesofDIF1.In-PlaceComputations(原位運(yùn)算、同址運(yùn)算)2.Bit-reversedorder(倒位序)Output:bit-reversedorder.Input:normalorder3.

Distancebetweentwosourcenodesofonebutterfly

Stagem=0m=1m=2Distance421四、ComparisonofDIT-FFTandDIF-FFT1.ideaDIT-FFT:

dividetheinputsequencex[n]intosmallerandsmallersubsequencesDIF-FFT:

dividetheoutputsequenceX[k]intosmallerandsmallersubsequences2.ButterflycomputationisdifferentDIT-FFT:

DIF-FFT:

(fig.9.11)

(fig.9.21)

3.StructuresaretransposedeachotherDIT-FFT:

(fig.9.10)

DIF-FFT:

(fig.9.20)

4.Botharein-placecomputation5.Thecomputation