《快速付立叶变换(FFT).ppt》由会员分享，可在线阅读，更多相关《快速付立叶变换(FFT).ppt（75页珍藏版）》请在三一办公上搜索。
1、第四章 FFT快速傅氏变换,4-5线性卷积的FFT算法,4-3 DIF的FFT算法,4-4 IFFT算法,4-2按时间抽取(DIT)的FFT算法,4-1 引言,目录,4-1引言,一.DFT的计算工作量 两者的差别仅在指数的符号和因子1/N.,DFT与IDFT运算特点,同理：IDFT运算量与DFT相同。,通常x(n)和都是复数,所以计算一个 X(k)的值需要N次复数乘法运算,和 次 复数加法运算.那么,所有的X(k)就要N2次复 数乘法运算,N(N-1)次复数加法运算.当N很 大时,运算量将是惊人的,如N=1024,则要完 成1048576 次(一百多万次)运算.这样,难以做到实时处理.,一个X
2、(k)的值的工作量,如X(1),二.改进的途径,1.的对称性和周期性,得:,对称性:,周期性:,利用上述特性,可以将有些项合并,并将DFT分解为短序列,从而降低运算次数,提高运算速度.1965年,库利(cooley)和图基(Tukey)首先提出FFT算法.对于N点DFT,仅需(N/2)log2N 次复数乘法运算.例如N=1024=210 时，需要(1024/2)log2 210=512*10=5120次。5120/1048576=4.88%,速度提高20倍,FFT算法分类:,时间抽选法DIT:Decimation-In-Time频率抽选法DIF:Decimation-In-Frequency,
3、4-2 按时间抽取(DIT)的FFT算法 库利-图基算法,一.算法原理(基2FFT)(一)N/2点DFT1.先将 按n的奇偶分为两组作DFT,设N=2L,不足时,可补些零。这样有:n为偶数时:n为奇数时:,因此，,由于:所以,上式可表示为:,(n为偶数)(n为奇数),其中,2.两点结论:(1)X(k),X(k)均为N/2点的DFT。(2)X(k)=X(k)+W X(k)只能确定出 X(k)的k=个；即前一半的结果。,1 2,1 2,k,N,同理,这就是说,X1(k),X2(k)的后一半,分别 等于其前一半的值。,3.X(k)的后一半的确定,由于（周期性）,所以:,可见,X(k)的后一半，也完全
4、由X1(k),X2(k)的前一半所确定。*N点的DFT可由两个N/2点的DFT来计算。,又由于,所以,实现上式运算的流图称作蝶形运算,前一半,4.蝶形运算,后一半,（N/2个蝶形),由X1(k)、X 2(k)表示X(k)的运算是一种特殊的运算-碟形运算,5.分解后的运算量：,运算量减少了近一半,例如 N=8 时的DFT,可以分解为两个 N/2=4点的DFT.具体方法如下:(1)n为偶数时,即 分别记作:,(2)n为奇数时,分别记作:,x1(0)=x(0)x1(1)=x(2)N/2点 x1(2)=x(4)DFT x1(3)=x(6)x2(0)=x(1)x2(1)=x(3)N/2点 x2(2)=x
5、(5)DFT x2(3)=x(7),1 2,X1(0),X1(1),X1(2),X1(3),X2(0),X2(1),X2(2),X2(3),W,N,2,W,N,1,W,N,0,W,N,3,-1,-1,-1,-1,X(0),X(1),X(2),X(3),X(4),X(5),X(6),X(7),(3)对X(k)和X(k)进行蝶形运算,前半部为 X(0)X(3),后半部分为X(4)X(7)整个过程如下图所示:,由于N=2 L,所以 N/2仍为偶数,可以进 一步把每个N/2点的序列再按其奇偶部分 分解为两个N/4的子序列。例如，n为偶数时的 N/2点分解为:,(二)N/4点DFT,进行N/4点的DFT
6、,得到,从而可得到前N/4的X1(k),后N/4的X1(k)为,注意到,同样对n为奇数时，N/2点分为两个N/4点 的序列进行DFT，则有:,例如,N=8时的DFT可分解为四个N/4的DFT,具体步骤如下:,(1)将原序列x(n)的“偶中偶”部分:,构成N/4点DFT，从而得到X3(0),X3(1)。,(2)将原序列x(n)的“偶中奇”部分:,构成N/4点DFT，从而得到X4(0),X4(1)。,(3)将原序列x(n)的“奇中偶”部分:,构成N/4点DFT，从而得到X5(0),X5(1)。,(4)将原序列x(n)的“奇中奇”部分:,构成N/4点DFT，从而得到X6(0),X6(1)。,（5）由
7、 X3(0),X3(1),X4(0),X4(1)进行碟形运算,得到X1(0),X1(1),X1(2),X1(3)。,（6）由 X5(0),X5(1),X6(0),X6(1)进行碟形运算,得到X2(0),X2(1),X2(2),X2(3)。,(0)=(0)=(0)N/4(1)=(2)=(4)DFT(0)=(1)=(2)N/4(1)=(3)=(6)DFT(0)=(0)=(1)N/4(1)=(2)=(5)DFT(0)=(1)=(3)N/4(1)=(3)=(7)DFT,3 1,3 1,4 1,4 1,5 2,5 2,6 2,6 2,0,2,N,N,0,2,N,N,-1,-1,-1,-2,-1,-1,X
8、(0),X(1),X(2),X(3),X(4),X(5),X(6),X(7),（7）由X1(0),X1(1),X1(2),X1(3)，X2(0),X2(1),X2(2),X2(3)进行碟形运算,得到 X(0),X(1),X(2),X(3)X(4),X(5),X(6),X(7)。,这样,又一次分解,得到四个N/4点DFT,两级蝶形运算,其运算量有大约减少一半 即为N点DFT的1/4。对于N=8时DFT,N/4点即为两点DFT,因此,亦即,(0)(4)(2)(6)(1)(5)(3)(7),W,N,0,W,N,0,W,N,0,W,0,N,-1,-1,-1,-1,-1,-1,-1,-1,N,0,N,1
9、,N,2,N,3,-1,-1,-1,-1,X(0),X(1),X(2),X(3),X(4),X(5),X(6),X(7),因此,8点DFT的FFT的运算流图如下,这种FFT算法,是在时间上对输入序列 的次序是属于偶数还是属于奇数来进行分 解的,所以称作按时间抽取的算法。,(DIT),（三）FFT运算量与运算特点,1 N=2L时，共有L=log2N级运算；每一级有N/2个蝶形结。2每一级有N个数据中间数据），且每级只用到本级的转入中间数据，适合于迭代运算。3计算量：每级N/2次复乘法，N次复加。（每蝶形只乘一次，加减各一次）。共有L*N/2=N/2log2N 次复乘法；复加法L*N=Nlog2N
10、 次。与直接DFT定义式运算量相比(倍数)N2/(Nlog2N)。当 N大时，此倍数很大。,比较DFT,参考P150 表4-1 图4-6,可以直观看出，当点数N越大时，FFT的优点更突出。,(0)=X0(0)X1(0)X2(0)X3(0)=X(0)(4)=X0(1)X1(1)X2(1)X3(1)=X(1)(2)=X0(2)X3(2)=X(2)(6)=X0(3)X3(3)=X(3)(1)=X0(4)X1(4)X2(4)X3(4)=X(4)(5)=X0(5)X3(5)=X(5)(3)=X0(6)X3(6)=X(6)(7)=X0(7)X1(7)X2(7)X3(7)=X(7),W,W,W,W,N,0,
11、N,0,N,0,N,0,-1,-1,-1,-1,W,W,W,W,N,0,N,2,N,0,N,2,-1,-1,-1,-1,W,W,W,W,N,N,N,N,0,1,2,3,.,.,.,.,三.DIT的FFT算法的特点 1.原位运算,输入数据、中间运算结果和最后输出均用同一存储器。,设用m(m=1,2,L)表示第m列;用k,j表示蝶形输入数据所在的（上/下）行数(0,1,2,N-1);这时任何一个蝶形运算可用下面通用式表示，即,由运算流图可知,一共有N个输入/出行,一共有log2 N=L列（级）蝶形运算(基本迭代运算).,1 1,1,1,-1,所以,当m=1时,则有（前两个蝶形）,当m=2时,则有（
12、前两个蝶形）当m=3时,则有（前两个蝶形）,可见,在某列进行蝶形运算的任意两个节点(行)k和j的节点变量 就完全可以确定蝶形运算的结果,与其它行(节点)无关。这样,蝶形运算的两个输出值仍可放回蝶形运算的两个输入所在的存储器中,即实现所谓原位运算。每一组(列)有N/2个蝶形运算,所以只需N个存储单元，可以节 省存储单元。,2 倒位序规律 由图可知,输出X(k)按正常顺序排列在存储单元,而输入是按顺序:这种顺序称作倒位序,即二进制数倒位。,这是由奇偶分组造成的,以N=8为例 说明如下:,3.倒位序实现 输入序列先按自然顺序存入存储单 元,然后经变址运算来实现倒位序排列 设输入序列的序号为n,二进制
13、为(n2 n1 n0)2,倒位序顺序用 表示,其倒位序二进制为(n0 n1 n2)2,例如，N=8时如下表：,0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 4 2 0 1 0 0 1 0 2 3 0 1 1 1 1 0 6 4 1 0 0 0 0 1 1 5 1 0 1 1 0 1 5 6 1 1 0 0 1 1 3 7 1 1 1 1 1 1 7,自然顺序n 二进制n n n 倒位序二进制n n n 倒位顺序n,2 1 0 0 1 2,变址处理方法,存储单元,自然顺序,变址,倒位序,4.蝶形运算两节点的距离:2m-1 其中,m表示第m列,且m=1,L 例如N=8=23,第一级(
14、列)距离为21-1=1,第二级(列)距离为22-1=2，第三级(列)距离为23-1=4。,(0)(4)(2)(6)(1)(5)(3)(7),W,N,0,W,N,0,W,N,0,W,0,N,-1,-1,-1,-1,-1,-1,-1,-1,N,0,N,1,N,2,N,3,-1,-1,-1,-1,X(0),X(1),X(2),X(3),X(4),X(5),X(6),X(7),结点距离为1,节（结）点距离为2,5.WNr 的确定(仅给出方法)考虑蝶形运算两节点的距离为2m-1,蝶 形运算可表为 Xm(k)=Xm-1(k)+Xm-1(k+2m-1)WNr Xm(k+2m-1)=Xm-1(k)-Xm-1(
15、k+2m-1)WNr 由于N为已知,所以将r的值确定即可。,例如 N=8=23(1)k=2,m=3 的r值,k=2=(010)2 左移L-m=3-3=0,r=(010)2=2;(2)k=3,m=3 的r值;k=3=(011)2,左移0位,r=3；(3)k=5,m=2的值;k=5=(101)2 左移L-m=1位 r=(010)2=2。,为此，令k=(n2n1n0)2,再将k=(n2n1n0)2 左移(L-m)位,右边位置补零,就可得到(r)2 的值，即(r)2=(k)22L-m。,6.存储单元 存输入序列(n),n=0,1,N-1,计N 个单元;存放系数,r=0,1,N/2-1,需N/2个存储单
16、元；共计(N+N/2)个存储单元。,4-3 DIF的FFT算法(桑德图基算法),一.算法原理 1.N点DFT的另一种表达形式,由于 故 因此 X(k)可表为,2.N点DFT按k的奇偶分组可分为两个N/2的DFT 当k为偶数,即 k=2r时,(-1)k=1；当k为奇数,即 k=2r+1 时(-1)k=-1。这时 X(k)可分为两部分：,k为偶数时：,可见,上面两式均为N/2的DFT。,k为奇数时：,-1,3.蝶形运算,-1,-1,-1,-1,4.N=8时,按k的奇偶分解过程 先蝶形运算，后DFT:,5.仿照DIT的方法 再将N/2点DFT按k的奇偶分解为两个N/4点的DFT,如此进行下去,直至分
17、解为2点DFT。,(0)X(0)(1)X(4)(2)X(2)(3)X(6)(4)X(1)(5)X(5)(6)X(3)(7)X(7),-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,例如 N=8时DIF的FFT流图如下：,二.原位运算 每级(列)都是由N/2个蝶形运算构 成,即,-1,W,N,r,三.蝶形运算两节点的距离,一般公式为2L-m=N/2m 例如 N=23=8：(1)m=1 时的距离为 8/2=4；(2)m=2 时的距离为 8/4=2;(3)m=3 时的距离为 8/8=1。,r的求法：k=(n2 n1 n0),左移m-1位,右边空出补零,得(r)2,亦即(r)2
18、=(k)2 2m-1.例如,N=8:(1)m=1,k=2,k=(010)2 左移0位,(r)2=(010)2=2;(2)m=2,k=1,k=(001)2 左移1位,(r)2=(010)2=2;(3)m=2,k=5,k=(101)2 左移1位,(r)2=(010)2=2.,四.的计算 由于DIF蝶形运算的两节点的距离为 N/2m,所以蝶形运算可表为：,1.相同点(1)进行原位运算；(2)运算量相同,均为（N/2)Log2N次复乘,N Log2N次复加。2.不同点(1)DIT输入为倒位序,输出为自然顺序；DIF正好与此相反。但DIT也有输入为自然顺序,输出为倒位序的情况。,五.DIF法与DIT法的
19、异同,(2)蝶形运算不同,a.(DIT),用矩阵表示,=,1,1,b.(DFT),用矩阵表示,=,1,1,(3)两种蝶形运算的关系 互为转置（矩阵）；,将流图的所有支路方向都反向,交换输入和输出，即可得到另一种蝶形。,a.(DIT),b.(DFT),1,1,1,1,4-4 IFFT算法,一.稍微变动FFT程序和参数可实现IFFT,比较两式可知,只要DFT的每个系数 换成,最后再乘以常数1/N就可以得到IDFT的快速算法-IFFT。另外,可以将常数1/N分配到每级运算中,也就是每级蝶形运算均乘以1/2。,二.不改(FFT)的程序直接实现IFFT,这就是说,先将X(k)取共轭,即将X(k)的虚部乘
20、-1，直接利用FFT程序计算DFT；然后再取一次共轭；最后再乘1/N,即得。所以FFT,IFFT可用一个子程序。,4-5 线性卷积的FFT算法,一.线性卷积的长度 设一离散线性移不变系统的冲激响 应为,其输入信号为.其输出 为.并且 的长度为L点,的 长度为M点,则：,以实例说明：,0 1 2 3,1,2,3,.,。,1,。,。,。,0 1 2 3 4 5,1,3,3,5,6,6,。,二.用FFT算 的步骤：,FFT,FFT,IFFT,x,x(n),h(n),y(n),X(k),H(k),Y(k),流程图,三.几点说明 1.当 M=L 时,用圆周卷积计算线性 卷积的速度快,点数越多,速度越快,N64时,速度增加明显.2.LM 时,速度增加不太明显,为了 增加速度,采用(1)重叠相加法(2)重叠保留法.,放映结束,
