《西交大数字信号处理课件第四讲》由会员分享，可在线阅读，更多相关《西交大数字信号处理课件第四讲（70页珍藏版）》请在金锄头文库上搜索。
1、第四讲 FFT 快速傅氏变换,4-5线性卷积的FFT算法,4-3按频率抽取DIF的FFT算法,4-4 IFFT算法,4-2按时间抽取(DIT)的FFT算法,4-1 引言,目 录,4-1引言,一.DFT的计算工作量 两者的差别仅在指数的符号和因子1/N.,通常x(n)和 都是复数,所以计算一个 X(k)的值需要N次复数乘法运算,和 次 复数加法运算.那么,所有的X(k)就要N2次复 数乘法运算,N(N-1)次复数加法运算.当N很 大时,运算量将是惊人的,如N=1024,则要完 成1048576 次(一百多万次)运算.这样,难以做到实时处理.,一个X(k)的值的工作量,如X(1),二.改进的途径,
2、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倍,4-2 按时间抽取(DIT)的FFT算法 库利-图基算法,一.算法原理(基2FFT) (一)N/2点DFT 1.先将 按n的奇偶分为两组作DFT,设N=2L ,不足时,
3、可补些零。这样有: 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)的后一半，也完全由X1(k), X2(k)的前一半所确定。 *N点的DFT可由两个N/2点的DFT来计算。,又由于 ,所以,实现上式运算的流图称
4、作蝶形运算,前一半,4.蝶形运算,后一半,（N/2个蝶形),(前一半),(后一半),1 1,1,1,-1,由X1(k)、X 2(k)表示X(k)的运算是一种特殊的运算-碟形运算,(1)N/2点的DFT运算量:复乘次数: 复加次数: (2)两个N/2点的DFT运算量:复乘次数: 复加次数: (3)N/2个蝶形运算的运算量:复乘次数: 复加次数:,5.计算工作量分析,复乘:,复加:,总共运算量:,按奇、偶分组后的计算量：,*但是,N点DFT的复乘为N2 ;复加N(N-1);与 分解后相比可知,计算工作点差不多减少 一半。,例如 N=8 时的DFT,可以分解为两个 N/2=4点的DFT.具体方法如下
5、: (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) 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(
6、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,得到,(偶中偶),(偶中奇),从而可得到前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),
7、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）由 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)=
8、(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(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
9、)进行碟形运算, 得到 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,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的F
10、FT的运算流图如下,这种FFT算法,是在时间上对输入序列 的次序是属于偶数还是属于奇数来进行分 解的,所以称作按时间抽取的算法 。 二.运算量 由上述分析可知,N=8需三级蝶形运算 N=2 =8,由此可知,N=2L 共需L级蝶形运算, 而且每级都由N/2个蝶形运算 组成,每个蝶 形运算有一次复乘,两次复加。,(DIT),3,因此,N点的FFT的运算量为 复乘: mF =（N/2）L=（N/2） log2 N 复加: aF =N L=N log2 N,(0)=X0(0) X1(0) X2(0) X3(0)=X(0) (4)=X0(1) X1(1) X2(1) X3(1)=X(1) (2)=X0(
11、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,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.原位运算,输入数据、中间运算结果和最后输出均
12、用同一存储器。,设用m(m=1,2, ,L)表示第m列;用k,j表示蝶形 输入数据所在的（上/下）行数(0,1,2, ,N-1);这时任何一个蝶形运算可用下面通用式表示， 即,由运算流图可知,一共有N个输入/出行,一共有log2 N=L列（级）蝶形运算(基本迭代运算).,所以,当m=1时,则有（前两个蝶形）,当m=2时,则有（前两个蝶形） 当m=3时,则有（前两个蝶形）,可见,在某列进行蝶形运算的任意两个节点(行)k和j的节点变量 就完全可以确定蝶形运算的结果 ,与其它行(节点)无关。 这样,蝶形运算的两个输出值仍可放回蝶形运算的两个输入所在的存储器中,即实现所谓原位运算。每一组(列)有N/2
13、个蝶形运算,所以只需N个存储单元，可以节 省存储单元。,2 倒位序规律 由图可知,输出X(k)按正常顺序排 列在存储单元,而输入是按顺序: 这种顺序称作倒位序,即二进制数 倒位。,这是由奇偶分组造成的,以N=8为例 说明如下:,3.倒位序实现 输入序列先按自然顺序存入存储单 元,然后经变址运算来实现倒位序排列 设输入序列的序号为n,二进制为 (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
14、 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 ,第一级(列)距离为21-1=1, 第二级(列)距离为22-1=2， 第三级(列)距离为23-1=4。,5.WNr 的确定(仅给出方法) 考虑蝶形运算两节点的距离为2m-1 ,蝶 形运算可表为 Xm(k)=Xm-1(k)+Xm-1(k+2m-1)WNr Xm(k+2m-1)=Xm-1(k)-Xm-1(k+2m-1)WNr 由于N为已知,所以将r的值确定即可。,为此，令k=(n2n1n0)2 ,再将k= (n2n1n0)2 左移(L-m)位,右边位
