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

第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多第第4章章 快速傅里叶变换快速傅里叶变换(FFT)4.1 4.1 引言引言引言引言 4.2 4.2 基基基基2FFT2FFT算法算法算法算法 4.3 4.3 进一步减少运算量的措施进一步减少运算量的措施进一步减少运算量的措施进一步减少运算量的措施 4.4 4.4 其他快速算法简介其他快速算法简介其他快速算法简介其他快速算法简介第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多4.1 引引 言言DFT是数字信号分析与处理中的一种重要变换。但是数字信号分析与处理中的一种重要变换。但直接计算直接计算DFT，当，当N较大时，计算量太大，所以在快速较大时，计算量太大，所以在快速傅里叶变换傅里叶变换FFT(Fast Fourier Transform)出现以前，直出现以前，直接用接用DFT算法进行谱分析和信号的实时处理是不切实际算法进行谱分析和信号的实时处理是不切实际的。直到的。直到1965年提出年提出DFT的一种快速算法以后，情况才的一种快速算法以后，情况才发生了根本的变化。发生了根本的变化。第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多自从自从1965年库利和图基在年库利和图基在计算数学计算数学杂志上发杂志上发表了著名的表了著名的机器计算傅里叶级数的一种算法机器计算傅里叶级数的一种算法论文论文后，桑德后，桑德图基等快速算法相继出现，又经人们进行图基等快速算法相继出现，又经人们进行改进，很快形成一套高效计算方法，这就是现在的改进，很快形成一套高效计算方法，这就是现在的快快速傅里叶变换（速傅里叶变换（FFT）。）。这种算法使这种算法使DFT的运算效率提高了的运算效率提高了1 2个数量级，个数量级，为数字信号处理技术应用于各种信号的实时处理创造为数字信号处理技术应用于各种信号的实时处理创造了条件，大大推动了数字信号处理技术的发展。了条件，大大推动了数字信号处理技术的发展。第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多人类的求知欲和科学的发展是永无止境的。多年来，人类的求知欲和科学的发展是永无止境的。多年来，人们继续寻求更快、更灵活的好算法。人们继续寻求更快、更灵活的好算法。1984年，法国的年，法国的杜哈梅尔杜哈梅尔(P.Dohamel)和霍尔曼和霍尔曼(H.Hollmann)提出的提出的分分裂基快速算法裂基快速算法，使运算效率进一步提高。，使运算效率进一步提高。本章主要讨论本章主要讨论基基2FFT算法。算法。第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多4.2 基基2FFT算法算法4.2.1 直接计算直接计算DFT的特点及减少运算量的基本的特点及减少运算量的基本 途径途径 有限长序列有限长序列x(n)的的N点点DFT为为考虑考虑x(n)为复数序列的一般情况，对某一个为复数序列的一般情况，对某一个k值，直接按值，直接按(4.2.1)式计算式计算X(k)的的1个值需要个值需要N次复数乘法和次复数乘法和(N1)次复数加法。因此，次复数加法。因此，计算计算X(k)的所有的所有N个值，共需个值，共需N2次次复数乘法和复数乘法和N(N1)次复数加法运算。次复数加法运算。（4.2.1）第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多当当时，时，N(N1)N2。由上述可见，。由上述可见，N点点DFT的乘法和加法运算次数均为的乘法和加法运算次数均为N2。当。当N较大时，运算量相较大时，运算量相当可观。例如当可观。例如N=1024时，时，N2=1 048 576。这对于实时信。这对于实时信号处理来说，必将对处理设备的计算速度提出难以实号处理来说，必将对处理设备的计算速度提出难以实现的要求。所以，必须减少其运算量，才能使现的要求。所以，必须减少其运算量，才能使DFT在在各种科学和工程计算中得到应用。各种科学和工程计算中得到应用。如前所述，如前所述，N点点DFT的复乘法次数等于的复乘法次数等于N2。显然，。显然，把把N点点DFT分解为几个较短的分解为几个较短的DFT，可使乘法次数大大，可使乘法次数大大减少。减少。第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多FFT算法就是不断地把长序列的算法就是不断地把长序列的DFT分解成几个短序分解成几个短序列的列的DFT，并利用，并利用 的周期性和对称性来减少的周期性和对称性来减少DFT的的运算次数。算法最简单最常用的是基运算次数。算法最简单最常用的是基2FFT。其对称性表现为其对称性表现为(4.2.3a)或者或者(4.2.3b)另外，旋转因子具有明显的周期性和对称性。其周期性表现为另外，旋转因子具有明显的周期性和对称性。其周期性表现为第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多4.2.2 时域抽取法基时域抽取法基2FFT基本原理基本原理基基2FFT算法分为两类：算法分为两类：时域抽取法时域抽取法FFT(DecimationIn Time FFT，简称，简称DITFFT)；频域抽取法频域抽取法FFT(Decimation In Frequency FFT，简称，简称DIFFFT)。本节。本节介绍介绍DITFFT算法。算法。设序列设序列x(n)的长度为的长度为N，且满足，且满足N=2M，M为自然数。为自然数。按按n的奇偶的奇偶把把x(n)分解为两个分解为两个N/2点的子序列点的子序列第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多则则x(n)的的DFT为为因为因为所以所以第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多其中其中1(k)和和X2(k)分别为分别为x1(r)和和x2(r)的的N/2点点DFT,即即由于由于X1(k)和和X2(k)均以均以N/2为周期，且为周期，且 ，因此，因此X(k)又可表示为又可表示为(4.2.5)(4.2.6)第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多这样，就将这样，就将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(4)X(7)则由则由(4.2.8)式给出。式给出。(4.2.7)(4.2.8)第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多图图4.2.1 蝶形运算符号蝶形运算符号偶数点的偶数点的N/2 DFT奇数点的奇数点的N/2 DFT序列序列DFT的的N/2个点个点序列序列DFT的后的后N/2个个点点第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多图图4.2.2 8点点DFT一次时域抽取分解运算流图一次时域抽取分解运算流图第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多由图由图4.2.1可见，要完成可见，要完成一个蝶形运算一个蝶形运算，需要，需要一次复一次复数乘法数乘法和和两次复数加法两次复数加法运算。由图运算。由图4.2.2容易看出，经过容易看出，经过一次分解后，计算一次分解后，计算1个个N点点DFT共需要计算共需要计算两个两个N/2点点DFT和和N/2个蝶形运算个蝶形运算。而计算一个。而计算一个N/2点点DFT需要需要(N/2)2次复次复数乘法和数乘法和N/2(N/21)次复数加法。所以，按图次复数加法。所以，按图4.2.2计算计算N点点DFT时，总共需要的复数乘法次数为时，总共需要的复数乘法次数为 复数加法次数为复数加法次数为第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多 由此可见，仅仅经过一次分解，就使运算量减少近由此可见，仅仅经过一次分解，就使运算量减少近一半。既然这样分解对减少一半。既然这样分解对减少DFT的运算量是有效的，且的运算量是有效的，且N=2M,N/2仍然是偶数，故可以对仍然是偶数，故可以对N/2点点DFT再作进一步再作进一步分解。分解。与第一次分解相同，将与第一次分解相同，将x1(r)按奇偶分解成两个按奇偶分解成两个N/4点点的子序列的子序列x3(l)和和x4(l)，即，即第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多X1(k)又可表示为又可表示为(4.2.9)第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多式中式中同理，由同理，由X3(k)和和X4(k)的周期性和的对称性的周期性和的对称性最后得到：最后得到：(4.2.10)第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多用同样的方法可计算出用同样的方法可计算出(4.2.11)其中：其中：第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多 这样，经过第二次分解，又将这样，经过第二次分解，又将N/2点点DFT分解为分解为2个个N/4点点DFT和和(4.2.10)式或式或(4.2.11)式所示的式所示的N/4个蝶形运算，个蝶形运算，如图如图4.2.3所示。所示。依次类推，依次类推，经过经过M次分解，最后将次分解，最后将N点点DFT分解成分解成N个个1点点DFT和和M级蝶形运算，而级蝶形运算，而1点点DFT就是时域序列本就是时域序列本身。身。一个完整的一个完整的8点点DITFFT运算流图如图运算流图如图4.2.4所示。所示。图中用到关系式。图中图中用到关系式。图中输入序列不是顺序排输入序列不是顺序排列列，但后面会看到，但后面会看到，其排列是有规律的其排列是有规律的。图中的数组。图中的数组A用于存放输入序列和每级运算结果。用于存放输入序列和每级运算结果。第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多图图4.2.3 8点点DFT二次时域抽取分解运算流图二次时域抽取分解运算流图第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多图图4.2.4 8点点DIT-FFT运算流图运算流图第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多4.2.3 DIT-FFT算法与直接计算算法与直接计算DFT运算量的比较运算量的比较由由DIT-FFT算法的分解过程及图算法的分解过程及图4.2.4可见，当可见，当N=2M 时，时，其运算流图应有其运算流图应有M级蝶形级蝶形，每一级都由，每一级都由N/2个蝶形运算个蝶形运算构成。构成。因此，每一级运算都需要因此，每一级运算都需要N/2次复数乘和次复数乘和N次复数加次复数加(每个蝶每个蝶形需要两次复数加法形需要两次复数加法)。所以，。所以，M级运算总共需要的复数乘级运算总共需要的复数乘次数为次数为复数加次数为复数加次数为第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多而直接计算而直接计算DFT的复数乘为的复数乘为N2次，复数加为次，复数加为N(N1)次。次。当当N1时，时，N2(N/2)log2N，所以，所以，DIT-FFT算法比直算法比直接计算接计算DFT的运算次数大大减少。的运算次数大大减少。例如，例如，N=210=1024时，时，这样，就使运算效率提高这样，就使运算效率提高200多倍。图多倍。图4.2.5为为FFT算法算法和直接计算和直接计算DFT所需复数乘法次数所需复数乘法次数CM与变换点数与变换点数N的关的关系曲线。由此图更加直观地看出系曲线。由此图更加直观地看出FFT算法的优越性，显算法的优越性，显然，然，N越大时，优越性就越明显。越大时，优越性就越明显。第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多图图4.2.5 DIT-FFT算法与直接计算算法与直接计算DFT所需复数乘法次数的比较曲线所需复数乘法次数的比较曲线第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多4.2.4 DIT-FFT的运算规律及蝶形画法的运算规律及蝶形画法1 原位计算原位计算由图由图4.2.4可以看出，可以看出，DIT-FFT的运算过程很有规律。的运算过程很有规律。N=2M点的点的FFT共进行共进行M级运算，每级由级运算，每级由N/2个蝶形运算个蝶形运算 组成。组成。同一级中，每个蝶形的两个输入数据只对计算本蝶形有同一级中，每个蝶形的两个输入数据只对计算本蝶形有 用，而且每个蝶形的输入、输出数据结点又同在一条水用，而且每个蝶形的输入、输出数据结点又同在一条水 平线上，这就意味着计算完一个蝶形后，所得输出数据平线上，这就意味着计算完一个蝶形后，所得输出数据 可立即存入原输入数据所占用的存储单元可立即存入原输入数据所占用的存储单元(数组元素数组元素)。这样，这样，经过经过M级运算后，原来存放输入序列数据的级运算后，原来存放输入序列数据的N个个 存储单元存储单元(数组数组A)中便依次存放中便依次存放X(k)的的N个值。个值。第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多8点点DIT-FFT运算流图的画法运算流图的画法第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2 旋转因子的变化规律旋转因子的变化规律如上所述，如上所述，N点点DIT-FFT运算流图中，每级都有运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以因子，称其为个蝶形。每个蝶形都要乘以因子，称其为旋转因子旋转因子，p为旋转因子的指数。但各级的旋转因子都有所不同。为旋转因子的指数。但各级的旋转因子都有所不同。为了画出蝶形图，应先找出旋转因子为了画出蝶形图，应先找出旋转因子 与运算级数与运算级数的关系。用的关系。用L表示从左到右的运算级数表示从左到右的运算级数(L=1，2，M)。观察图观察图4.2.4不难发现，第不难发现，第L级共有级共有2L1个不同的旋转因个不同的旋转因子。子。N=23=8时的各级旋转因子表示如下：时的各级旋转因子表示如下：第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多对对N=2M的一般情况，第的一般情况，第L级的旋转因子为：级的旋转因子为：第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多因为因为所以所以（4.2.12）（4.2.13）这样，就可按这样，就可按(4.2.12)和和(4.2.13)式式确定第确定第L级运算的旋转级运算的旋转因子因子。第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多3 序列的倒序序列的倒序DIT-FFT算法的输入序列的排序看起来似乎很乱，但仔算法的输入序列的排序看起来似乎很乱，但仔 细分析就会发现这种倒序是很有规律的。由于细分析就会发现这种倒序是很有规律的。由于N=2M，因此顺序数可用因此顺序数可用M位二进制数位二进制数(nM1 nM2n1n0)表示。表示。表表4.2.1列出了列出了N=8时以二进制数表示的顺序数和倒序时以二进制数表示的顺序数和倒序 数，由表显而易见，数，由表显而易见，只要将顺序数只要将顺序数(n2n1n0)的二进制位的二进制位 倒置，则得对应的二进制倒序值倒置，则得对应的二进制倒序值(n0n1n2)第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多表表表表4.2.1 4.2.1 顺序和倒序二进制数对照表顺序和倒序二进制数对照表顺序和倒序二进制数对照表顺序和倒序二进制数对照表第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多4.2.5 频域抽取法频域抽取法FFT(DIF-FFT)在基在基2FFT算法中，频域抽取法算法中，频域抽取法FFT也是一种常用也是一种常用的快速算法，简称的快速算法，简称DTF-FFT。设序列设序列x(n)长度为长度为N=2M，首先将，首先将x(n)前后对半分前后对半分开开，得到两个子序列，其，得到两个子序列，其DFT可表示为如下形式：可表示为如下形式：第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多式中式中将将X(k)分解成偶数组与奇数组，当分解成偶数组与奇数组，当k取取偶数偶数(k=2m,m=0,1,N/21)时时（4.2.14）第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多当当k取奇数取奇数(k=2m+1,m=0,1,N/21)时，时，令令(4.2.15)第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多将将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)和和x(n)之间的关系也可用图之间的关系也可用图4.2.10所示的蝶所示的蝶形运算流图符号表示。图形运算流图符号表示。图4.2.11表示表示N=8时第一次分解时第一次分解的运算流图。的运算流图。（4.2.164.2.16）第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多图图4.2.10 DTFFFT蝶形运算流图符号蝶形运算流图符号序列的序列的前半部前半部分分序列的后序列的后半部分半部分第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多图图4.2.11 DIF-FFT第一次分解运算流图（第一次分解运算流图（N=8）第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多由于由于N=2M，N/2仍然是偶数，继续将仍然是偶数，继续将N/2点点DFT分成分成 偶数组和奇数组，这样每个偶数组和奇数组，这样每个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运算流图如图运算流图如图4.2.13所示。所示。第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多图图4.2.12 DIF-FFT第二次分解运算流图（第二次分解运算流图（N=8）第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多图图4.2.13 DIF-FFT运算流图（运算流图（N=8）第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多这种算法是对这种算法是对X(k)进行奇偶抽取分解的结果，所以称之为进行奇偶抽取分解的结果，所以称之为 频域抽取法频域抽取法FFT。观察图观察图4.2.13可知，可知，DIF-FFT算法与算法与DIT-TTF算法类似，算法类似，共有共有M级运算，每级共有级运算，每级共有N/2个蝶形运算，所以两种算法个蝶形运算，所以两种算法 的运算次数亦相同。的运算次数亦相同。不同的是不同的是DIF-FFT算法输入序列为自然顺序，而输出为倒算法输入序列为自然顺序，而输出为倒 序排列。因此，序排列。因此，M级运算完后，要对输出数据进行排序才级运算完后，要对输出数据进行排序才 能得到自然顺序的能得到自然顺序的X(k)。另外，蝶形运算略有不同，另外，蝶形运算略有不同，DIT-FFT蝶形先乘后加蝶形先乘后加(减减)，而而DIF-FFT蝶形先加蝶形先加(减减)后相乘。后相乘。第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多4.2.6 IDFT的高效算法的高效算法上述上述FFT算法流图也可以用于计算算法流图也可以用于计算IDFT。比较。比较DFT和和IDFT的运算公式：的运算公式：第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多只要将只要将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。第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多如果希望直接调用如果希望直接调用FFT子程序计算子程序计算IFFT，则可用，则可用下面的方法：下面的方法：由于由于所以，可以先将所以，可以先将X(k)取复共轭，然后直接调用取复共轭，然后直接调用FFT子程子程序，最后取复共轭并乘以序，最后取复共轭并乘以1/N得到序列得到序列x(n)。这种方法。这种方法虽然用了两次取共轭运算，但可以与虽然用了两次取共轭运算，但可以与FFT共用同一子共用同一子程序，因而用起来很方便。程序，因而用起来很方便。第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多图图4.2.4 8点点DIT-FFT运算流图运算流图 L=1 L=2 L=3第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多4.3 进一步减少运算量的措施进一步减少运算量的措施4.3.1 多类蝶形单元运算多类蝶形单元运算由由DIT-FFT运算流图已得出结论，运算流图已得出结论，N=2M点点FFT共需要共需要MN/2次复数乘法。次复数乘法。由由(4.2.12)式，当式，当L=1时，只有一种旋转因子时，只有一种旋转因子所以，第一级不需要乘法运算。当所以，第一级不需要乘法运算。当L=2 时，共有两个时，共有两个旋转因子：旋转因子：和和 ，因此，第二级也不，因此，第二级也不需要乘法运算。在需要乘法运算。在DFT中，又称其值为中，又称其值为1和和j的旋转的旋转因子为无关紧要的旋转因子如因子为无关紧要的旋转因子如 ，等。等。第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多综上所述，先除去第一、二两级后，所需复数乘综上所述，先除去第一、二两级后，所需复数乘法次数应是法次数应是进一步考虑各级中的无关紧要旋转因子。当进一步考虑各级中的无关紧要旋转因子。当L=3时，时，有两个无关紧要的旋转因子和，因为同一有两个无关紧要的旋转因子和，因为同一旋转因子对应着旋转因子对应着2ML=N/2L个碟形运算，所以第三级共个碟形运算，所以第三级共有有2N/23=N/4 个碟形不需要复数乘法运算。依此类推，个碟形不需要复数乘法运算。依此类推，当当L3时，第时，第L级的级的2个无关紧要的旋转因子减少复数乘个无关紧要的旋转因子减少复数乘法的次数为法的次数为2N/2L=N/2L1。这样，从。这样，从L=3至至L=M共减少共减少复数乘法次数为复数乘法次数为(4.3.1)第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多因此，因此，DIT-FFT的的复乘次数降至复乘次数降至 下面再讨论下面再讨论FFT中特殊的复数运算，以便进一步减少中特殊的复数运算，以便进一步减少 复数乘法次数。复数乘法次数。一般实现一次复数乘法运算需要四次一般实现一次复数乘法运算需要四次 实数乘，两次实数加实数乘，两次实数加。但对这一特。但对这一特 殊复数，任一复数殊复数，任一复数(x+jy)与其相乘时，与其相乘时，(4.3.2)（4.3.3）第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多只需要两次实数加和两次实数乘就可实现。这样，只需要两次实数加和两次实数乘就可实现。这样，对应的每个蝶形节省对应的每个蝶形节省两次实数乘两次实数乘。第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多在在DIT-FFT运算流图中，从运算流图中，从L=3至至L=M级，每级级，每级都包含旋转因子都包含旋转因子 ，第，第L级中，级中，对应对应N/2L个蝶个蝶形运算。因此从第三级至最后一级，旋转因子形运算。因此从第三级至最后一级，旋转因子 节省的实数乘次数与节省的实数乘次数与(4.3.2)式相同。式相同。所以从实数乘运算考虑，计算所以从实数乘运算考虑，计算N=2M点点DIT-FFT所所需需实数乘法实数乘法次数为次数为(4.3.4)第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多在基在基2FFT程序中，若包含了所有旋转因子，则称该程序中，若包含了所有旋转因子，则称该算法为一类碟形单元运算；若去掉算法为一类碟形单元运算；若去掉 的旋转因子，的旋转因子，则称之为二类碟形单元运算；若再去掉则称之为二类碟形单元运算；若再去掉 的旋转因的旋转因子，则称为三类碟形单元运算；若再判断处理子，则称为三类碟形单元运算；若再判断处理，则称之为四类碟形运算。我们将后三种运算称为多类，则称之为四类碟形运算。我们将后三种运算称为多类碟形单元运算。显然，碟形单元运算。显然，碟形单元类型越多，编程就越复碟形单元类型越多，编程就越复杂，但当杂，但当N较大时，乘法运算的减少量是相当可观的。较大时，乘法运算的减少量是相当可观的。例如，例如，N=4096时，三类碟形单元运算的乘法次数为一类时，三类碟形单元运算的乘法次数为一类碟形单元运算的碟形单元运算的75%。第第第第4 4章章章章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换(FFT)(FFT)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多4.3.2 旋转因子的生成旋转因子的生成在在FFT运算中，旋转因子运算中，旋转因子，求正弦和余弦函数值的计算量是很，求正弦和余弦函数值的计算量是很大的。所以编程时，产生旋转因子的方法直接影响运大的。所以编程时，产生旋转因子的方法直接影响运算速度。算速度。一种方法是在每级运算中直接产生；另一种一种方法是在每级运算中直接产生；另一种方法是在方法是在FFT程序开始前预先计算出程序开始前预先计算出，m=0，1，N/21，存放在数组存放在数组中，作为旋转因子表，在中，作为旋转因子表，在程序执行过程中直接查表得到所需旋转因子值，不再程序执行过程中直接查表得到所需旋转因子值，不再计算。计算。这样使运算速度大大提高，其不足之处是占用这样使运算速度大大提