《数字信号处理办法教案第4章.ppt》由会员分享，可在线阅读，更多相关《数字信号处理办法教案第4章.ppt（76页珍藏版）》请在三一文库上搜索。
1、,数字信号处理办法教案第4章,2,4.1 引言, DFT 是数字信号处理的基础，是 一种重要变换。 快速算法的引出，使数字信号处 理技术得到广泛应用。 各种快速算法不断被采用,3,数字计算机,N足够大,.1.1 DFT提供了计算机处理的可能性,模拟信号的频谱分析,4.1.2 DFT的运算量,k=0,1,2,N1,计算机运算时：,N项,N个,计算一个 N点DFT ，共需,次复乘。,以做,一次复乘1s计，若N =4096，所需时间为,由于计算量大，且要求相当大的内存，,难以实现实时处理，限制了DFT的应用。,5,长期以来，人们一直在寻求一种能提高DFT运算速度的方法。FFT便是Cooley&Tuk
2、ey 在1965 年提出的的快速算法，它可以使运算速度提高几百倍，从而使数字信号处理学科成为一个新兴的应用学科。,4.1.3 FFT算法的设计思想,1利用,的特点,具有,1）周期性,2）共轭性,3）对称性,4）恒等性,5）可约性,2把N 点DFT化为几组点数较少的DFT运算,N点DFT运算的复乘次数为,次，若将N点DFT,化为2 组，则复乘次数约为,次。,7,4.2 基 2 抽取FFT 算法,（the Decimation-In-Time Radix-2 FFT Algorithm）FFT分为两大类：时域抽取FFT（Decimation-In-Time FFT，简称DIT-FFT）频域抽取FF
3、T（Decimation-In-Frequency FFT， 简称DIF-FFT）,8,4.2.1 直接计算DFT的问题及改进的途径,k=0, 1, , N-1,n=0, 1, , N-1,DFT及IDFT的定义,9,可见，DFT 与 IDFT 的计算成本基本相同。直接计算N点DFT 时：对应一个k需要N次复数乘和（N-1）次复数加；对所有N个k值，则需要 N复数乘和N (N-1)次复数加 。其中:一次复数乘需要4次实数乘和2次实数加方能完成。当N较大时，运算量很大。,10,例如：当N=8时，DFT需要64次复数乘；当N=1024时，DFT所需复数乘为次，即一百多万次复数乘。为了减少运算次数，
4、改进计算的方法：1）利用旋转因子的对称性、周期性和可约性； 旋转因子（twiddle factor）2）使长序列变短。,11,4.2.2 基2时域抽取法原理,（库利-图基算法）设序列x（n）的长度为N，且M为自然数N-point DFT,N is even,12,将其一分为二，分成偶数和奇数序列项（the even-indexed and odd-indexed terms）则N/2点的序列为： even: x1(r)=x(2r) , r=0, 1, , N/2-1 odd: x2(r)=x(2r+1) , r=0, 1, , N/2-1,13,偶数序列 the range: 02nN-2 (
5、N is even) 0n(N/2)-1奇数序列 the range: 12n+1N-1 (N is even) 02nN-2 0n(N/2)-1,14,则x（n）的DFT：,15,由于所以,k=0,1,N-1,16,上式说明,按n的奇偶性将 分解为两个N/2长的序列 和 ,则N点DFT可分解为两个N/2点的DFT来计算.,17,其中 N/2-point DFT:,k=0,1,N/2-1,k=0,1,N/2-1,18,因此，可写出两个N/2点的方程:,19,而,20,同理而,21,所以,22,表示上述算法可用蝶形结（ butterfly）,23,Example : 如N=4,x(n)=x0,
6、x1, x2, x3 even: x0, x2 even: x0 odd: x2 odd: x1, x3 even: x1 odd: x3,24,bit reversal/shuffling process,混序或反序,码位倒置,分成四个1点的序列,25,the butterfly（蝶形运算）,1点序列的DFT就是序列本身，即不用计算,-1,-1,-1,-1,26,如N4，则,将 x1(r) 再按r的奇偶进一步分解成两个N/4点长的子序列：,27,28,其中,29,由X3（k）和X4（k）的周期性和 的对称性，得,30,同理，得,31,其中,32,8点DIT-FFT运算流图,33,4.2.3
7、IDFT的高效算法,这样IFFT可与FFT用同一子程序实现。,34,IDFT的运算规律,35,求IFFT，也可用DIT-FFT的流程来实现。,36,Example:,Determine the x(n) by IDFT.X=5, -1, 1, -1 Solution: n=0,1,2,3,37,38,所以 x(n)=1, 1, 2, 1,39,%the program in MATLAB: X=input(Please input X=); N=length(X); x=fft(conj(X),N); x=conj(x/N),40,Example :,用FFT算法计算下面信号的 8点DFT；
8、x(n)=4 3 2 0 1 2 3 1然后，再用 IFFT恢复原信号。,41,solution:,2,2,2,2,2,2,42,IFFT(X)=1/NFFT(X*)*,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,乘以1/N=1/8得原序列,43,4.2.4 FFT的计算成本,最简单的FFT 是Cooley-Tukey法因为,N点DFT有M级蝶形运算，每一级都有N/2个蝶形运算结构；每个蝶形运算结构都有1次复数乘和2次复数加；,45,所以，M级蝶形运算有复数乘M级蝶形运算有复数加,46,直接DFT的复数乘和复数加均近似为 。当N1时，所以DIT-FFT大大减少了运算次数。,
9、47,Example : for N=8,Solution : M= =3 stages（三级） for FFT, the total cost is （FFT的总计算成本是） MN/2=38/2=12 complex multiplications （复数乘）,48,for directly DFT, the total cost is（直接计算DFT的成本是） N=8=64 (complex multiplications) The ratio is: （比值是） 实际上，当N=2048时，直接运算与 FFT算法的计算量之比为372.4,49,4.2.5 DIT-FFT的运算规律及编程思想
10、,1、原位运算：利用同一单元存储蝶形计算的输入、输出数据。每个蝶形的输入和输出均为相同位数。原位运算可节省大量内存，因而硬件成本低。2、旋转因子的变化规律： N点DFT，共有M级蝶形运算，每级有N/2个蝶形。,50,称为旋转因子，p称为旋转因子的指数。 为了编写程序，应找出旋转因子 与运算 级数的关系。 设L=1，2，M，表示从左到右的运算 级数，第L级有 个不同的旋转因子，,51,对于 ，各级的旋转因子表示为L=1时，L=2时，L=3时，,52,对于 的一般情况，第L级的旋转因子为,，,由于,53,所以通过上式，可以计算第L级运算的旋转因子。,54,3、蝶形运算规律,设序列x（n）经过时域倒
11、序存入数组X如蝶形运算的两个输入数据相距B个点，应用原位运算，可得：,55,4、编程思想及程序框图,其它运算规律：第L级中，每个蝶形的两个输入数据相距 个点；同一旋转因子对应着间隔为 点的 个蝶形（对应第几组蝶形）,56,8点DIT-FFT运算流图,57,编程的运算方法：从输入端（第1级）开始，逐级进行，共进行M级运算。在进行第L级运算时，依次求出 个不同的旋转因子，然后计算其对应相同的旋转因子的 个蝶形。可用三重循环程序实现DIT-FFT运算。,58,(3),59,5、序列的倒置（bit reversal）,倒序是有规律的。由于 ，所以顺序数可用M位二进制数（ ）表示。,60,用硬件电路和汇
12、编语言程序产生倒序很容易，用高级语言倒序的规律为：倒序数是在M位二进制数最高位加1，逢2向右进位。,61,4.2.6 频率抽取法FFT(DIF-FFT),设序列x（n）长度为 ，将其前后对半分开，得：,62,式中,63,再将X（k）分解成偶数组和奇数组 k为偶数时：,64,k为奇数时：,65,令,66,得,67,DIF-FFT蝶形运算流图,-,+,68,N=8时，DIF-FFT蝶形运算流图,69,注意：DIT-FFT和DIF-FFT的算法流图不 是唯一的。 其变形运算流图见P108。,70,4.3 进一步减少运算量的措施,以程序的复杂度换取计算量的进一步提高。4.3.1 多类蝶形单元运算第一级
13、旋转因子可简化：第二级旋转因子可简化：称为无关紧要的旋转因子。,71,其复数乘法次数可减少为： CM（2）=（M-2）*N/2当L=3时，第三级蝶形有两个无关紧要旋转因子，同一因子对应2(M-L)=N/2L级蝴蝶结,所以第三级共有(书110页),72,依次类推，从L=3到L=M共可减少复数乘法次数为：DIT-FFT的复数乘法次数为：,73,另外，也可用实数乘法减少计算量。包含所有旋转因子称为一类蝶形单元运算；去掉 为二类；去掉 为三类；依次类推，称为多类蝶形单元运算。N=4096时，三类与一类比，仅75%。,74,4.3.2 旋转因子的生成 直接查表，提高速度，多占内存。4.3.3 实序列的FFT算法 两个实序列，构造序列y（n）,75,由于x（n）为实序列，所以X（k）具有共轭对称性：,76,4.4 分裂基FFT算法,任意基：基较大，则程序或硬件将很复杂，基大于8无意义。分裂基：采用基2和基4的混合算法，可有效提高运算速度。,