《《信号与系统》第八章b--考研及期末考试》由会员分享，可在线阅读，更多相关《《信号与系统》第八章b--考研及期末考试（67页珍藏版）》请在金锄头文库上搜索。
1、虽然频谱分析和DFT运算很重要，但在很长一段时间里，由于DFT运算复杂，并没有得到真正的运用，而频谱分析仍大多采用模拟信号滤波的方法解决，直到1965年库利（T.W.Cooley）和图基（J.W.Tukey）首次提出DFT运算的一种快速算法以后，情况才发生了根本变化，人们开始认识到DFT运算的一些内在规律，从而很快地发展和完善了一套高速有效的运算方法快速傅立叶变换（FFT）算法。FFT的出现，使DFT的运算大大简化，运算速度提高12个数量级，使DFT的运算在实际中得到广泛应用。本节重点介绍FFT算法的基本思想和基2时域抽取法FFT算法 。,8.5 快速傅里叶变换（FFT）,一般，x(n)和WN
2、nk都是复数，因此，每计算一个X(k)值，要进行N次复数相乘，和N-1次复数相加， X(k)一共有N个点，故完成全部DFT运算，需要 复数乘法次数：N 2 复数加法次数：N(N-1) N2,长度为N的有限长序列x(n)的DFT为,特点：在N点DFT的计算中，不论是乘法和加法，运算量均与N2 成正比。因此，N 较大时，运算量十分可观。,例如，计算N=10点的DFT，需要100次复数乘法，而N=1024点时，需要1048576（一百多万）次复数乘法。反变换IDFT与DFT的运算结构相同，只是多乘一个常数1/N，所以二者的计算量相同。,减少DFT运算量的基本途径,有限长序列 x(n)进行一次DFT运
3、算所需的运算量。,2. 减少运算量的基本途径,利用,的周期性和对称性减少运算次数,周期性：,对称性：,与,关于实轴对称。,与,关于原点对称,(2) 把N点DFT分解为几个较短的DFT，可使乘法次数大大减少。,实轴对称,原点对称,FFT算法基本上分为两大类： 时域抽取法FFT (Decimation In Time FFT, 简称DIT-FFT) 频域抽取法FFT (Decimation In Frequency FFT, 简称DIFFFT)。,8.5.1 基2时域抽取法FFT算法,首先将序列x(n) 按n的奇偶分解为两组，一组为偶数项，一组为奇数项：,第一次分解 (最后一级运算),1. 算法的
4、推导,设序列x(n)的长度为N，所谓基2是指N满足N=2M，M为正整数。,k=0, 1，N/2-1,如果用此式子计算所有的N个X(k)运算量不会减小。,研究发现：前一半的X(k)用上式计算，后一半X(k) 利用周期性和对称性也可以用前一半的结果计算，从而可以减小运算量。,k=0, 1，N/2 - 1,可以看出：X1(k) 和X2(k)都是以N/2为周期。,k=0, 1，N/2 - 1,k=0, 1，N/ 2 - 1,该运算称为蝶形运算，用下图符号表示,N点DFT的一次时域抽取分解图(N=8),第二次分解,(1) 将序列x1( r) 按r的奇偶分解分解成两个N/4长的子序列x3( l )和x4(
5、 l )，即,k=0, 1，N/4 - 1,系数统一为,(2) 将序列x2(r) 按r的奇偶分解分解成两个N/4长的子序列x5(l)和x6(l)，即,k=0, 1，N/4 - 1,第二次分解,(1) 将序列x1( r) 按r的奇偶分解分解成两个N/4长的子序列x3( l )和x4( l )，即,k=0, 1，N/2 - 1,同理，由X3(k)和X4(k)的周期性(以N/4为周期)和WkN/2的对称性，得,k=0, 1，N/4 - 1,(2) 将序列x2(r) 按r的奇偶分解分解成两个N/4长的子序列x5(l)和x6(l)，即,k=0, 1，N/2 - 1,同理，由X5(k)和X6(k)的周期性
6、(以N/4为周期)和WkN/2的对称性，得,k=0, 1，N/4 - 1,经过第二次分解，又将两个N/2点DFT分解为四个N/4点DFT和N/2个蝶形运算，如图6-10所示。如果N=8，X3 (k)、X4 (k) 、X5 (k)和X6 (k)都是二点的DFT，不能再分了。图6-11所示为8点按时间抽取 FFT运算流图，从图中可以看出，每一个二点DFT实际上也是一个蝶形运算。如果N=2M8，则继续分解下去，直到经M-1次分解，将N点DFT分解成N/2个两点DFT为止。,N点DFT分解成四个N/4点DFT(N=8),L=1,L=2,L=3,N=8按时间抽取FFT运算流图,(1)实现一次蝶形运算，实
7、际仅需一次乘法、两次加减法。,N点DFT的一次时域抽取分解的运算量分析,(2)运算量：,计算X1(k) 和X2(k)各需要(N/2)2次复数乘法，还有N/2个蝶形运算，乘法数为N/2。,复数乘法总数为：,计算X1(k) 和X2(k)各需要N/2(N/2-1) 次复数加法还有N/2个蝶形运算，加法数为2N/2。,复数加法总数为：,仅一次分解，运算量减少一半。,(3) 算法的运算量,每一级运算都需要N/2次复数乘和N次复数加(每个蝶 形需要两次复数加法)。N=2M , 所以，共M级蝶形运 算，总共需要的复数乘次数为,总共需要的复数加次数为,例如，N=210=1024时,FFT显然要比直接法快得多。
8、,3. 算法的特点,（1）原位计算 当数据输入到存储单元中以后，每一级蝶形运算的结果仍然储存在原输入数据所占用的存储单元中，直到最后输出，中间无需其它存储单元，这种蝶形计算输入和输出数据共占同一存储单元的方法叫原位计算。 原位计算的优点：可节省存储单元，降低设备成本，还可节省寻址的时间。,(2) 旋转因子的变化规律,寻找旋转因子的变化规律，是编制FFT程序的关键。,如上所述，N点DITFFT运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以因子WpN，称其为旋转因子(单位圆周上的点)，p称为旋转因子的指数。,观察图6-11不难发现，第L级共有2L - 1个不同的旋转因子。,L=1, 2, ,
9、M,以N=23=8为例，分析旋转因子的变化规律：,L=1时，,L=2时，,L=3时，,对N=2M的一般情况，第L级的旋转因子为 而,J=0,J=0，1,J=0，1，2，3,J的取值由第L级不同旋转因子数2L - 1确定。,的下标和指数都变化，如果将其变成,则只有指数在变化，编程较容易。p的变化规律:,(3) 蝶形运算规律,第L级中，每个蝶形运算的两个输入数据相距B= 2L - 1个点，即,XL(J) = XL-1(J)+XL-1(J+B)WpN XL(J+B) =XL-1(J)-XL-1(J+B)WpN 式中 p=J2M - L；J=0, 1, , 2L - 1 -1；L=1, 2, , M,
10、第L级中，不同的旋转因子数也是B= 2L - 1，相同旋转因子的 蝶形结间的距离为2L个点。,相邻不同旋转因子的蝶形结间距离为1。,(4) 序列的倒序,对按时间抽取FFT的原位运算结构，当运算完毕时，X(k)依照自然顺序排列，如正好顺序存放着 X(0)，X(1)，X(2)，X(7)，但这种原位运算的输入序列 x(n)却不能按这种自然顺序存入存储单元中，如是按x(0)，x(4)，x(2)，x(6)， x(1)，x(5)，x(3)，x(7)的顺序存入存储单元，这正是由于对x(n)做奇偶分开所产生的。,序列的倒序数(顺序数与倒序数之间的关系),x(0),x(1),x(2),x(3), x(4),x(
11、5), x(6),x(7),x(0),x(2),x(4),x(6), x(1),x(3), x(5),x(7),x(0),x(4),x(2),x(6), x(1),x(5), x(3),x(7),以N=8为例：,第一次按奇偶分开：,第二次按奇偶分开：,用二进制数表示顺序数与倒序数：,顺序和倒序二进制数的关系：,将顺序二进制数(n2n1n0)倒置，即可得到倒序二进 制数(n0n1n2) 。,倒序数的十进制运算规律,(a) 二进制数的运算规律,倒序数是从0开始，在M位二进制数最高位加1，逢二 向右进位，即可得到下一个倒序数。,(b) 十进制数的运算规律,J表示当前倒序数，二进制数各位的权值为,二进
12、制数各位加1，相当于十进制运算加上各位的权值；,二进制数各位减1，相当于十进制运算减去各位的权值。,倒序程序框图,第一序列值和最后一个序列值不需要交换；,输入倒序排列，输出才是顺序排列；,为避免再次交换，只在 IJ 时才交换A(I)和A(J)的内容。,将顺序排列的输入，按倒序调换排列，放在同一数组中。,本位变为0，求本位右边位的权值存入K；,I中是顺序数；,J中是倒序数，也是第2个数；,第一和最后一个输入不参与调换；,由前一个倒序数得到后一个 倒序数，K中为最高位权值；,向右进位；,避免再次调换已调换过的一对数据；,调换数组元素；,4. 编程思想及程序框图,第L级中，不同的旋转因子数为 2L
13、- 1，相同的旋转因子数 为2M L 。,(2) 每一级中，蝶形数也是旋转因子总数, 它等于不 同的旋转因子数乘以相同的旋转因子数，即 2L - 12M L = 2M /2 = N/2,(3) 从第1级开始，逐级进行，共进行M级运算，在 进行第L级运算时，依次求出2L - 1个不同的旋转因 子及它们对应的所有2M L个蝶形。,最外层循环控制运算的级数；,计算蝶形结间距；,第二层控制计算不同旋转因子的蝶形结；,计算不同旋转因子的指数,步长为不同旋转因子间距离。,最内层进行同一旋转因子的蝶形结运算,，步长为相同旋转因子间距离2L 。,计算N；,以上讨论的FFT算法都是复数运算,包括序列x(n)也认
14、为是复数,但大多数场合,信号是实数序列,任何实数都可看成虚部为零的复数,例如,求某实信号x(n)的复谱,可认为是将实信号加上数值为零的虚部变成复信号(x(n)+j0),再用FFT求其离散傅里叶变换。这种作法很不经济,因为把实序列变成复序列,存储器要增加一倍,且计算机运行时,即使虚部为零,也要进行涉及虚部的运算,浪费了运算量。合理的解决方法是利用复数据FFT对实数据进行有效计算,下面介绍两种方法。,8.5.2 实序列的FFT算法,设x1(n)、x2(n)是彼此独立的两个N点实序列,将它们作为一复序列的实部及虚部，构成新序列x(n)如下 ： x(n)=x1(n)+jx2(n) 对x(n)进行DFT
15、， 得到 X(k)=DFTx(n)=Xep(k)+Xop(k),Xep(k)=DFTx1(n)=1/2X(k)+X*(N-k) Xop(k)=DFTjx2(n)=1/2X(k)-X*(N-k) X1(k)=DFTx1(n)=1/2X(k)+X*(N-k) X2(k)=DFTx2(n)= -j1/2X(k)-X*(N-k),(1)用 一个N点FFT同时计算两个N点实序列的DFT,由此得,(2)用一个N/2点的FFT计算N点实序列的DFT,设x(n)为N点实序列，取x(n)的偶数点和奇数点分别作为新构造序列y(n)的实部和虚部，即,x1(n)=x(2n) n=0,1,N/2-1 x2(n)=x(2
16、n+1) n=0,1,N/2-1 然后将x1(n)及x2(n)组成一个复序列： y(n)=x1(n)+jx2(n),对y(n)进行N/2点FFT，输出Y(k)，则,X1(k)=Yep(k)=DFTx1(n)=1/2Y(k)+Y*(N-k) X2(k)= -j Yop(k)= DFTx2(n)= -j1/2Y(k)-Y*(N-k),由于x(n)为实序列，所以X(k)具有共轭对称性，X(k)的另外N/2点的值为,k =1, 2, , N/2 - 1,k =0, 1, , N/2 - 1,8.5.3 IDFT的FFT算法,比较DFT和IDFT的运算公式：,IDFT与DFT的差别： 1）把DFT中的每一个系数 改为 ； 2）再乘以常数 1/N 。,以上所讨论的时间抽取或频率抽取的FFT运算均可直接用于IDFT运算，当然，蝶
