《快速傅里叶变换推演》由会员分享，可在线阅读，更多相关《快速傅里叶变换推演（54页珍藏版）》请在金锄头文库上搜索。
1、 离散傅里叶变换 （ DFT）1. DFT运算量复数乘法复数加法一个X(k)NN 1N个X(k) (N点DFT)N 2N (N 1)实数乘法实数加法 一次复乘42一次复加2一个X (k)4N2N+2 (N 1)=2 (2N 1)N个X (k) (N点DFT)4N 22N (2N 1)快速傅里叶变换 （ FFT）FFT算法分类:时间抽选法 DIT: Decimation-In-Time频率抽选法 DIF: Decimation-In-FrequencyFFT：DFT的快速算法时间抽取法基-2FFT算法基本思想（基-2 Decimation-In-Time FFT） 1、算法原理 设序列点数 N
2、= 2M，M 为整数。若不满足，则补零将序列x(n)按n的奇偶分成两组：N为2的整数幂的FFT算法称基-2FFT算法。n为偶数时:n为奇数时:则x(n)的DFT:其中,结论:G (k),H (k)均为N/2点的DFT。以N=8为例：同理,这就是说, G(k),H(k)的后一半,分别等于其前一半的值。由于 （周期性）,所以:可见,X(k)的后一半，也完全由 G(k), H(k)的前一半所确定。结论：N点的DFT可由两个N/2点的DFT来计算。又由于 ,所以实现上式运算的流图称作蝶形运算前一半蝶形运算后一半（N/2个蝶形)(前一半)(后一半)1 1 1 1-1由G(k)、H(k)表示X(k)的运算
3、是一种特殊的运算-碟形运算图4.2.1 蝶形运算符号 x(0) x(4) N/2点 x(2) DFT x(6) x(1) x(5) N/2点 x(3) DFT x(7) G(0)G(1)G(2)G(3)H(0)H(1)H(2)H(3)WN2WN1WN0WN3-1-1-1-1X(0) X(1) X(2) X(3)X(4) X(5) X(6) X(7)对G (k)和H(k)进行蝶形运算(N=8),前半 部为X(0)- X(3),后半部分为X(4)- X(7) 整个过程如下图所示:由于N=2 M ,所以 N/2仍为偶数,可以进一步把每个N/2点的序列再按其奇偶部分分解为两个N/4的子序列（以G(k)
4、 为例）。N/4点DFTr为偶数时，r=2l, r为奇数时， r=2l+1 R为偶数R为奇数设N=8,则A(k),B(k),都是2点的DFT,不需要再进行DFT,它 们与G(k)的关系为：B(0)A(0)A(1)B(1)G(2)G(0)G(1)G(3)A(0)A(1)x(0)x(4)B(0)B(1)x(2)x(6)对H(k)可以与G(k)类似，分解为：(0)(4)(2)(6)(1)(5)(3)(7)WN0WN0WN0W0N-1-1-1-1A(0)A(1)B(0)B(1)C(0)C(1)D(0)D(1)WN0WN2WN0WN2-1-1-1-1G(0)G(1)G(2)G(3)H(0)H(1)H(2
5、)H(3)WWWWN0N1N2N3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)因此,8点DFT的FFT的运算流图如下N/2分解后的运算量：复数乘法复数加法一个N / 2点DFT(N / 2)2N / 2 (N / 2 1)两个N / 2点DFTN 2 / 2N (N / 2 1)一个蝶形12N / 2个蝶形N / 2N总计运算量减少了近一半4.2.3 基2DIT-FFT算法与直接DFT 运算量的比较当N = 2M时，共有M级蝶形，每级N / 2个蝶形， 每个蝶形有1次复数乘法，2次复数加法。复数乘法：复数加法：与DFT 比较4.2.4 DIF-FFT的运算规
6、律及编程思想1）原位计算DIT-FFT的运算过程很有规律，共进行M级运算， 每级由N/2个蝶形运算组成。同一级中，每个蝶形 的两个输入数据只对计算本蝶形有用，与其它蝶形 运算无关。 这样,蝶形运算的两个输出值仍可放回 蝶形运算的两个输入所在的存储器中,这种利用同 一存储单元存储蝶形计算输入、输出的方法即为原 位运算。每一级(列)有N/2个蝶形运算,所以只需N 个存储单元，可以节省存储单元。运算规律(0)=A0(0) A1(0) A2(0) A3(0)=X(0) (4)=A0(1) A1(1) A2(1) A3(1)=X(1)(2)=A0(2) A3(2)=X(2)(6)=A0(3) A3(3)
7、=X(3)(1)=A0(4) A1(4) A2(4) A3(4)=X(4)(5)=A0(5) A3(5)=X(5)(3)=A0(6) A3(6)=X(6)(7)=A0(7) A1(7) A2(7) A3(7)=X(7)WWWWN0N0N0N0-1-1-1-1WWWWN0N2N0N2-1-1-1-1WWWWNNNN0123. . . . .原位运算的图示输入数据、中间运算结果和最后输出均用同一存储器。L=1L=2L=3开始时，输入序列的N个数放于此N个存储器内，倒序重排后仍存于这N个存储器中，每一次迭代运算后的结果也仍然存于这N个存储器中，整个运算完成后，这N个存储器中即为所求的频谱序列X(k)
8、 （k = 0、1、 N-1）。这就是所谓的同址计算，这样可以大大节约存储元件。 N点DITFFT运 算流图中，每级 都有N/2个蝶形。 每个蝶形都要乘 以因子WpN，称 其为旋转因子，p 称为旋转因子的 指数。 2）旋转引子的变化规律3）蝶形运算规律对N = 2M点FFT，输入倒位序，输出自然顺序， 设第L级运算每个蝶形的两节点距离为 B行，则 第L级运算：旋转因子的确定仅与指数P有关，当L一定时J 可以确定，进而可以确定指数P。对于同一P ，参与本级蝶形运算的次数为 ，每级第 一次调用 的蝶形结第一个输入节点的位 置为J，第二次调用 的蝶形结第一个输入 节点的位置为J+2L，即以2L为步进
9、，搜索下一 蝶形运算第一个输入节点的位置。以此类推， 直至做完 个蝶形运算。同一级中，同一P的蝶形计算完成后，计 算下一个P值对应的蝶形运算，直至完成本级 所有蝶形运算。DIT-FFT原位计算步骤1.确定L； 2.求出第L级的 个 ； 3.对每一个 完成其所参与的 个蝶 形运算， 4. 重复步骤13完成M级蝶形运算。以2L为步进参 与本级同一旋 转因子对应的 其他蝶形运算作为 练习 请写 出L=3 时的 运算 过程 。4） 编程思想及程序框图在一般情况下，进行FFT运算的序列至少都有几百点的长度，因此需要编制FFT算法程序以便能够利用计算机来快速进行计算。输入倒位序，输出顺序的DIT-FFT的
10、编程思想， N必须等于2的正整数幂，FFT的计算程序可以分为两部分：一部分是倒序重排，另一部分是用三层嵌套的循环来完成M=log2N次迭代。 三层循环的功能是：最里的一层循环完成相同WNP的蝶形运算，中间的一层循环完成因子WNP的变化，而最外的一层循环则是完成M次迭代过程。 循环L确定输入数据所在的位 置,循环JL、P、B确定后 进行蝶形计算5） 序列的倒序由DIT-FFT的规律可知,输出X(k) 按正常顺序排列在存储单元,而输入是 按顺序:这种顺序称作倒位序,即二进制 数 倒位。在编程时需完成倒位序，才能 执 行原位计算。n =00n =10n =01n =11n =01n =110 101
11、0101(n2)x(000) 0 x(100) 4 x(010) 2 x(110) 6 x(001) 1x(101) 5 x(011) 3 x(111) 7 （偶）（奇）倒位序由奇偶分组造成,以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 倒位顺序n2 1 0 0 1 2权重：X(I)X(J)最低 位加1若最高位为
12、 0，二进制 最高位加1 ，对应的十 进数加 N/2=4若最高位为 1，最高位 置0，同时 J=J-N/2， 若次高位为 0次高位加 1,J=J+N/4若次高位为1 ，次高位置0 同时J=J-N/4 ，次次高位 加1,J=J+N/8顺序I起始及终止序号为：16倒序J起始序号为：N/2=4 当IJ 时，A(I)和A(J)的内容调换 形成倒序J后，将原存储器放的输入序列重新按倒序排列 。X(I)X(J)I=J 时不 需要 交换图4.2.9 倒序程序框图 确定J的起始序号及I的终 止序号K=N/2最高位为0否？J=J+N/2最高位为1，将最高 位置0，J=J-N/2；次 高位加1，K=N/4，倒序重
13、排的程序是一段经典程序，它以巧妙的构思、简单的语句用高级编程语言来完成了倒序重排的功能。下面是一段用FORTRAN语言编写的倒序重排程序。N=2*M （表示N=2M ，M是输入的正整数） LH=N/2 （LH是一个整数变量）N1=N-2 （N1也是一个整数变量）J=1 （对变量J赋初值）100 DO 7 I=1,N1(循环开始，到语句7结束； 循环变量I从1开始，到N1结束，步长为1) IF (I.GE.J) GOTO 5（如果IJ，就转移到语句5）（将输入序列中序号互为倒序的两个数值交换位置） 5 K=N2 6 IF(K.GE.J) GOTO 7 (如果KJ，就转移到语句7) J=J-kK=K/2GOTO 6 （转移到语句6）7 J=J+K 附：DIT算法的其他形式流图输入倒位序输出自然序输入自然序输出倒位序输入输出均自然序相同几何形状 输入倒位序输出自然序 输入自然序输出倒位序用Matlab方法计算信号的DFT时，是用函数fft(x,N) 和ifft(x.N)。对于这两个函数，如果N为2的正整数幂，则可以得到本章中介绍的基2 FFT快速算法；如果N既不是2的正
