离散傅里叶变换快速算法

2、计算一个 Xm的值需要N次复数乘法运算和N-1次复数加法运算。,所有的Xm就要N2次复数乘法运算，N(N-1)次复数加法运算。,当N很大时，运算量将是惊人的，如N=1024，则要完成1048576 次(一百多万次)运算。,Cooley, James W., and John W. Tukey, “An algorithm for the machine calculation of complex Fourier series,“ Math. Comput. 19, 297301 (1965),1965年，库利(cooley)和图基(Tukey)首先在机器计算傅里叶级数的一种算法文章中提出F

3、FT算法。,http:/ DFT,N/2点 DFT,X10,X11,X12,X13,X20,X21,X22,X23,X0,X4,X1,X5,X2,X6,X3,X7,N/2点 DFT,N/2点 DFT,X10,X11,X12,X13,X20,X21,X22,X23,+,X0,X4,X1,X5,X2,X6,X3,X7,+,+,+,-,-,-,-,N/2点 DFT,N/2点 DFT,将DFT长序列分解为短序列，降低运算次数。,当N很大时，运算量减少了近一半,N点有限长序列的DFT,N/2点有限长序列的DFT,旋转因子的可约性,m范围,如何求？,旋转因子的周期性,旋转因子的对称性,旋转因子,周期性,可

4、约性,对称性,前半部分,后半部分,碟形运算*,8点基2时间抽取FFT算法流图,X10,X11,X12,X13,X20,X21,X22,X23,X 0,X 1,X 2,X 3,X 4,X 5,X 6,X 7,-1,-1,-1,-1,8点基2时间抽取FFT算法流图,第一级,第二级,第三级,这种FFT算法,是在时间上对输入序列的次序是属于偶数还是属于奇数来进行分解的，所以称作按时间抽取的算法(DIT，Decimation in Time)。,二、运算量,当N=8 =23时，由3级蝶形运算组成；每级由4个蝶形运算组成；共有12个蝶形运算；每个蝶形运算有1次复乘，2次复加；共有12次复乘，24次

5、复加；,当N = 2L时，共有L级蝶形，每级N/2个蝶形，每个蝶形有1次复数乘法2次复数加法。,复数乘法：,复数加法：,复数乘法次数与DFT比较：,N点的FFT的运算量：,1024点来说，比值为204.8,FFT算法特点,第一级,第二级,第三级,000,001,010,011,100,101,110,111,000,100,010,110,001,101,011,111,FFT算法特点,级数碟形运算的数量: N/2,第一级,第二级,第三级,000,001,010,011,100,101,110,111,000,100,010,110,001,101,011,111,0 0 0 0 0 0 0

6、 0,自然顺序,二进制k2k1k0,倒位序二进制k0k1k2,倒位顺序,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,倒位序规律,由按时间抽选法FFT运算流图(书140页图3-6)可知，输出Xm按正常顺序排列在存储单元，而输入xk是按顺序:,以N=8为例，说明如下:,x0 x1 x2 x3 x4 x5 x6 x7,x0 x4 x2 x6 x1 x5 x3 x7,变址处理方法,存储单元,自然顺序,变址,倒位序,A(1)

7、 A(2) A(3) A(4) A(5) A(6) A(7) A(8),不必调换数值,交换xk与x 之间数值,1.原位计算,n表示第n级迭代，m，j表示数据所在的行数,输入数据、中间运算结果和最后输出均用同一存储器,第二级的蝶形系数为，蝶形节点的距离为2。,第一级的蝶形系数均为，蝶形节点的距离为1。,第三级的蝶形系数为，蝶形节点的距离为4。,第M级的蝶形系数为，蝶形节点的距离为N /2。,级数碟形运算的数量序列倒序序列原位旋转因子分布,例：试利用N=4基2时间抽取的FFT流图计算8点序列xk=1, -1, 1, -1, 2, 1, 1, 2的DFT。(书上作业3-5),解：,根

8、据基2时间抽取FFT算法原理，8点序列的DFT Xm可由两个4点序列的DFT X1m和X2m表达。如果按照序列xk序号的奇偶分解为x1k和 x2k，则存在,其中x1k=1, 1, 2, 1，x2k=-1, -1, 1, 2，X1m和X2m可通过4点的FFT来计算。,例：试利用N=4基2时间抽取的FFT流图计算8点序列xk=1, -1, 1, -1, 2, 1, 1, 2的DFT。,解：,X1m=5, -1, 1, -1, X2m=1, -2+3j, 1, -2-3j 利用上述公式，可得序列xk的DFT Xm为 Xm=6, -0.293+3.535j, 1+j, -1.707 + 3.535j,

9、 4, -1.707-3.535j, 1-j, -0.293-3.535j,快速傅里叶变换(FFT),基2时间抽取FFT算法与DFT的运算量对比算法的特点,在基-2FFT算法的流图中，当序列长度N=32时，一共有_级蝶形运算，蝶形个数为_，共完成_ 次复数加法、_次复数乘法。若直接完成DFT计算共需要_次复数加法、_次复数乘法。若输入序列按自然顺序排列，序号为13的输出序列号(倒位序)是_。,画出N=4 基-2FFT时间抽取蝶形流程图。,42,本节课内容,按频率抽选的基-2FFT算法*,FFT算法应用,43,3.2 按频率抽取(DIF)的基-2FFT 算法桑德-图基（Sand-Tu

10、key）算法,基2时间抽取FFT算法输入序列xk按其顺序的偶、奇数分解为越来越短的序列。,基2频率抽取(DIF)FFT算法输出序列Xm(也是N点序列)按其顺序的偶、奇来分解为越来越短的序列。,44,一、算法原理,设序列点数N=2L，L为整数。将Xm按m的奇偶分组前，先将输入xk按k的顺序分成前后两半：,45,46,按m的奇偶将Xm分成两部分：,47,则X2r和X2r+1分别是x1k和x2k的 N/2点DFT，记为X1m和X2m，碟形运算为：,令,-1,WNk,48,N/2点 DFT,N/2点 DFT,3,N,W,-1,2,N,W,-1,1,N,W,-1,0,N,W,-1,x0,x4,x1,

11、x5,x2,x6,x3,x7,4点,DFT,X0,X6,X2,X4,4点,DFT,X1,X3,X5,X7,50,N /2仍为偶数，进一步分解：N /2 N /4,51,52,同理：,其中：,X0,X6,X4,X2,X1,X5,X3,X7,0,N,W,1,N,W,2,N,W,3,N,W,-1,-1,-1,-1,x0,x3,x1,x2,x4,x5,x6,x7,0,N,W,2,N,W,2点,DFT,-1,-1,2,N,W,0,N,W,-1,-1,2点,DFT,2点,DFT,2点,DFT,0,N,W,1,N,W,2,N,W,3,N,W,-1,-1,-1,-1,x0,x3,x1,x2,x4,x5,x6,

12、x7,0,N,W,2,N,W,2,N,W,0,N,W,X0,X6,X4,X2,X1,X5,X3,X7,0,N,W,0,N,W,0,N,W,0,N,W,-1,-1,-1,-1,-1,-1,-1,-1,已知有限长序列xk 数值为 1, 2, -1, 3，请按频率抽选的基-2FFT(快速傅里叶变换)运算过程求Xm，并画出蝶形流程图,解：,56,二、算法特点,1. 原位计算,L级蝶形运算，每级N/2个蝶形。,2. 蝶形运算距离,对N=2L点FFT，输入自然序，输出倒位序，两节点距离：2L-n=N/2n,例如 N=23 =8 ： (1)n=1 时的距离为 8/2=4； (2)n=2 时的距离为 8/4=2; (3)n=3 时的距离为 8/8=1。,0,N,W,1,N,W,2,N,W,3,N,W,-1,-1,-1,-1,x0,x3,x1,x2,x4,x5,x6,x7,0,N,W,2,N,W,2,N,W,0,N,W,X0,X6,X4,X2,X1,X5,X3,X7,0,N,W,0,N,W,0,N,W,0,N,W,-1,-1,-1,-1,-1,-1,-1,-1,58,二、算法特点,3. 运算量,级数：log2N,每级的蝶形数：N/2,每蝶形：复乘1次，复加2次,总运算量：复

展开阅读全文