第4章快速傅里叶变换(FFT)课件.ppt

1、 第第4章章 快速傅里叶变换快速傅里叶变换(FFT)4.1 引引 言言DFT是数字信号分析与处理中的一种重要变换。但是数字信号分析与处理中的一种重要变换。但直接计算直接计算DFT，当，当N较大时，计算量太大，所以在快速较大时，计算量太大，所以在快速傅里叶变换傅里叶变换FFT(Fast Fourier Transform)出现以前，直出现以前，直接用接用DFT算法进行谱分析和信号的实时处理是不切实际算法进行谱分析和信号的实时处理是不切实际的。直到的。直到1965年提出年提出DFT的一种快速算法以后，情况才的一种快速算法以后，情况才发生了根本的变化。发生了根本的变化。自从自从1965年库利和图基在

2、年库利和图基在计算数学计算数学杂志上发杂志上发表了著名的表了著名的机器计算傅里叶级数的一种算法机器计算傅里叶级数的一种算法论文论文后，桑德后，桑德图基等快速算法相继出现，又经人们进行图基等快速算法相继出现，又经人们进行改进，很快形成一套高效计算方法，这就是现在的改进，很快形成一套高效计算方法，这就是现在的快快速傅里叶变换（速傅里叶变换（FFT）。）。这种算法使这种算法使DFT的运算效率提高了的运算效率提高了1 2个数量级，个数量级，为数字信号处理技术应用于各种信号的实时处理创造为数字信号处理技术应用于各种信号的实时处理创造了条件，大大推动了数字信号处理技术的发展。了条件，大大推动了数字信号处理

3、技术的发展。人类的求知欲和科学的发展是永无止境的。多年来，人类的求知欲和科学的发展是永无止境的。多年来，人们继续寻求更快、更灵活的好算法。人们继续寻求更快、更灵活的好算法。1984年，法国的年，法国的杜哈梅尔杜哈梅尔(P.Dohamel)和霍尔曼和霍尔曼(H.Hollmann)提出的提出的分分裂基快速算法裂基快速算法，使运算效率进一步提高。，使运算效率进一步提高。本章主要讨论本章主要讨论基基2FFT算法。算法。4.2 基基2FFT算法算法4.2.1 直接计算直接计算DFT的特点及减少运算量的基本的特点及减少运算量的基本 途径途径 有限长序列有限长序列x(n)的的N点点DFT为为考虑考虑x(n)

4、为复数序列的一般情况，对某一个为复数序列的一般情况，对某一个k值，直接按值，直接按(4.2.1)式计算式计算X(k)的的1个值需要个值需要N次复数乘法和次复数乘法和(N1)次复数加法。因此，次复数加法。因此，计算计算X(k)的所有的所有N个值，共需个值，共需N2次次复数乘法和复数乘法和N(N1)次复数加法运算。次复数加法运算。10110 )()(NnknNNkWnxkX，（4.2.1）当当时，时，N(N1)N2。由上述可见，。由上述可见，N点点DFT的乘法和加法运算次数均为的乘法和加法运算次数均为N2。当。当N较大时，运算较大时，运算量相当可观。例如量相当可观。例如N=1024时，时，N2=1

5、 048 576。这对于。这对于实时信号处理来说，必将对处理设备的计算速度提出实时信号处理来说，必将对处理设备的计算速度提出难以实现的要求。所以，必须减少其运算量，才能使难以实现的要求。所以，必须减少其运算量，才能使DFT在各种科学和工程计算中得到应用。在各种科学和工程计算中得到应用。如前所述，如前所述，N点点DFT的复乘法次数等于的复乘法次数等于N2。显然，。显然，把把N点点DFT分解为几个较短的分解为几个较短的DFT，可使乘法次数大大，可使乘法次数大大减少。减少。1N FFT算法就是不断地把长序列的算法就是不断地把长序列的DFT分解成几个短序分解成几个短序列的列的DFT，并利用，并利用 的

6、周期性和对称性来减少的周期性和对称性来减少DFT的运算次数。算法最简单最常用的是基的运算次数。算法最简单最常用的是基2FFT。其对称性表现为其对称性表现为(4.2.3a)mNNmNWW或者或者 mNmNNWW*(4.2.3b)mNNmNWW2knNW另外，旋转因子具有明显的周期性和对称性。其周期性表现为另外，旋转因子具有明显的周期性和对称性。其周期性表现为mNmNlNmNlNmNWW2j)(2jee 4.2.2 时域抽取法基时域抽取法基2FFT基本原理基本原理基基2FFT算法分为两类：算法分为两类：时域抽取法时域抽取法FFT(DecimationIn Time FFT，简称，简称DITFFT)

7、；频域抽取法频域抽取法FFT(Decimation In Frequency FFT，简称，简称DIFFFT)。本节。本节介绍介绍DITFFT算法。算法。设序列设序列x(n)的长度为的长度为N，且满足，且满足N=2M，M为自然数。为自然数。按按n的奇偶的奇偶把把x(n)分解为两个分解为两个N/2点的子序列点的子序列12()(2)0112()(21)0112Nx rxrrNx rxrr，则则x(n)的的DFT为为/2 1/2 12(21)00/2 1/2 1221200()()()(2)(21)()()knknNNnnNNkrkrNNrrNNkrkkrNNNrrX kx n Wx n Wxr W

8、xrWx r WWx r W偶数奇数因为因为22jj222/2eekrkrkrkrNNNNWW所以所以/2 1/2 11/22/20012()()()()()0,1,2,-1NNkrkkrNNNrrkNX kx r WWxr WXkW XkkN 其中其中1(k)和和X2(k)分别为分别为x1(r)和和x2(r)的的N/2点点DFT,即即由于由于X1(k)和和X2(k)均以均以N/2为周期，且为周期，且 ，因此，因此X(k)又可表示为又可表示为(4.2.5)/2 111/2120()()DFT()NkrNNrX kx r Wx r(4.2.6)/2 122/2220()()DFT()NkrNNr

9、Xkx r Wx rkNNkNWW212()()()0,1,2,-1kNX kX kW XkkN 这样，就将这样，就将N点点DFT分解为两个分解为两个N/2点点DFT和和(4.2.7)式以及式以及(4.2.8)式的运算。式的运算。(4.2.7)和和(4.2.8)式的运算可用图式的运算可用图4.2.1所示所示的流图符号表示，称为的流图符号表示，称为蝶形运算符号蝶形运算符号。采用这种图示法，。采用这种图示法，经过一次奇偶抽取分解后，经过一次奇偶抽取分解后，N点点DFT运算图可以用图运算图可以用图4.2.2表示。图中，表示。图中，N=23=8，X(0)X(3)由由(4.2.7)式给出，而式给出，而X

10、(4)X(7)则由则由(4.2.8)式给出。式给出。(4.2.7)1210)()()(21NkkXWkXkXkN，(4.2.8)1210)()()2(21NkkXWkXNkXkN，图图4.2.1 蝶形运算符号蝶形运算符号偶数点的偶数点的N/2 DFT奇数点的奇数点的N/2 DFTkNW序列序列DFT的的N/2个点个点序列序列DFT的后的后N/2个个点点 图图4.2.2 8点点DFT一次时域抽取分解运算流图一次时域抽取分解运算流图 由图由图4.2.1可见，要完成可见，要完成一个蝶形运算一个蝶形运算，需要，需要一次复一次复数乘法数乘法和和两次复数加法两次复数加法运算。由图运算。由图4.2.2容易看

11、出，经过容易看出，经过一次分解后，计算一次分解后，计算1个个N点点DFT共需要计算共需要计算两个两个N/2点点DFT和和N/2个蝶形运算个蝶形运算。而计算一个。而计算一个N/2点点DFT需要需要(N/2)2次复次复数乘法和数乘法和N/2(N/21)次复数加法。所以，按图次复数加法。所以，按图4.2.2计算计算N点点DFT时，总共需要的复数乘法次数为时，总共需要的复数乘法次数为 221(1)22222NNNN NN复数加法次数为复数加法次数为22122222NNNN 由此可见，仅仅经过一次分解，就使运算量减少近由此可见，仅仅经过一次分解，就使运算量减少近一半。既然这样分解对减少一半。既然这样分解

12、对减少DFT的运算量是有效的，且的运算量是有效的，且N=2M,N/2仍然是偶数，故可以对仍然是偶数，故可以对N/2点点DFT再作进一步再作进一步分解。分解。与第一次分解相同，将与第一次分解相同，将x1(r)按奇偶分解成两个按奇偶分解成两个N/4点的子序列点的子序列x3(l)和和x4(l)，即，即3141()(2)011()(21)4x lxlNlx lxl，X1(k)又可表示为又可表示为(4.2.9)/4 1/4 12(21)11/21/200/4 1/4 12(21)3/24/200/4 1/4 13/4/24/4003/24()(2)(21)()()()()()()0112NNklklNN

13、llNNklklNNllNNklkklNNNllkNX kxl WxlWx l Wx l Wx l WWx l WNXkWXkk，式中式中同理，由同理，由X3(k)和和X4(k)的周期性和的对称性的周期性和的对称性最后得到：最后得到：/4 133/4340()()DFT()NklNNlXkx l Wx l/4 144/4440()()DFT()NklNNlXkx l Wx lmNW2/kNNkNWW2/4/2/(4.2.10)14/10)()()4/()()()(42/3142/31NkkXWkXNkXkXWkXkXkNkN，用同样的方法可计算出用同样的方法可计算出/4 155/4540/4

14、166/46405262()()DFT()()()DFT()()(2)01/4 1()(21)NklNNlNklNNlXkx l Wx lXkx l Wx lx lxllNx lxl，1410 )()(4)()()(62/5262/52NkkXWkXNkXkXWkXkXkNkN，(4.2.11)其中：其中：这样，经过第二次分解，又将这样，经过第二次分解，又将N/2点点DFT分解为分解为2个个N/4点点DFT和和(4.2.10)式或式或(4.2.11)式所示的式所示的N/4个蝶形运算，个蝶形运算，如图如图4.2.3所示。所示。依次类推，依次类推，经过经过M次分解，最后将次分解，最后将N点点DFT

15、分解成分解成N个个1点点DFT和和M级蝶形运算，而级蝶形运算，而1点点DFT就是时域序列本就是时域序列本身。身。一个完整的一个完整的8点点DITFFT运算流图如图运算流图如图4.2.4所示。所示。图中用到关系式。图中图中用到关系式。图中输入序列不是顺序排输入序列不是顺序排列列，但后面会看到，但后面会看到，其排列是有规律的其排列是有规律的。图中的数组。图中的数组A用于存放输入序列和每级运算结果。用于存放输入序列和每级运算结果。mkNkmNWW/图图4.2.3 8点点DFT二次时域抽取分解运算流图二次时域抽取分解运算流图 图图4.2.4 8点点DIT-FFT运算流图运算流图 4.2.3 DIT-F

16、FT算法与直接计算算法与直接计算DFT运算量的比较运算量的比较由由DIT-FFT算法的分解过程及图算法的分解过程及图4.2.4可见，当可见，当N=2M 时，时，其运算流图应有其运算流图应有M级蝶形级蝶形，每一级都由，每一级都由N/2个蝶形运算个蝶形运算构成。构成。因此，每一级运算都需要因此，每一级运算都需要N/2次复数乘和次复数乘和N次复数加次复数加(每个每个蝶形需要两次复数加法蝶形需要两次复数加法)。所以，。所以，M级运算总共需要的复数级运算总共需要的复数乘次数为乘次数为复数加次数为复数加次数为2log22MNNCMN2logACN MNN 而直接计算而直接计算DFT的复数乘为的复数乘为N2

17、次，复数加为次，复数加为N(N1)次。次。当当N1时，时，N2(N/2)log2N，所以，所以，DIT-FFT算法比直算法比直接计算接计算DFT的运算次数大大减少。的运算次数大大减少。例如，例如，N=210=1024时，时，这样，就使运算效率提高这样，就使运算效率提高200多倍。图多倍。图4.2.5为为FFT算法算法和直接计算和直接计算DFT所需复数乘法次数所需复数乘法次数CM与变换点数与变换点数N的关的关系曲线。由此图更加直观地看出系曲线。由此图更加直观地看出FFT算法的优越性，显算法的优越性，显然，然，N越大时，优越性就越明显。越大时，优越性就越明显。221 048 576204.8512

18、0log2NNN 图图4.2.5 DIT-FFT算法与直接计算算法与直接计算DFT所需复数乘法次数的比较曲线所需复数乘法次数的比较曲线 4.2.4 DIT-FFT的运算规律及蝶形画法的运算规律及蝶形画法1 原位计算原位计算由图由图4.2.4可以看出，可以看出，DIT-FFT的运算过程很有规律。的运算过程很有规律。N=2M点的点的FFT共进行共进行M级运算，每级由级运算，每级由N/2个蝶形运算个蝶形运算 组成。组成。同一级中，每个蝶形的两个输入数据只对计算本蝶形有同一级中，每个蝶形的两个输入数据只对计算本蝶形有 用，而且每个蝶形的输入、输出数据结点又同在一条水用，而且每个蝶形的输入、输出数据结点

19、又同在一条水 平线上，这就意味着计算完一个蝶形后，所得输出数据平线上，这就意味着计算完一个蝶形后，所得输出数据 可立即存入原输入数据所占用的存储单元可立即存入原输入数据所占用的存储单元(数组元素数组元素)。这样，这样，经过经过M级运算后，原来存放输入序列数据的级运算后，原来存放输入序列数据的N个个 存储单元存储单元(数组数组A)中便依次存放中便依次存放X(k)的的N个值。个值。8点点DIT-FFT运算流图的画法运算流图的画法 2 旋转因子的变化规律旋转因子的变化规律如上所述，如上所述，N点点DIT-FFT运算流图中，每级都有运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以因子，称其为个蝶形。

20、每个蝶形都要乘以因子，称其为旋转因子旋转因子，p为旋转因子的指数。但各级的旋转因子都有所不同。为旋转因子的指数。但各级的旋转因子都有所不同。为了画出蝶形图，应先找出旋转因子为了画出蝶形图，应先找出旋转因子 与运算级数与运算级数的关系。用的关系。用L表示从左到右的运算级数表示从左到右的运算级数(L=1，2，M)。观察图观察图4.2.4不难发现，第不难发现，第L级共有级共有2L1个不同的旋转因个不同的旋转因子。子。N=23=8时的各级旋转因子表示如下：时的各级旋转因子表示如下：pNWpNW 对对N=2M的一般情况，第的一般情况，第L级的旋转因子为：级的旋转因子为：3,2,1,0 31,0 20 1

21、222/24/JWWWLJWWWLJWWWLJJNpNJJNpNJJNpNLLL时时时L-12,0,1,2,21LpJNWWJ 因为因为所以所以MLMLMLN222212,2,1,0122LJNJNpNJWWWLMML（4.2.12）LMJp2（4.2.13）这样，就可按这样，就可按(4.2.12)和和(4.2.13)式式确定第确定第L级运算的旋转级运算的旋转因子因子。3 序列的倒序序列的倒序DIT-FFT算法的输入序列的排序看起来似乎很乱，但仔算法的输入序列的排序看起来似乎很乱，但仔 细分析就会发现这种倒序是很有规律的。由于细分析就会发现这种倒序是很有规律的。由于N=2M，因此顺序数可用因此

22、顺序数可用M位二进制数位二进制数(nM1 nM2n1n0)表示。表示。表表4.2.1列出了列出了N=8时以二进制数表示的顺序数和倒序时以二进制数表示的顺序数和倒序 数，由表显而易见，数，由表显而易见，只要将顺序数只要将顺序数(n2n1n0)的二进制位的二进制位 倒置，则得对应的二进制倒序值倒置，则得对应的二进制倒序值(n0n1n2)4.2.5 频域抽取法频域抽取法FFT(DIF-FFT)在基在基2FFT算法中，频域抽取法算法中，频域抽取法FFT也是一种常用也是一种常用的快速算法，简称的快速算法，简称DTF-FFT。设序列设序列x(n)长度为长度为N=2M，首先将，首先将x(n)前后对半分前后对

23、半分开开，得到两个子序列，其，得到两个子序列，其DFT可表示为如下形式：可表示为如下形式：10/2 110/2/2 1/2 1(/2)00/2 1/20()DFT()()()()()2()2NknNnNNknknNNnn NNNknk n NNNnnNkNknNNnX kx nx n Wx n Wx n WNx n Wx nWNx nWx nW 式中式中将将X(k)分解成偶数组与奇数组，当分解成偶数组与奇数组，当k取取偶数偶数(k=2m,m=0,1,N/21)时时/21(1)1kNkNkWk 偶数奇数，/2 120/2 1/20(2)()2()2NmnNnNmnNnNXmx nx nWNx n

24、x nW（4.2.14）当当k取奇数取奇数(k=2m+1,m=0,1,N/21)时，时，令令122102)()(2)()(21NnWNnxnxnxNnxnxnxnN，/2 1(21)0/2 1/20(21)()2()2NnmNnNnnmNNnNXmx nx nWNx nx nWW(4.2.15)将将x1(n)和和x2(n)分别代入分别代入(4.2.14)和和(4.2.15)式，可得式，可得(4.2.16)式表明，式表明，X(k)按奇偶按奇偶k值分为两组，其偶数组是值分为两组，其偶数组是x1(n)的的N/2点点DFT，奇数组则是，奇数组则是x2(n)的的N/2点点DFT。x1(n)、x2(n)和

25、和x(n)之间的关系也可用图之间的关系也可用图4.2.10所示的蝶所示的蝶形运算流图符号表示。图形运算流图符号表示。图4.2.11表示表示N=8时第一次分解时第一次分解的运算流图。的运算流图。/2 11/20/2 12/20(2)()(21)()NmnNnNmnNnXmx n WXmx n W 图图4.2.10 DTFFFT蝶形运算流图符号蝶形运算流图符号序列的序列的前半部前半部分分序列的后序列的后半部分半部分 图图4.2.11 DIF-FFT第一次分解运算流图（第一次分解运算流图（N=8）由于由于N=2M，N/2仍然是偶数，继续将仍然是偶数，继续将N/2点点DFT分成分成 偶数组和奇数组，这

26、样每个偶数组和奇数组，这样每个N/2点点DFT又可由两个又可由两个N/4 点点DFT形成，其输入序列分别是形成，其输入序列分别是x1(n)和和x2(n)按上下对按上下对 半分开形成的四个子序列。半分开形成的四个子序列。图图4.2.12示出了示出了N=8时第二次分解运算流图。以这种方时第二次分解运算流图。以这种方 式分解下去，经过式分解下去，经过M1次分解，最后分解为次分解，最后分解为2M1个个 两点两点DFT，两点两点DFT就是一个基本蝶形运算流图就是一个基本蝶形运算流图。当当N=8，经两次分解，便分解为四个两点，经两次分解，便分解为四个两点DFT。N=8 的完整的完整DIF-FFT运算流图如

27、图运算流图如图4.2.13所示。所示。图图4.2.12 DIF-FFT第二次分解运算流图（第二次分解运算流图（N=8）图图4.2.13 DIF-FFT运算流图（运算流图（N=8）这种算法是对这种算法是对X(k)进行奇偶抽取分解的结果，所以称之为进行奇偶抽取分解的结果，所以称之为 频域抽取法频域抽取法FFT。观察图观察图4.2.13可知，可知，DIF-FFT算法与算法与DIT-TTF算法类似，算法类似，共有共有M级运算，每级共有级运算，每级共有N/2个蝶形运算，所以两种算法个蝶形运算，所以两种算法 的运算次数亦相同。的运算次数亦相同。不同的是不同的是DIF-FFT算法输入序列为自然顺序，而输出为

28、倒算法输入序列为自然顺序，而输出为倒 序排列。因此，序排列。因此，M级运算完后，要对输出数据进行排序才级运算完后，要对输出数据进行排序才 能得到自然顺序的能得到自然顺序的X(k)。另外，蝶形运算略有不同，另外，蝶形运算略有不同，DIT-FFT蝶形先乘后加蝶形先乘后加(减减)，而而DIF-FFT蝶形先加蝶形先加(减减)后相乘。后相乘。4.2.6 IDFT的高效算法的高效算法上述上述FFT算法流图也可以用于计算算法流图也可以用于计算IDFT。比较。比较DFT和和IDFT的运算公式：的运算公式：1010()DFT()()1()IDFT()()NknNnNknNkX kx nx n Wx nX kX

29、k WN 只要将只要将DFT运算式中的系数运算式中的系数改为，最后乘以改为，最后乘以 1/N，就是，就是IDFT运算公式。运算公式。所以，只要将上述的所以，只要将上述的DIT-FFT与与DIF-FFT算法中的旋算法中的旋 转因子转因子 改为，最后的输出再乘以改为，最后的输出再乘以1/N就可以用就可以用 来计算来计算IDFT。只是现在流图的输入是。只是现在流图的输入是X(k)，输出就，输出就 是是x(n)。因此，原来的因此，原来的DIT-FFT改为改为IFFT后，称为后，称为DIF-IFFT 更合适；更合适；DIF-FFT改为改为IFFT后后,应称为应称为DIT-IFFT。knNWpNWpNWk

30、nNW 如果希望直接调用如果希望直接调用FFT子程序计算子程序计算IFFT，则可用，则可用下面的方法：下面的方法：由于由于所以，可以先将所以，可以先将X(k)取复共轭，然后直接调用取复共轭，然后直接调用FFT子子程序，最后取复共轭并乘以程序，最后取复共轭并乘以1/N得到序列得到序列x(n)。这种方。这种方法虽然用了两次取共轭运算，但可以与法虽然用了两次取共轭运算，但可以与FFT共用同一共用同一子程序，因而用起来很方便。子程序，因而用起来很方便。*10*)(1)(1)(kXDFTNWkXNnxNkknN 图图4.2.4 8点点DIT-FFT运算流图运算流图 L=1 L=2 L=3 4.3 进一步

31、减少运算量的措施进一步减少运算量的措施4.3.1 多类蝶形单元运算多类蝶形单元运算由由DIT-FFT运算流图已得出结论，运算流图已得出结论，N=2M点点FFT共需要共需要MN/2次复数乘法。次复数乘法。由由(4.2.12)式，当式，当L=1时，只有一种旋转因子时，只有一种旋转因子所以，第一级不需要乘法运算。当所以，第一级不需要乘法运算。当L=2 时，共有两个时，共有两个旋转因子：旋转因子：和和 ，因此，第二级也不，因此，第二级也不需要乘法运算。在需要乘法运算。在DFT中，又称其值为中，又称其值为1和和j的旋的旋转因子为无关紧要的旋转因子如转因子为无关紧要的旋转因子如 ，等。等。10NW10NW

32、jWNN4/0NW2/NNW4/NNW 综上所述，先除去第一、二两级后，所需复数乘综上所述，先除去第一、二两级后，所需复数乘法次数应是法次数应是进一步考虑各级中的无关紧要旋转因子。当进一步考虑各级中的无关紧要旋转因子。当L=3时，时，有两个无关紧要的旋转因子和，因为同一有两个无关紧要的旋转因子和，因为同一旋转因子对应着旋转因子对应着2ML=N/2L个碟形运算，所以第三级共个碟形运算，所以第三级共有有2N/23=N/4 个碟形不需要复数乘法运算。依此类推，个碟形不需要复数乘法运算。依此类推，当当L3时，第时，第L级的级的2个无关紧要的旋转因子减少复数乘个无关紧要的旋转因子减少复数乘法的次数为法的

33、次数为2N/2L=N/2L1。这样，从。这样，从L=3至至L=M共减共减少复数乘法次数为少复数乘法次数为 0NW4/NNW(2)2MNCM(4.3.1)因此，因此，DIT-FFT的的复乘次数降至复乘次数降至 下面再讨论下面再讨论FFT中特殊的复数运算，以便进一步减少中特殊的复数运算，以便进一步减少 复数乘法次数。复数乘法次数。一般实现一次复数乘法运算需要四次一般实现一次复数乘法运算需要四次 实数乘，两次实数加实数乘，两次实数加。但对这一特。但对这一特 殊复数，任一复数殊复数，任一复数(x+jy)与其相乘时，与其相乘时，(4.3.2)222122331NNNMLLMLL2/2)1(8/jWNN(

34、2)2(3)2222MNNNCMM（4.3.3）22(1j)(j)(jj)222()j()2xyxyxyxyxyRjI2()222()()22RxyIxyyx 只需要两次实数加和两次实数乘就可实现。这样，只需要两次实数加和两次实数乘就可实现。这样，对应的每个蝶形节省对应的每个蝶形节省两次实数乘两次实数乘。8/NNW 在在DIT-FFT运算流图中，从运算流图中，从L=3至至L=M级，每级级，每级都包含旋转因子都包含旋转因子 ，第，第L级中，级中，对应对应N/2L个蝶个蝶形运算。因此从第三级至最后一级，旋转因子形运算。因此从第三级至最后一级，旋转因子 节省的实数乘次数与节省的实数乘次数与(4.3.

35、2)式相同。式相同。所以从实数乘运算考虑，计算所以从实数乘运算考虑，计算N=2M点点DIT-FFT所所需需实数乘法实数乘法次数为次数为 8/NNW8/NNW8/NNW(4.3.4)134(3)22210222MNNRMNM 在基在基2FFT程序中，若包含了所有旋转因子，则称程序中，若包含了所有旋转因子，则称该算法为一类碟形单元运算；若去掉该算法为一类碟形单元运算；若去掉 的旋转因的旋转因子，则称之为二类碟形单元运算；若再去掉子，则称之为二类碟形单元运算；若再去掉 的旋的旋转因子，则称为三类碟形单元运算；若再判断处理转因子，则称为三类碟形单元运算；若再判断处理，则称之为四类碟形运算。我们将后三种

36、运算称为多，则称之为四类碟形运算。我们将后三种运算称为多类碟形单元运算。显然，类碟形单元运算。显然，碟形单元类型越多，编程就越碟形单元类型越多，编程就越复杂，但当复杂，但当N较大时，乘法运算的减少量是相当可观的。较大时，乘法运算的减少量是相当可观的。例如，例如，N=4096时，三类碟形单元运算的乘法次数为一类时，三类碟形单元运算的乘法次数为一类碟形单元运算的碟形单元运算的75%。1mNW(1j)2/2mNWmNWj 4.3.2 旋转因子的生成旋转因子的生成在在FFT运算中，旋转因子运算中，旋转因子，求正弦和余弦函数值的计算量是很，求正弦和余弦函数值的计算量是很大的。所以编程时，产生旋转因子的方

37、法直接影响运大的。所以编程时，产生旋转因子的方法直接影响运算速度。算速度。一种方法是在每级运算中直接产生；另一种一种方法是在每级运算中直接产生；另一种方法是在方法是在FFT程序开始前预先计算出程序开始前预先计算出，m=0，1，N/21，存放在数组存放在数组中，作为旋转因子表，中，作为旋转因子表，在程序执行过程中直接查表得到所需旋转因子值，不在程序执行过程中直接查表得到所需旋转因子值，不再计算。再计算。这样使运算速度大大提高，其不足之处是占这样使运算速度大大提高，其不足之处是占用内存较多。用内存较多。)/2cos(NmWmN)/2sin(jNmmNW 4.3.3 在实际工作中，数据在实际工作中，

38、数据x(n)常常是实数序列。如果直常常是实数序列。如果直接按接按FFT运算流图计算，就是把运算流图计算，就是把x(n)看成一个虚部为零看成一个虚部为零的复序列进行计算，这就增加了存储量和运算时间。的复序列进行计算，这就增加了存储量和运算时间。处处理该问题的方法有两种。理该问题的方法有两种。早期提出的早期提出的方法是用一个方法是用一个N点点FFT计算两个计算两个N点实序列的点实序列的FFT，一个实序列作为，一个实序列作为x(n)的的实部，另一个作为虚部，计算完实部，另一个作为虚部，计算完FFT后，根据后，根据DFT的共的共轭对称性，由输出轭对称性，由输出X(k)分别得到两个实序列的分别得到两个实

39、序列的N点点DFT（例题（例题3.2.2）。）。第二种方法是用第二种方法是用N/2点点FFT计算一个计算一个N点点实序列的实序列的DFT。下面简要介绍第二种方法。下面简要介绍第二种方法。设设x(n)为为N点实序列，取点实序列，取x(n)的偶数点和奇数点分的偶数点和奇数点分别作为新构造序列别作为新构造序列y(n)的实部和虚部，即的实部和虚部，即对对y(n)进行进行N/2点点FFT，输出，输出Y(k)，则，则1210)(j)()(1210)12()()2()(2121NnnxnxnyNnnxnxnxnx，1122()DFT()()0112()DFT()()epopX kx nYkNkXkx njY

40、k，根据根据DIT-FFT的思想及式的思想及式(4.2.7)和和(4.2.8)，可得到，可得到X(k)的前的前 个值：个值：式中，式中，。由于。由于x(n)为实序列，为实序列，因此因此X(k)具有共轭对称性，具有共轭对称性，X(k)的后的后N/2点的值为点的值为12N)0(2),0(22211XNXXNX1210)()(*NkkXkNX，210)()()(21NkkXWkXkXkN，（4.3.5）计算计算 N/2点点FFT的复乘次数为的复乘次数为N(M-1)/4，计算式，计算式(4.3.5)的复乘次数为的复乘次数为N/2，所以用这种算法，所以用这种算法,计算计算X(k)所需所需复数乘法次数为复

41、数乘法次数为 。相对一般的。相对一般的N点点FFT算法，上述算法的运算效率为算法，上述算法的运算效率为当当N=2M=210时，时，=20/11，运算速度提高近，运算速度提高近1倍。倍。)1(42)1(4MNNMN)1/(2)1(4/2MMMNMN 4.4 其他快速算法简介其他快速算法简介快速傅里叶变换算法是信号处理领域重要的研究课快速傅里叶变换算法是信号处理领域重要的研究课题。题。本章仅介绍算法最简单、编程最容易的基本章仅介绍算法最简单、编程最容易的基2FFT算法算法原理及其编程思想，使读者建立快速傅里叶变换的基本原理及其编程思想，使读者建立快速傅里叶变换的基本概念，了解研究概念，了解研究FF

42、T算法的主要途径和编程思路。例如，算法的主要途径和编程思路。例如，分裂基分裂基FFT算法、离散哈特莱变换算法、离散哈特莱变换(DHT)、基、基4FFT、基、基8FFT、基、基rFFT、混合基、混合基FFT，以及进一步减少运算量的，以及进一步减少运算量的途径等内容，对研究新的快速算法都是很有用的。本节途径等内容，对研究新的快速算法都是很有用的。本节简要介绍其他几种快速算法的运算量及其主要特点，以简要介绍其他几种快速算法的运算量及其主要特点，以便读者选择快速算法时参考。便读者选择快速算法时参考。从理论上讲，不同基数的从理论上讲，不同基数的FFT算法的运算效率不同，算法的运算效率不同，实际中最常用的

43、是基实际中最常用的是基2FFT、基基4 FFT、分裂基、分裂基FFT和和DHT。为此，下面简要。为此，下面简要介绍后三种介绍后三种FFT算法的特点算法的特点,以扩以扩展读者的视野。展读者的视野。在基在基rFFT算法中，基算法中，基4FFT算法运算效率与基算法运算效率与基8FFT很很 接近，但基接近，但基4FFT算法实现程序简单，且判断开销少。算法实现程序简单，且判断开销少。可以证明，可以证明，当当FFT的基大于的基大于4时，不会明显降低计算量。时，不会明显降低计算量。分裂基分裂基FFT算法算法是将基是将基2分解和基分解和基4分解糅合提出的，分解糅合提出的，其其复数乘法次数接近复数乘法次数接近F

44、FT理论最小值理论最小值，但其运算流图，但其运算流图 却与基却与基2FFT很相似，编程简单，运算程序也很短，是很相似，编程简单，运算程序也很短，是 一种很实用的高效算法一种很实用的高效算法。但是，对实序列但是，对实序列x(n)，上述各种，上述各种FFT算法仍将其看成虚算法仍将其看成虚 部为零的复序列存储和计算。而一次复数乘法需要四部为零的复序列存储和计算。而一次复数乘法需要四 次实数乘法和二次实数加法。所以，次实数乘法和二次实数加法。所以，必然浪费存储资必然浪费存储资 源和增加多余的运算量源和增加多余的运算量。我们知道，实序列的我们知道，实序列的N点点DFT具有共轭对称性，即具有共轭对称性，即

45、*()(),0,1,2,1X NkXkkN所以，所以，只要计算出只要计算出X（k）的前面）的前面N/2个值，则其后面个值，则其后面的的N/2个值可以由对称性求得个值可以由对称性求得。因此，。因此，FFT算法得到算法得到的的N个个X（k）值有一半是多余的。）值有一半是多余的。所以，对实序列一定存在更高效的快速算法。所以，对实序列一定存在更高效的快速算法。离散哈特离散哈特 莱变换（莱变换（DHT）就是针对实序列的一种高效变换算法）就是针对实序列的一种高效变换算法，相，相 对一般的对一般的FFT算法，算法，DHT的快速算法的快速算法FHT可以减少近一半可以减少近一半 的计算量。的计算量。应当说明，应

46、当说明，DHT是与是与DFT不同的变换，所以要想得到不同的变换，所以要想得到 实序列实序列DFT，还要根据二者的关系式进行转换。下面，还要根据二者的关系式进行转换。下面 会看到该关系非常简单。会看到该关系非常简单。DHT具有以下具有以下主要特点主要特点：(1)DHT是实数变换，在对实信号进行处理时避免了是实数变换，在对实信号进行处理时避免了复数运算，运算效率高。复数运算，运算效率高。(2)DHT的正、逆变换（除了因子的正、逆变换（除了因子1/N外）具有相同的外）具有相同的形式。形式。N点点DHT定义如下：定义如下：N点逆点逆DHT变换定义为变换定义为(3)DHT满足循环卷积定理，所以，可以直接用满足循环卷积定理，所以，可以直接用FHT实实现实序列的快速卷积，大大提高处理速度。现实序列的快速卷积，大大提高处理速度。（4.4.6）(4)DHT与与DFT之间的关系非常简单，容易实现二者之间之间的关系非常简单，容易实现二者之间的转换，关系式如下：的转换，关系式如下：HHHH11()()()j()()22X kXkXNkXkXNk（4.4.7）