4-快速傅里叶变换解析

1、第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 1第第4章章 快速傅里叶变换快速傅里叶变换 4.1 引言引言 4.2 直接计算直接计算DFT的问题及改进的途径的问题及改进的途径 4.3 按时间抽取（按时间抽取（DIT）的基）的基2-FFT算法算法4.4 按频率抽取（按频率抽取（DIF）的基）的基2-FFT算法算法4.5 离散傅里叶反变换（离散傅里叶反变换（IDFT）的快速计算方法）的快速计算方法 4.10 线性卷积的线性卷积的FFT算法算法 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 24.1 引引 言言 快速傅里叶变换（快速傅里叶变换（FFT）并不是一种新的变换，并不是一种新的变

2、换， 而是而是离散傅里叶变换离散傅里叶变换（DFT）的一种快速算法）的一种快速算法。 由于有限长序列在其频域也可离散化为有限长序列（由于有限长序列在其频域也可离散化为有限长序列（DFT），因此离散），因此离散傅里叶变换（傅里叶变换（DFT）在数字信号处理中是非常有用的。例如，在信号的频谱）在数字信号处理中是非常有用的。例如，在信号的频谱分析、分析、 系统的分析、系统的分析、 设计和实现中都会用到设计和实现中都会用到DFT的计算。的计算。 但是，在相当长但是，在相当长的时间里，的时间里， 由于由于DFT的计算量太大的计算量太大，即使采用计算机也很难对问题进行实时，即使采用计算机也很难对问题进行实

3、时处理，所以并没有得到真正的运用。处理，所以并没有得到真正的运用。 直到直到1965年首次发现了年首次发现了DFT运算的一种运算的一种快速算法以后，情况才发生了根本的变化。人们开始认识到快速算法以后，情况才发生了根本的变化。人们开始认识到DFT运算的一些运算的一些内在规律，从而很快地发展和完善了一套高速有效的运算方法，内在规律，从而很快地发展和完善了一套高速有效的运算方法， 这就是现在这就是现在人们普遍称之为快速傅里叶变换（人们普遍称之为快速傅里叶变换（FFT）的算法。）的算法。 FFT出现后使出现后使DFT的运算的运算大大简化，运算时间一般可缩短一二个数量级之多，从而使大大简化，运算时间一般

4、可缩短一二个数量级之多，从而使DFT的运算在实的运算在实际中真正得到了广泛的应用。际中真正得到了广泛的应用。 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 34.2 直接计算直接计算DFT的问题及改进的途径的问题及改进的途径 一、直接计算一、直接计算DFT的运算量的运算量 设设x(n)为为N点有限长序列，其点有限长序列，其DFT为为 10)()(NnnkNWnxkXk=0, 1, , N-1 （4-1） 反变换（反变换（IDFT）为）为 101( )( )NnkNkx nX k WNn=0, 1, , N-1 （4-2） 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4 二者的差别

5、只在于二者的差别只在于WN的指数符号不同，以及差一个常数乘的指数符号不同，以及差一个常数乘因子因子1/N，所以，所以IDFT与与DFT具有相同的运算工作量。具有相同的运算工作量。 下面我们下面我们只讨论只讨论DFT的运算量。的运算量。 一般来说，一般来说，x(n)和和WNnk都是复数，都是复数，X(k)也是复数，因此每也是复数，因此每计算一个计算一个X(k)值值，需要，需要N次复数乘法次复数乘法和和N-1次复数加法次复数加法。而。而X(k)一共有一共有N个点（个点（k从从0取到取到N-1），所以），所以完成整个完成整个DFT运算运算总共需总共需要要N2次复数乘法次复数乘法及及N(N-1)次复数

6、加法次复数加法。 在这些运算中乘法运算在这些运算中乘法运算要比加法运算复杂，需要的运算时间也多一些。因为复数运算要比加法运算复杂，需要的运算时间也多一些。因为复数运算实际上是由实数运算来完成的，实际上是由实数运算来完成的， 这时这时DFT运算式可写成运算式可写成 10)()(NnnkNWnxkX101( )( )NnkNkx nX k WN反变换：反变换：正变换：正变换：第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 5)Re)(ImIm)(ReIm)(ImRe)(ReIm)Re(Im)(Re)()(101010nkNnkNnkNNnnkNNnnkNnkNNnnkNWnxWnxjWnxWn

7、xWjWnxjnxWnxkX（4-3） 由此可见，由此可见，一次复数乘法一次复数乘法需用需用四次实数乘法四次实数乘法和和二次实数加法二次实数加法；一次复数加法需二次实数加法。一次复数加法需二次实数加法。 因而每因而每运算一个运算一个X(k)需需4N次实次实数乘法数乘法和和2N+2(N-1)=2(2N-1)次实数加法次实数加法。 所以，所以，整个整个DFT运算运算总共需要总共需要4N2次实数乘法次实数乘法和和2N(2N-1)次实数加法次实数加法。 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 6 当然，上述统计与实际需要的运算次数稍有出入，因为某当然，上述统计与实际需要的运算次数稍有出入，

8、因为某些些WNnk可能是可能是1或或j，就不必相乘了，例如，就不必相乘了，例如W0N=1，W N=-1， WNN/4=-j等就不需乘法。等就不需乘法。 但是为了便于和其他运算方法作比较，但是为了便于和其他运算方法作比较， 一般都不考虑这些特殊情况，而是把一般都不考虑这些特殊情况，而是把WNnk都看成复数，当都看成复数，当N很很大时，这种特例的影响很小。大时，这种特例的影响很小。 从上面的统计可以看到，从上面的统计可以看到，直接计算直接计算DFT，乘法次数和加法，乘法次数和加法次数都是和次数都是和N2成正比的成正比的，当当N很大时，运算量是很可观的，有很大时，运算量是很可观的，有时是无法忍受的。

9、时是无法忍受的。 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 7 例例3-1 根据式（根据式（3-1），对一幅），对一幅NN点的二维图像进行点的二维图像进行DFT变换，如用每秒可做变换，如用每秒可做10万次复数乘法的计算机，当万次复数乘法的计算机，当N=1024时，时，问需要多少时间（不考虑加法运算时间）？问需要多少时间（不考虑加法运算时间）？ 解解 直接计算直接计算DFT所需复乘次数为（所需复乘次数为（N2)21012次，因此用每次，因此用每秒可做秒可做10万次复数乘法的计算机，则需要近万次复数乘法的计算机，则需要近3000小时。小时。 这对实时性很强的信号处理来说，要么提高计算速度

10、，而这这对实时性很强的信号处理来说，要么提高计算速度，而这样，对计算速度的要求太高了。另外，只能通过改进对样，对计算速度的要求太高了。另外，只能通过改进对DFT的计的计算方法，以大大减少运算次数。算方法，以大大减少运算次数。 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 8二、二、 改善途径改善途径 能否减少运算量，从而缩短计算时间呢？仔细观察能否减少运算量，从而缩短计算时间呢？仔细观察DFT的运算就可看出，的运算就可看出， 利用系数利用系数Wnk的以下固有特性，就可减少运的以下固有特性，就可减少运算量：算量： （1） WNnk的共轭对称性的共轭对称性 nkNnkNWW*)(（2） WN

11、nk的周期性的周期性 )()(NknNkNnNnkNWWW（3） WNnk的可约性的可约性 mnkmNnkNnmkmNnkNWWWW/,第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 9另外另外 kNNkNNNnkNknNNkNnNWWWWWW)2/(2/)()(, 1, 这样，利用这些特性，使这样，利用这些特性，使DFT运算中有些项可以合并，运算中有些项可以合并，并能使并能使DFT分解为更少点数的分解为更少点数的DFT运算。由于运算。由于DFT的运算的运算量是与量是与N2成正比的，所以成正比的，所以N越小越有利，因而小点数序列越小越有利，因而小点数序列的的DFT比大点数序列的比大点数序列

12、的DFT的运算量要小。的运算量要小。 快速傅里叶变换算法正是基于这样的基本思想而发展快速傅里叶变换算法正是基于这样的基本思想而发展起来的。它的算法形式有很多种，但基本上可以分成两大起来的。它的算法形式有很多种，但基本上可以分成两大类：类： 按时间抽取按时间抽取(ecimation inTime，缩写为，缩写为DIT)法法 按频率抽取按频率抽取(Decimationin Frequency，缩写为，缩写为DIF)法法第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 104.3 按时间抽取按时间抽取(DIT)的的基基-2 FFT算法算法 (库利库利-图基算法图基算法)一、一、 算法原理算法原理

13、设序列设序列x(n)长度为长度为N，且满足，且满足N=2L，L为正整数。按为正整数。按n的奇的奇偶把偶把x(n)分解为两个分解为两个N/2点的子序列：点的子序列： 12, 1 , 0)() 12()()2(21Nrrxrxrxrx（4-4） 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 11则可将则可将DFT化为化为 111000( ) ( )( )( )( )NNNnknknkNNNnnnnnX kDFT x nx n Wx n Wx n W为偶数为奇数由于由于 ， 则上式可表示成则上式可表示成 2222/2/2jjNNNNWeeW111221/22/2200( )( )( )( )(

14、 )NNkNrkkrkNNNrrX kxX kr WW XWkx r W（4-5） 11222(21)001122221200(2 )(21)( )()( )()NNrkrkNNrrNNrkkrkNNNrrxr WxrWx r WWx r W第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 12式中，式中，X1(k)与与X2(k)分别是分别是x1(r)及及x2(r)的的N/2点点DFT： rkNNrrkNNrrkNNrrkNNrWrxWrxkXWrxWrxkX2/1202/212022/1202/11201)12()()()2()()(（4-6） （4-7） X1(k)，X2(k)只有只有N

15、/2个点，即个点，即k=0, 1, , N/2-1。而而X(k)却有却有N个点，即个点，即k=0, 1, , N-1， 故用故用式（式（4-5）计算得到的只是计算得到的只是X(k)的前一半的结果的前一半的结果:11221/22/21200( )( )( )( )( ),NNrkkrkkNNNNrrX kx r WWx r WX kW Xk12, 1 , 0Nk第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 13rkNNkrNWW2/22/（周期性）（周期性）由于由于1122()()()2221/2/200()( )(21),2NNNNNr kkr kNNNrrNX kx r WWxrW再考

16、虑到再考虑到WkN 的以下性质的以下性质: kNkNNNkNNWWWW2/211221/22/20012()( )( )2( )( ),NNrkkrkNNNrrkNNX kx r WWx r WX kW Xk所以所以X(k)的后一半结果为的后一半结果为:12, 1 , 0Nk12, 1 , 0Nk第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 1412,( )( )( )0,1,12kNNX kX kW Xkk21212222( )( ),NkNkNNNNX kXkWXkX kW Xk12, 1 , 0Nk（4-11） （4-12） 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 15

17、图图 4-1 时间抽选法蝶形运算流图符号时间抽选法蝶形运算流图符号 X2(k)X1(k)kNW1X1(k)kNWX2(k)X1(k)kNWX2(k)12, 1 , 0)()()(21NkkXWkXkXkN12( )( )0,1,122kNNNXkX kW Xkk.蝶形运算蝶形运算这样，就可将这样，就可将X(k)表达为前后两部分：表达为前后两部分： 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 16图图 4-2 按时间抽选将一个按时间抽选将一个N点点DFT分解分解 为两个为两个N/2点点DFT（N=8） X1(0)X1(1)x1(0) x(0)X(0)X(1)X1(2)X1(3)110NW

18、DFT2点Nx1(1) x(2)x1(2) x(4)x1(3) x(6)X(2)X(3)X2(0)X2(1)x2(0) x(1)X(4)X(5)X2(2)X2(3)DFT2点Nx2(1) x(3)x2(2) x(5)x2(3) x(7)X(6)X(7)1NW2NW3NW1112, 1 ,0)()()(21NkkXWkXkXkN12( )( )0,1,122kNNNXkXkWXkk12(2 )( )(21)( )0,1,12xrx rxrx rNr第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 17(1)N/2点的点的DFT运算量运算量: 复乘次数复乘次数:复加次数复加次数:(2)两个两个N

19、/2点的点的DFT运算量运算量:复乘次数复乘次数:复加次数复加次数: (3)N/2个蝶形运算的运算量个蝶形运算的运算量:复乘次数复乘次数:复加次数复加次数: 运算量运算量复乘复乘:复加复加:总共运算量总共运算量: *N点点DFT的复乘为的复乘为N2 ;复加复加N(N-1);与分解后相比可知与分解后相比可知,计算工作点差不多减少计算工作点差不多减少 一半。一半。22()24NN(1)22NN22N(1)2NN2N22NN22(1)/ 2222NNNNN2(1)22NNNN第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 18 由于由于N=2L，因而，因而N/2仍是偶数，可以进一步把每个仍是偶数

20、，可以进一步把每个N/2点子序列再按其奇偶部分分解为两个点子序列再按其奇偶部分分解为两个N/4点的子序列。点的子序列。 1314(2 )( )0,1,1(21)( )4xlx lNlxlx l（4-13） 14, 1 , 0)()()()() 12()2()(42/31404/42/1404/3140)12(2/114022/11NkkXWkXWlxWWlxWlxWlxkXkNNllkNkNNllkNNlklNNllkN例如，例如，n为偶数时的为偶数时的 N/2点分解为点分解为:第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 19且且 )()(442/31kXWkXkNXkN14, 1 ,

21、 0Nk式中：式中： 1404/441404/33)()()()(NllkNNllkNWlxkXWlxkX（4-14） （4-15） 图图4-3给出给出N=8时，将一个时，将一个N/2点点DFT分解成两个分解成两个N/4点点DFT， 由这两个由这两个N/4点点DFT组合成一个组合成一个N/2点点DFT的流图。的流图。 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 20图图 4-3 N/2点点DFT分解为两个分解为两个N/4点点DFT DFT4点NX3(0)X3(1)x3(0) x1(0) x(0)x3(1) x1(2) x(4)X1(0)X1(1)DFT4点NX4(0)X4(1)x4(0

22、) x1(1) x(2)x4(1) x1(3) x(6)X1(2)X1(3)1102/NW12/NW12(2 )( )0,1,1(21)( )2xrx rNrxrx r1314(2 )( )0,1,1(21)( )4xlx lNlxlx l第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 21X2(k)也可进行同样的分解：也可进行同样的分解： )()(4)()()(62/5262/52kXWkXkNXkXWkXkXkNkN14, 1 , 0Nk式中：式中： 1404/21404/661404/21404/55) 12()()()2()()(NllkNNllkNNllkNNllkNWlxWlx

23、kXWlxWlxkX同样对同样对n为奇数时，为奇数时，N/2点分为两个点分为两个N/4点点 的序列进行的序列进行DFT第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 22图图 4-4 一个一个N=8点点DFT分解为四个分解为四个N/4点点DFT DFT4点NX3(0)X3(1)x3(0) x1(0) x(0)x3(1) x1(2) x(4)X1(0)X1(1)DFT4点NX4(0)X4(1)x4(0) x1(1) x(2)x4(1) x1(3) x(6)X1(2)X1(3)110NW2NWX(0)X(1)X(2)X(3)DFT4点NX5(0)X5(1)x5(0) x2(0) x(1)x5(

24、1) x2(2) x(5)X2(0)X2(1)DFT4点NX6(0)X6(1)x6(0) x2(1) x(3)x6(1) x2(3) x(7)X2(2)X2(3)11X(4)X(5)X(6)X(7)0NW1NW2NW3NW11110NW2NW第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 23 根据上面同样的分析知道，利用四个根据上面同样的分析知道，利用四个N/4点的点的DFT及两级蝶及两级蝶形组合运算来计算形组合运算来计算N点点DFT，比只用一次分解蝶形组合方式的，比只用一次分解蝶形组合方式的计算量又减少了大约一半。计算量又减少了大约一半。 对于对于N=8时的时的DFT, N/4点即为两

25、点点即为两点DFT,因此因此 133/40144/40155/40166/40( )( ), k0,1( )( ), k0,1( )( ), k0,1( )( ), k0,1lkNllkNllkNllkNlXkx l WXkx l WXkx l WXkx l W第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 24式中，式中， , 故上式不需要乘法。故上式不需要乘法。0122121NjjWeeW可得：可得：004424104424(0)(0)(1)(2)(6)(1)(0)(1)(2)(6)NNXxW xxW xXxW xxW x005525105525(0)(0)(1)(1)(5)(1)(0

26、)(1)(1)(5)NNXxW xxW xXxW xxW x006626106626(0)(0)(1)(3)(7)(1)(0)(1)(3)(7)NNXxW xxW xXxW xxW x003323103323(0)(0)(1)(0)(4)(1)(0)(1)(0)(4)NNXxW xxW xXxW xxW x第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 25 这种方法的每一步分解，都是这种方法的每一步分解，都是按输入序列在时间上的次序按输入序列在时间上的次序是属于偶数还是属于奇数来分解是属于偶数还是属于奇数来分解为两个更短的子序列，所以称为两个更短的子序列，所以称为为“按时间抽取法按时间抽

27、取法”。 图图 4-5 N=8 按时间抽取的按时间抽取的FFT运算流图运算流图x(0)X(0)x(4)X(1)10NWx(2)X(2)x(6)X(3)10NW0NW2NW11x(1)X(4)x(5)X(5)10NWx(3)X(6)x(7)X(7)10NW0NW2NW110NW1NW2NW3NW1111第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 26二、二、 运算量运算量 由按时间抽取法由按时间抽取法FFT的流图可见，当的流图可见，当N=2L时，共有时，共有L级级蝶形，蝶形， 每级都由每级都由N/2个蝶形运算组成，每个蝶形需要一次复个蝶形运算组成，每个蝶形需要一次复乘、乘、 二次复加，因

28、而每级运算都需二次复加，因而每级运算都需N/2次复乘和次复乘和N次复加，次复加，这样这样L级运算总共需要级运算总共需要 复乘数复乘数 22log22logFFNNmLNaNLNN复加数复加数 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 27 由于计算机上乘法运算所需的时间比加法运算所需由于计算机上乘法运算所需的时间比加法运算所需的时间多得多，故以乘法为例，直接的时间多得多，故以乘法为例，直接DFT复数乘法次数复数乘法次数是是N2，FFT复数乘法次数是复数乘法次数是(N/2) log2N。 直接计算直接计算DFT与与FFT算法的计算量之比为算法的计算量之比为 22222loglog22N

29、NNNNNLN当当N=2048时，这一比值为时，这一比值为372.4，即直接计算，即直接计算DFT的运算量的运算量是是FFT运算量的运算量的372.4倍。当点数倍。当点数N越大时，越大时，FFT的优点更为的优点更为明显明显(见书中见书中P150.表表4-1)。 （4-20） 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 28 三、按时间抽取的三、按时间抽取的FFT算法的特点算法的特点 1. 原位运算（同址运算）原位运算（同址运算） 从从图图4-5可以看出这种运算是很有规律的，其每级（每列）可以看出这种运算是很有规律的，其每级（每列）计算都是由计算都是由N/2 个蝶形运算构成的，每一个蝶形

30、结构完成下述个蝶形运算构成的，每一个蝶形结构完成下述基本迭代运算：基本迭代运算： rNmmmrNmmmWjXkXjXWjXkXkX)()()()()()(1111（4-21a） （4-21b） 式中，式中，m表示第表示第m列迭代，列迭代，k, j为数据所在行数。式（为数据所在行数。式（4-21）的蝶）的蝶形运算形运算如图如图4-7所示，由一次复乘和两次复加（减）组成。所示，由一次复乘和两次复加（减）组成。 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 29图图 4-7 按时间抽选的蝶形运算结构按时间抽选的蝶形运算结构1rNWXm1(k)Xm1( j)Xm(k) Xm1(k) Xm1( j

31、)Xm( j) Xm1(k) Xm1( j)rNWrNW 在某列进行蝶形运算的任意两个节点在某列进行蝶形运算的任意两个节点(行行)k和和j的节点变量的节点变量 就完全可以确定蝶形运算的结果就完全可以确定蝶形运算的结果 ,与其它行与其它行(节点节点)无关。无关。 这样这样,蝶形运算的两个输出值仍可放蝶形运算的两个输出值仍可放回蝶形运算的两个输入所在的存储器中回蝶形运算的两个输入所在的存储器中,即实现所谓即实现所谓原位运原位运算算。每一组每一组(列列)有有N/2个蝶形运算个蝶形运算,所以只需所以只需N个存储单元，个存储单元，可以节省存储单元。可以节省存储单元。11( ),( )mmXkXj( ),

32、( )mmXkXj第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 30 由由图图4-5的流图看出，某一列的任何两个节点的流图看出，某一列的任何两个节点k和和j的节点变的节点变量进行蝶形运算后，得到结果为下一列量进行蝶形运算后，得到结果为下一列k, j两节点的节点变量，两节点的节点变量，而和其他节点变量无关，因而可以采用原位运算，即某一列的而和其他节点变量无关，因而可以采用原位运算，即某一列的N个数据送到存储器后，经蝶形运算，其结果为下一列数据，它们个数据送到存储器后，经蝶形运算，其结果为下一列数据，它们以蝶形为单位仍存储在这同一组存储器中，直到最后输出，中间以蝶形为单位仍存储在这同一组存储

33、器中，直到最后输出，中间无需其他存储器。也就是蝶形的两个输出值仍放回蝶形的两个输无需其他存储器。也就是蝶形的两个输出值仍放回蝶形的两个输入所在的存储器中。每列的入所在的存储器中。每列的N/2 个蝶形运算全部完成后，再开始个蝶形运算全部完成后，再开始下一列的蝶形运算。这样存储器数据只需下一列的蝶形运算。这样存储器数据只需N个存储单元。下一级个存储单元。下一级的运算仍采用这种原位方式，只不过进入蝶形结的组合关系有所的运算仍采用这种原位方式，只不过进入蝶形结的组合关系有所不同。不同。 这种这种原位运算结构可以节省存储单元，降低设备成本。原位运算结构可以节省存储单元，降低设备成本。 第第4章章 快速傅

34、里叶变换快速傅里叶变换(FFT) 31 2. 倒位序规律倒位序规律 FFT的输出的输出X(k)按正常顺序排列在存储单元中，即按按正常顺序排列在存储单元中，即按X(0)，X(1)，X(7)的顺序排列，但是这时输入的顺序排列，但是这时输入x(n)却不是按自然顺却不是按自然顺序存储的，而是按序存储的，而是按x(0)，x(4)， ， x(7)的顺序存入存储单元，的顺序存入存储单元，看起来好像是看起来好像是“混乱无序混乱无序”的，实际上是有规律的，我们称之的，实际上是有规律的，我们称之为倒位序。为倒位序。 这是由奇偶分组造成的这是由奇偶分组造成的,以以N=8为例为例 说明如下说明如下:第第4章章 快速傅

35、里叶变换快速傅里叶变换(FFT) 32 造成倒位序的原因是输入造成倒位序的原因是输入x(n)按标号按标号n的偶奇的不断分组。的偶奇的不断分组。 如果如果n用二进制数表示为用二进制数表示为(n2n1n0)2（当（当N=8=23时，二进制为三时，二进制为三位），位）， 第一次分组，由图第一次分组，由图4-2看出，看出，n为偶数（相当于为偶数（相当于n的二进制的二进制数的最低位数的最低位n0=0）在上半部分，）在上半部分，n为奇数（相当于为奇数（相当于n的二进制数的二进制数的最低位的最低位 n0=1）在下半部分。）在下半部分。 下一次则根据次最低位下一次则根据次最低位n1为为“0”或是或是“1”来分

36、偶奇（而不管原来的子序列是偶序列还是奇序来分偶奇（而不管原来的子序列是偶序列还是奇序列），列）， 如此继续分下去，直到最后如此继续分下去，直到最后N个长度为个长度为1的子序列。的子序列。 图图4-8的树状图描述了这种分成偶数子序列和奇数子序列的过程。的树状图描述了这种分成偶数子序列和奇数子序列的过程。 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 33图图4-8 描述倒位序的树状图描述倒位序的树状图 x(000)x(100)x(010)x(110)010101x(001)x(101)x(011)x(111)01010101x(n2n1n0)n2n1n0第第4章章 快速傅里叶变换快速傅里叶

37、变换(FFT) 34 3.倒位序实现倒位序实现 输入序列先按自然顺序存入存储单元输入序列先按自然顺序存入存储单元,然后经变址运算来然后经变址运算来实现实现倒位序排列倒位序排列。 设输入设输入序列的序号为序列的序号为n,二进制为二进制为(n2 n1 n0 )2 , 倒位序倒位序顺序用顺序用 表示表示,其倒位序其倒位序二进制为二进制为(n0 n1 n2 )2 , 例如例如 ，N=8时如下表：时如下表：表表4-2 码位的倒位序（码位的倒位序（N=8）自然顺序（n） 二进制数 倒位序二进制数 倒位序顺序（） 01234567000001010011100101110111000100010110001

38、10101111104261537第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 35图图 4-9 倒位序的变址处理倒位序的变址处理 (N=8)存储单元自然顺序输入变址倒位序A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)变址处理方法变址处理方法第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 36 4. 蝶形运算两节点的蝶形运算两节点的“距离距离” 以以图图4-5的的8点点FFT为例，其输入是倒位序的，输出是自然顺为例，其输入是倒位序的，输出是

39、自然顺序的。序的。 其第一级（第一列）每个蝶形的两节点间其第一级（第一列）每个蝶形的两节点间“距离距离”为为1， 第二级每个蝶形的两节点第二级每个蝶形的两节点“距离距离”为为2， 第三级每个蝶形的两节第三级每个蝶形的两节点点“距离距离”为为4。 由此类推得，对由此类推得，对N=2L点点FFT，当输入为倒位，当输入为倒位序，序， 输出为正常顺序时，其第输出为正常顺序时，其第m级运算，级运算，每个蝶形的两节点每个蝶形的两节点“距离距离”为为2m-1。 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 37 5. WNr的确定的确定 由于对第由于对第m级运算，一个级运算，一个DFT蝶形运算的两节点

40、蝶形运算的两节点“距离距离”为为2m-1， 因而式（因而式（4-21）可写成）可写成: rNmmmmmrNmmmmWkXkXkXWkXkXkX)2()()2()2()()(1111111（4-22a） （4-22b） 为了完成上两式运算，还必须知道系数为了完成上两式运算，还必须知道系数Nr的变换规律：的变换规律： 把式（把式（4-22）中蝶形运算两节点中的第一个节点标号值，）中蝶形运算两节点中的第一个节点标号值， 即即k值，表示成值，表示成L位（注意位（注意N=2L）二进制数；）二进制数； 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 38 把此二进制数乘上把此二进制数乘上2L-m，即将

41、此，即将此L位二进制数左移位二进制数左移L-m位（注意位（注意m是第是第m级运算），把右边空出的位置补零，级运算），把右边空出的位置补零， 此数即此数即为所求为所求r的二进制数。的二进制数。 从图从图4-5看出，看出，WNr因子最后一列有因子最后一列有N/2种，顺序为种，顺序为WN0， WN1， ， 其余可类推。其余可类推。 12NNW第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 39 6.存储单元存储单元 存输入序列存输入序列 需需N个存储单元个存储单元存放系数存放系数 需需N/2个存储单元；个存储单元； 共计共计需需(N+N/2)个存储单元。个存储单元。(n)(n=0,1, ,N-1

42、)x(r=0,1, ,N/2 - 1)rNW第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 40四、四、 按时间抽取的按时间抽取的FFT算法的其他形式流图算法的其他形式流图 显然，显然，对于任何流图，只要保持各节点所连的支路及传输对于任何流图，只要保持各节点所连的支路及传输系数不变，则不论节点位置怎么排列所得流图总是等效的，所系数不变，则不论节点位置怎么排列所得流图总是等效的，所得最后结果都是得最后结果都是x(n)的的DFT的正确结果的正确结果，只是数据的提取和存，只是数据的提取和存放的次序不同而已。这样就可得到按时间抽取的放的次序不同而已。这样就可得到按时间抽取的FFT算法的若算法的若干

43、其他形式流图。干其他形式流图。 将图将图4-5中和中和x(4)水平相连的所有节点和水平相连的所有节点和x(1)水平相连的所水平相连的所有节点位置对调，再将和有节点位置对调，再将和x(6)水平相连的所有节点与和水平相连的所有节点与和x(3)水平水平相连的所有节点对调，其余诸节点保持不变，可得相连的所有节点对调，其余诸节点保持不变，可得图图4-10的流的流图。图。 图图4-10与图与图4-5的蝶形相同，运算量也一样，不同点是：的蝶形相同，运算量也一样，不同点是： 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 41 数据存放的方式不同，图数据存放的方式不同，图4-5是输入倒位序、输出自然是输入

44、倒位序、输出自然顺序，图顺序，图4-10是输入自然顺序、输出倒位序；是输入自然顺序、输出倒位序； 取用系数的顺序不同，图取用系数的顺序不同，图4-5的最后一列是按的最后一列是按 的顺序取用系数，且其前一列所用系数是的顺序取用系数，且其前一列所用系数是后 一 列 所 用 系 数 中 具 有 偶 数 幂 的 那 些 系 数 （ 例 如后 一 列 所 用 系 数 中 具 有 偶 数 幂 的 那 些 系 数 （ 例 如 ） ； 图） ； 图 4 - 1 0 是 最 后 一 列 是 按是 最 后 一 列 是 按 的顺序取用系数，且其前一列所用系数是后一列所用系数的前的顺序取用系数，且其前一列所用系数是后

45、一列所用系数的前一半，一半， 这种流图是最初由库利和图基给出的时间抽取法。这种流图是最初由库利和图基给出的时间抽取法。 经过简单变换，也可得输入与输出都是按自然顺序排列的经过简单变换，也可得输入与输出都是按自然顺序排列的流图以及其他各种形式的流图流图以及其他各种形式的流图 。3210,NNNNWWWW,20NNWW3120,NNNNWWWW第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 42图图 4-10 时间抽取、时间抽取、 输入自然顺序、输入自然顺序、 输出倒位序的输出倒位序的FFT流图流图 0NW0NW0NW2NW1110NW10NW2NW1111X(0)x(0)X(4)x(1)X(

46、2)x(2)X(6)x(3)X(1)x(4)X(5)x(5)X(3)x(6)X(7)x(7)110NW0NW2NW1NW3NW11第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 434.4 按频率抽取（按频率抽取（DIF）的基）的基 -2 FFT算法（桑德算法（桑德-图基算法）图基算法） 一、一、 算法原理算法原理 仍设序列点数为仍设序列点数为N=2L，L为正整数。在把输出为正整数。在把输出X(k)按按k的奇的奇偶分组之前，先把输入序列按前一半、后一半分开（不是按偶偶分组之前，先把输入序列按前一半、后一半分开（不是按偶数、数、 奇数分开），奇数分开）， 把把N点点DFT写成两部分。写成两部

47、分。 1112002112220012/20( )( )( )( )( )2( )2NNNnknknkNNNNnnnNNNnknkNNnnNNknkNNnX kx n Wx nWx n WNx nWx nWNx nx nWWk=0, 1, , N-1 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 44由于由于 ，故，故，可得，可得1nkNWkNkNW) 1(2/nkNNnkWNnxnxkX1202) 1()()( k=0, 1, , N-1 当当k为偶数时，为偶数时，(-1)k=1；k为奇数时，为奇数时，(-1)k=-1。因此，按。因此，按k的奇偶可将的奇偶可将X(k)分为两部分分为两部

48、分: nrNNnnkNNnWNnxnxWNnxnxrX2/12021202)(2)()2(12, 1 , 0Nr为前一半输入与后一半输入之和的N/2点DFT第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 45nrNNnnNrnNNnWWNnxnxWNnxnxrX2/120)12(1202)(2)() 12(12, 1 , 0Nr为前一半输入与后一半输入之差再与为前一半输入与后一半输入之差再与WNn之积的之积的N/2点点DFT。nNWNnxnxnxNnxnxnx2)()(2)()(2112, 1 , 0Nr第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 46图图 4-14 按频率抽取蝶形

49、运算流图符号按频率抽取蝶形运算流图符号 1x(n)x(n N / 2)nNWx(n) x(n N / 2)x(n) x(n N / 2)nNWnNWNnxnxnxNnxnxnx2)()(2)()(2112, 1 , 0Nr第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 47 这样可把一个这样可把一个N点点DFT按按k的奇偶分解为两个的奇偶分解为两个N/2点的点的DFT。 N=8时，上述分解过程示于图时，上述分解过程示于图4-15。 图图 4-15 按频率抽取，将按频率抽取，将N点点DFT分解为两个分解为两个N/2点点DFT的组合的组合 X(0)X(2)110NWDFT2点NX(4)X(6)

50、X(1)X(3)DFT2点NX(5)X(7)1NW2NW3NW11x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 48由于由于N=2L，N/2仍是一个偶数，因而可以将每个仍是一个偶数，因而可以将每个N/2点点DFT的输出再分解为偶数组与奇数组，这就将的输出再分解为偶数组与奇数组，这就将N/2点点DFT进一步进一步分解为两个分解为两个N/4 点点DFT。 图图4-16示出了这一步分解的过程示出了这一步分解的过程。 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 49图图 4-16 按频率抽取的第二次分解按频率抽取的第二次分解 DFT4点N110NW2NWx(0)x(1)x(2)x(3)11x(4)x(5)x(6)x(7)0NW1NW2NW3NWDFT4点NDFT4点NDFT4点NX(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)0NW2NW1111第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 50 这样的分解可以一直进行到第这样的分解可以一直进行到第L次（次（N=2L），第），第L次实际上次实际上是做两点是做两点DFT，它只有加减运算。，它只有加减运算。