离散时间信号处理(英文版)chap9-第1讲

Ch9.ComputationoftheDiscreteFourierTransform,Maincontents,Decimation-In-TimeFFTalgorithm(DIT-FFT),Decimation-In-FrequencyFFTalgorithm(DIF-FFT),IFFT,9.0Introduction,TheFastFourierTransform(FFT)isnotanewalgorithmwhichisdifferentfromtheDFT,butanefficientalgorithmforfastcomputationoftheDFT.,9.1EfficientComputationoftheDFT,ThedirectcomputationofDFT,N,N-1,N(N-1),4N,2N+2(N-1)=4N-2,e.g.,N:,ComplexMul:,8,1024,64,1048576,Theamountofcomputation(thecomputationtime)requiredtocomputetheDFTbythedirectmethodbecomesverylargeforlargeN.,Forthisreason,weareinterestedincomputationalproceduresthatreducethenumberofmultiplicationsandadditions.,(i)complexconjugatesymmetry:,(ii)periodicityinnandk:,(iii)可约性:,ApproachestoreducethecomputationofDFTbyusingthePropertiesof,(iv),FFT算法的基本思路,Decimation-In-TimeFFT(DIT-FFT),Decimation-In-FrequencyFFT(DIF-FFT),利用的周期性、对称性、可约性，使DFT运算中某些项合并,将长序列的DFT分解为若干短序列的DFT,9.3.Decimation-In-TimeFFTalgorithms,Thedecompositionisbasedondecomposingthesequencexnintosuccessivelysmallersubsequences.,PrincipleoftheDIT-FFTAlgorithm,Let,radix-2FFT,Decomposexnintotwosequencesaccordingnisevenorodd,Then,AnotherhalfofXk:,So,ButterflyComputation:,AN-pointDFTisdecomposedintotwoN/2-pointDFTs,onecomplexmultiplication+twocomplexaddition,e.g.,complexmul:,complexadd:,Computation=twoN/2-pointDFTs+N/2butterflies,计算量减少大约一半,(ii)The2nddecomposition:,Similarly,Then,aN-pointDFTisdecomposedintofourN/4-pointDFTs.,计算量进一步减少大约一半,e.g.,Computation=FourN/4-pointDFTs+2stagesbutterflies,(iii)Furtherdecompositionuntil2-pointDFTsareleft,e.g.,So,the8-pointDIT-FFT:,ComputationofDIT-FFT,当时，共有级蝶形；每级都由N/2个蝶形运算组成，每个蝶形有1次复乘、2次复加，因此每级运算需N/2次复乘和N次复加。,v级运算总共需要复乘和复加。,(i)TheDIT-FFT,complexmul:,complexadd:,(ii)ThedirectDFT,complexmul:,complexadd:,(iii)Ratio,ComparisonofthecomputationofDFTandDIT-FFT,ComparisonofthecomputationofDFTandDIT-FFT,CharacteristicsofDIT-FFT,(i)In-PlaceComputations(原位运算、同址运算),迭代运算：,(i)In-PlaceComputations(原位运算、同址运算),第m级的两个节点p,q的值只与第(m-1)级的p,q两个节点有关，与其他节点均无关。因此，蝶形的两个输出值Xmp和Xmq可以存放在蝶形的两个输入Xmp-1和Xmq-1所在的存储器中(这种运算就称为原位运算)。每一级的蝶形运算全部完成后，再开始下一级的蝶形运算，直到最后输出，中间无需其他存储器。这样存储数据只需要N个存储单元。,(ii)Bit-reversedorder(倒位序),input:,bit-reversedorder,Thereasonforbit-reversedorder,Therealizationofbit-reversedorder,(iii)Distancebetweentwosourcenodesofonebutterfly,第一级(第一列)每个蝶形的两个节点间距离为1第二级(第二列)每个蝶形的两个节点间距离为2第三级(第三列)每个蝶形的两个节点间距离为4,依次类推，对于点DIT-FFT，当输入为倒位序，输出为正常序时，其第m级运算每个蝶形的两节点间距离为,(iv)Determine,最后一级有N/2种：,倒数第二级有N/4种:,依次类推，第一级有1种：,(v)存储单元,存储输入序列的N个存储单元单元，以及存储系数的N/2个存储单元。,AlternativeForms,只要保持各节点所连的支路及其传输系数不变，则不论节点位置怎么排列，所得流图总是等效的，所得结果都是xn的DFT的正确结果，只是数据的提取和存放顺序不同而已。,inputinnormalorder,