数字信号处理(丁玉美版)教案第4章.pptVIP

*称为旋转因子，p称为旋转因子的指数。为了编写程序，应找出旋转因子与运算级数的关系。设L=1，2，…，M，表示从左到右的运算级数，第L级有个不同的旋转因子，对于，各级的旋转因子表示为L=1时，L=2时，L=3时，对于的一般情况，第L级的旋转因子为由于所以通过上式，可以计算第L级运算的旋转因子。3、蝶形运算规律*设序列x（n）经过时域倒序存入数组X如蝶形运算的两个输入数据相距B个点，应用原位运算，可得：因此，可写出两个N/2点的方程:*而同理而所以*表示上述算法可用蝶形结（butterfly）Example:如N=4*x(n)=x0,x1,x2,x3even:x0,x2even:x0odd:x2odd:x1,x3even:x1odd:x3*bitreversal/shufflingprocess混序或反序码位倒置分成四个1点的序列*

thebutterfly（蝶形运算）1点序列的DFT就是序列本身，即不用计算-1-1-1-1如N4，则*将x1(r)再按r的奇偶进一步分解成两个N/4点长的子序列：其中*由X3（k）和X4（k）的周期性和的对称性，得同理，得*其中*8点DIT-FFT运算流图*4.2.3IDFT的高效算法*这样IFFT可与FFT用同一子程序实现。IDFT的运算规律*求IFFT，也可用DIT-FFT的流程来实现。Example:*Determinethex(n)byIDFT.X=[5,-1,1,-1]Solution:n=0,1,2,3所以x(n)=[1,1,2,1]%theprograminMATLAB:X=input(‘PleaseinputX=’);N=length(X);x=fft(conj(X),N);x=conj(x/N)Example:*用FFT算法计算下面信号的8点DFT；01.x(n)=[4–320–1–231]′02.然后，再用IFFT恢复原信号。03.solution:*?2?2?2030201?2?2?2*IFFT(X)=1/N[FFT(X*)]*?2?2?2?2?2?2?2?2?2?2?2?2?2?2?2?2乘以1/N=1/8得原序列4.2.4FFT的计算成本*N点DFT有M级蝶形运算，每一级都有N/2个蝶形运算结构；每个蝶形运算结构都有1次复数乘和2次复数加；最简单的FFT是Cooley-Tukey法因为M级蝶形运算有复数加所以，M级蝶形运算有复数乘直接DFT的复数乘和复数加均近似为。当1时，所以DIT-FFT大大减少了运算次数。Example:forN=8*Solution:M==3stages（三级）forFFT,thetotalcostis（FFT的总计算成本是）MN/2=3?8/2=12complexmultiplications（复数乘）fordirectlyDFT,thetotalcostis（直接计算DFT的成本是）N2=82=64(complexmultiplications)Theratiois:（比值是）实际上，当N=2048时，直接运算与FFT算法的计算量之比为372.44.2.5DIT-FFT的运算规律及编程思想N点DFT，共有M级蝶形运算，每级有N/2个蝶形。旋转因子的变化规律：原位运算：利用同一单元存储蝶形计算的输入、输出数据。每个蝶形的输入和输出均为相同位数。原位运算可节省大量内存，因而硬件成本低。降*第四章快速傅立叶变换 （FFT）FastFourierTransform数字信号处理4.1引言*A?DFT是数字信号处理的基础，是B一种重要变换。C?快速算法的引出，使数字信号处D理技术得到广泛应用。E?各种快速算法不断被采用*数字计算机N足够大４