《《快速傅里叶变换》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《快速傅里叶变换》PPT课件.ppt（58页珍藏版）》请在金锄头文库上搜索。
1、第4章 快速傅里叶变换(FFT) 第第4章章 快速傅里叶变换快速傅里叶变换 4.1 引言引言 4.2 直接计算直接计算DFT的问题及改进的途径的问题及改进的途径 4.3 按时间抽取（按时间抽取（DIT）的基的基2-FFT算法算法4.4 按频率抽取（按频率抽取（DIF）的基的基2-FFT算法算法4.5 离散傅里叶反变换（离散傅里叶反变换（IDFT）的快速计算方法）的快速计算方法 4.10 线性线性卷积卷积的的FFT算法算法 第4章 快速傅里叶变换(FFT) 4.1 引引 言言 快快速速傅傅里里叶叶变变换换（FFT）并并不不是是一一种种新新的的变变换换， 而而是是离离散散傅傅里里叶叶变变换换（DF
2、T）的一种快速算法的一种快速算法。 由由于于有有限限长长序序列列在在其其频频域域也也可可离离散散化化为为有有限限长长序序列列（DFT），因因此此离离散散傅傅里里叶叶变变换换（DFT）在在数数字字信信号号处处理理中中是是非非常常有有用用的的。例例如如，在在信信号号的的频频谱谱分分析析、 系系统统的的分分析析、 设设计计和和实实现现中中都都会会用用到到DFT的的计计算算。 但但是是，在在相相当当长长的的时时间间里里， 由由于于DFT的的计计算算量量太太大大，即即使使采采用用计计算算机机也也很很难难对对问问题题进进行行实实时时处处理理，所所以以并并没没有有得得到到真真正正的的运运用用。 直直到到19
3、65年年首首次次发发现现了了DFT运运算算的的一一种种快快速速算算法法以以后后，情情况况才才发发生生了了根根本本的的变变化化。人人们们开开始始认认识识到到DFT运运算算的的一一些些内内在在规规律律，从从而而很很快快地地发发展展和和完完善善了了一一套套高高速速有有效效的的运运算算方方法法， 这这就就是是现现在在人人们们普普遍遍称称之之为为快快速速傅傅里里叶叶变变换换（FFT）的的算算法法。 FFT出出现现后后使使DFT的的运运算算大大大大简简化化，运运算算时时间间一一般般可可缩缩短短一一二二个个数数量量级级之之多多，从从而而使使DFT的的运运算算在在实实际中真正得到了广泛的应用。际中真正得到了广
4、泛的应用。 第4章 快速傅里叶变换(FFT) 4.2 直接计算直接计算DFT的问题及改进的途径的问题及改进的途径 一、直接计算一、直接计算DFT的运算量的运算量 设设x(n)为为N点有限长序列，其点有限长序列，其DFT为为 k=0, 1, , N-1 （4-1） 反变换（反变换（IDFT）为为 n=0, 1, , N-1 （4-2） 第4章 快速傅里叶变换(FFT) 二二者者的的差差别别只只在在于于WN的的指指数数符符号号不不同同，以以及及差差一一个个常常数数乘乘因因子子1/N，所所以以IDFT与与DFT具具有有相相同同的的运运算算工工作作量量。 下下面面我我们们只讨论只讨论DFT的运算量。的
5、运算量。 一一般般来来说说，x(n)和和WNnk都都是是复复数数，X(k)也也是是复复数数，因因此此每每计计算算一一个个X(k)值值，需需要要N次次复复数数乘乘法法和和N-1次次复复数数加加法法。而而X(k)一一共共有有N个个点点（k从从0取取到到N-1），所所以以完完成成整整个个DFT运运算算总总共共需需要要N2次次复复数数乘乘法法及及N(N-1)次次复复数数加加法法。 在在这这些些运运算算中中乘乘法法运运算算要要比比加加法法运运算算复复杂杂，需需要要的的运运算算时时间间也也多多一一些些。因因为为复复数数运运算算实际上是由实数运算来完成的，实际上是由实数运算来完成的， 这时这时DFT运算式可
6、写成运算式可写成 第4章 快速傅里叶变换(FFT) （4-3） 由由此此可可见见，一一次次复复数数乘乘法法需需用用四四次次实实数数乘乘法法和和二二次次实实数数加加法法；一一次次复复数数加加法法需需二二次次实实数数加加法法。 因因而而每每运运算算一一个个X(k)需需4N次次实实数数乘乘法法和和2N+2(N-1)=2(2N-1)次次实实数数加加法法。 所所以以，整整个个DFT运运算算总共需要总共需要4N2次实数乘法和次实数乘法和2N(2N-1)次实数加法。次实数加法。 第4章 快速傅里叶变换(FFT) 当当然然，上上述述统统计计与与实实际际需需要要的的运运算算次次数数稍稍有有出出入入，因因为为某某
7、些些WNnk可可能能是是1或或j，就就不不必必相相乘乘了了，例例如如W0N=1，W N=-1， WNN/4=-j等等就就不不需需乘乘法法。 但但是是为为了了便便于于和和其其他他运运算算方方法法作作比比较较， 一一般般都都不不考考虑虑这这些些特特殊殊情情况况，而而是是把把WNnk都都看看成成复复数数，当当N很很大时，这种特例的影响很小。大时，这种特例的影响很小。 从从上上面面的的统统计计可可以以看看到到，直直接接计计算算DFT，乘乘法法次次数数和和加加法法次次数数都都是是和和N2成成正正比比的的，当当N很很大大时时，运运算算量量是是很很可可观观的的，有有时是无法忍受的。时是无法忍受的。 第4章
8、快速傅里叶变换(FFT) 例例3-1 根根据据式式（3-1），对对一一幅幅NN点点的的二二维维图图像像进进行行DFT变变换换，如如用用每每秒秒可可做做10万万次次复复数数乘乘法法的的计计算算机机，当当N=1024时时，问问需要多少时间（不考虑加法运算时间）？需要多少时间（不考虑加法运算时间）？ 解解 直直接接计计算算DFT所所需需复复乘乘次次数数为为（N2)21012次次，因因此此用用每每秒可做秒可做10万次复数乘法的计算机，则需要近万次复数乘法的计算机，则需要近3000小时。小时。 这这对对实实时时性性很很强强的的信信号号处处理理来来说说，要要么么提提高高计计算算速速度度，而而这这样样，对对
9、计计算算速速度度的的要要求求太太高高了了。另另外外，只只能能通通过过改改进进对对DFT的的计计算方法，以大大减少运算次数。算方法，以大大减少运算次数。 第4章 快速傅里叶变换(FFT) 二、二、 改善途径改善途径 能能否否减减少少运运算算量量，从从而而缩缩短短计计算算时时间间呢呢？仔仔细细观观察察DFT的的运运算算就就可可看看出出， 利利用用系系数数Wnk的的以以下下固固有有特特性性，就就可减少运算量：可减少运算量： （1） WNnk的共轭对称性的共轭对称性 （2） WNnk的周期性的周期性 （3） WNnk的可约性的可约性 第4章 快速傅里叶变换(FFT) 另外另外 这这样样，利利用用这这些
10、些特特性性，使使DFT运运算算中中有有些些项项可可以以合合并并，并并能能使使DFT分分解解为为更更少少点点数数的的DFT运运算算。由由于于DFT的的运运算算量量是是与与N2成成正正比比的的，所所以以N越越小小越越有有利利，因因而而小小点点数数序序列列的的DFT比大点数序列的比大点数序列的DFT的运算量要小。的运算量要小。 快快速速傅傅里里叶叶变变换换算算法法正正是是基基于于这这样样的的基基本本思思想想而而发发展展起起来来的的。它它的的算算法法形形式式有有很很多多种种，但但基基本本上上可可以以分分成成两两大大类：类： 按时间抽取按时间抽取(ecimation inTime，缩写为缩写为DIT)法
11、法 按按频频率率抽抽取取(Decimationin Frequency，缩缩写写为为DIF)法法第4章 快速傅里叶变换(FFT) 4.3 按时间抽取按时间抽取(DIT)的基的基-2 FFT算法算法 (库利库利-图基算法图基算法)一、一、 算法原理算法原理 设设序序列列x(n)长长度度为为N，且且满满足足N=2L，L为为正正整整数数。按按n的的奇奇偶把偶把x(n)分解为两个分解为两个N/2点的子序列：点的子序列： （4-4） 第4章 快速傅里叶变换(FFT) 则可将则可将DFT化为化为 由于由于 ， 则上式可表示成则上式可表示成 （4-5） 第4章 快速傅里叶变换(FFT) 式中，式中，X1(k
12、)与与X2(k)分别是分别是x1(r)及及x2(r)的的N/2点点DFT： （4-6） （4-7） X1(k)，X2(k)只有只有N/2个点，即个点，即k=0, 1, , N/2-1。而而X(k)却有却有N个点，即个点，即k=0, 1, , N-1， 故故用用式式（4-5）计计算算得得到到的的只只是是X(k)的的前前一一半半（ ）的结果。）的结果。第4章 快速傅里叶变换(FFT) 所以所以 （4-8） 同理可得同理可得 （4-9） 式（式（4-8）、式（）、式（4-9）说明了）说明了后半部分后半部分k值值（N/2kN-1）所对应的所对应的X1(k),2(k)分别等于前半部分分别等于前半部分k值
13、值（0kN/2-1）所对应的所对应的X1(k), X2(k)。 （周期性）（周期性）由于由于第4章 快速傅里叶变换(FFT) 再考虑到再考虑到WkN 的的以下性质以下性质: 这这样样，把把式式（4-8）、式式（4-9）、式式（4-10）代代入入式式（4-5），就可将就可将X(k)表达为前后两部分：表达为前后两部分： （4-10） （4-11） （4-12） 第4章 快速傅里叶变换(FFT) 图图 4-1 时间抽选法蝶形运算流图符号时间抽选法蝶形运算流图符号 .蝶形运算蝶形运算第4章 快速傅里叶变换(FFT) 图图 4-2 按时间抽选将一个按时间抽选将一个N点点DFT分解分解 为两个为两个N/2
14、点点DFT（N=8） 第4章 快速傅里叶变换(FFT) (1)N/2点的点的DFT运算量运算量: 复乘次复乘次数数:复加次数复加次数:(2)两个两个N/2点的点的DFT运算量运算量:复乘次复乘次数数:复加次数复加次数: (3)N/2个蝶形运算的运算量个蝶形运算的运算量:复乘次复乘次数数:复加次数复加次数: 运算量运算量复乘复乘:复加复加:总共运算量总共运算量: *N点点DFT的的复复乘乘为为N2 ;复复加加N(N-1);与与分分解解后后相相比比可可知知,计算工作点差不多减少计算工作点差不多减少 一半。一半。第4章 快速傅里叶变换(FFT) 由由于于N=2L，因因而而N/2仍仍是是偶偶数数，可可
15、以以进进一一步步把把每每个个N/2点子序列再按其奇偶部分分解为两个点子序列再按其奇偶部分分解为两个N/4点的子序列。点的子序列。 （4-13） 例如，例如，n为偶数时的为偶数时的 N/2点分解为点分解为:第4章 快速傅里叶变换(FFT) 且且 式中：式中： （4-14） （4-15） 图图4-3给给出出N=8时时，将将一一个个N/2点点DFT分分解解成成两两个个N/4点点DFT， 由这两个由这两个N/4点点DFT组合成一个组合成一个N/2点点DFT的流图。的流图。 第4章 快速傅里叶变换(FFT) 图图 4-3 N/2点点DFT分解为两个分解为两个N/4点点DFT 第4章 快速傅里叶变换(FF
16、T) X2(k)也可进行同样的分解：也可进行同样的分解： 式中：式中： 同样对同样对n为奇数时，为奇数时，N/2点分为两个点分为两个N/4点点 的序列进行的序列进行DFT第4章 快速傅里叶变换(FFT) 图图 4-4 一个一个N=8点点DFT分解为四个分解为四个N/4点点DFT 第4章 快速傅里叶变换(FFT) 根根据据上上面面同同样样的的分分析析知知道道，利利用用四四个个N/4点点的的DFT及及两两级级蝶蝶形形组组合合运运算算来来计计算算N点点DFT，比比只只用用一一次次分分解解蝶蝶形形组组合合方方式式的的计算量又减少了大约一半。计算量又减少了大约一半。 对于对于N=8时的时的DFT, N/
17、4点即为两点点即为两点DFT,因此因此 第4章 快速傅里叶变换(FFT) 式式中中， , 故故上上式式不不需需要要乘乘法。法。可得：可得：第4章 快速傅里叶变换(FFT) 这这种种方方法法的的每每一一步步分分解解，都都是是按按输输入入序序列列在在时时间间上上的的次次序序是是属属于于偶偶数数还还是是属属于于奇奇数数来来分分解解为为两两个个更更短短的的子子序序列列，所所以以称称为为“按时间抽取法按时间抽取法”。 图图 4-5 N=8 按时间抽取的按时间抽取的FFT运算流图运算流图第4章 快速傅里叶变换(FFT) 二、二、 运算量运算量 由由按按时时间间抽抽取取法法FFT的的流流图图可可见见，当当N
18、=2L时时，共共有有L级级蝶蝶形形， 每每级级都都由由N/2个个蝶蝶形形运运算算组组成成，每每个个蝶蝶形形需需要要一一次次复复乘乘、 二二次次复复加加，因因而而每每级级运运算算都都需需N/2次次复复乘乘和和N次次复复加加，这样这样L级运算总共需要级运算总共需要 复乘数复乘数 复加数复加数 第4章 快速傅里叶变换(FFT) 由由于于计计算算机机上上乘乘法法运运算算所所需需的的时时间间比比加加法法运运算算所所需需的的时时间间多多得得多多，故故以以乘乘法法为为例例，直直接接DFT复复数数乘乘法法次次数数是是N2，FFT复复数数乘乘法法次次数数是是(N/2) log2N。 直直接接计计算算DFT与与F
19、FT算法的计算量之比为算法的计算量之比为 当当N=2048时时，这这一一比比值值为为372.4，即即直直接接计计算算DFT的的运运算算量量是是FFT运运算算量量的的372.4倍倍。当当点点数数N越越大大时时，FFT的的优优点点更更为为明显明显(见书中见书中P150.表表4-1)。 （4-20） 第4章 快速傅里叶变换(FFT) 三、按时间抽取的三、按时间抽取的FFT算法的特点算法的特点 1. 原位运算（同址运算）原位运算（同址运算） 从从图图4-5可可以以看看出出这这种种运运算算是是很很有有规规律律的的，其其每每级级（每每列列）计计算算都都是是由由N/2 个个蝶蝶形形运运算算构构成成的的，每每
20、一一个个蝶蝶形形结结构构完完成成下下述述基本迭代运算：基本迭代运算： （4-21a） （4-21b） 式式中中，m表表示示第第m列列迭迭代代，k, j为为数数据据所所在在行行数数。式式（4-21）的的蝶蝶形运算形运算如图如图4-7所示，由一次复乘和两次复加（减）组成。所示，由一次复乘和两次复加（减）组成。 第4章 快速傅里叶变换(FFT) 图图 4-7 按时间抽选的蝶形运算结构按时间抽选的蝶形运算结构 在某列进行蝶形运算的任意两个节点在某列进行蝶形运算的任意两个节点(行行)k和和j的节点变量的节点变量 就完全可以确定蝶形运算的结果就完全可以确定蝶形运算的结果 ,与其它行与其它行(节点节点)无关
21、。无关。 这样这样,蝶形运算的两个输出值仍可蝶形运算的两个输出值仍可放回蝶形运算的两个输入所在的存储器中放回蝶形运算的两个输入所在的存储器中,即实现所谓原位即实现所谓原位运算。每一组运算。每一组(列列)有有N/2个蝶形运算个蝶形运算,所以只需所以只需N个存储单元，个存储单元，可以节省存储单元。可以节省存储单元。第4章 快速傅里叶变换(FFT) 由由图图4-5的的流流图图看看出出，某某一一列列的的任任何何两两个个节节点点k和和j的的节节点点变变量量进进行行蝶蝶形形运运算算后后，得得到到结结果果为为下下一一列列k, j两两节节点点的的节节点点变变量量，而而和和其其他他节节点点变变量量无无关关，因因
22、而而可可以以采采用用原原位位运运算算，即即某某一一列列的的N个个数数据据送送到到存存储储器器后后，经经蝶蝶形形运运算算，其其结结果果为为下下一一列列数数据据，它它们们以以蝶蝶形形为为单单位位仍仍存存储储在在这这同同一一组组存存储储器器中中，直直到到最最后后输输出出，中中间间无无需需其其他他存存储储器器。也也就就是是蝶蝶形形的的两两个个输输出出值值仍仍放放回回蝶蝶形形的的两两个个输输入入所所在在的的存存储储器器中中。每每列列的的N/2 个个蝶蝶形形运运算算全全部部完完成成后后，再再开开始始下下一一列列的的蝶蝶形形运运算算。这这样样存存储储器器数数据据只只需需N个个存存储储单单元元。下下一一级级的
23、的运运算算仍仍采采用用这这种种原原位位方方式式，只只不不过过进进入入蝶蝶形形结结的的组组合合关关系系有有所所不同。不同。 这种原位运算结构可以节省存储单元，降低设备成本。这种原位运算结构可以节省存储单元，降低设备成本。 第4章 快速傅里叶变换(FFT) 2. 倒位序规律倒位序规律 FFT的的输输出出X(k)按按正正常常顺顺序序排排列列在在存存储储单单元元中中，即即按按X(0)，X(1)，X(7)的的顺顺序序排排列列，但但是是这这时时输输入入x(n)却却不不是是按按自自然然顺顺序序存存储储的的，而而是是按按x(0)，x(4)， ， x(7)的的顺顺序序存存入入存存储储单单元元，看看起起来来好好像
24、像是是“混混乱乱无无序序”的的，实实际际上上是是有有规规律律的的，我我们们称称之之为倒位序。为倒位序。 这是由奇偶分组造成的这是由奇偶分组造成的,以以N=8为例为例 说明如下说明如下:第4章 快速傅里叶变换(FFT) 造造成成倒倒位位序序的的原原因因是是输输入入x(n)按按标标号号n的的偶偶奇奇的的不不断断分分组组。 如如果果n用用二二进进制制数数表表示示为为(n2n1n0)2（当当N=8=23时时，二二进进制制为为三三位位）， 第第一一次次分分组组，由由图图4-2看看出出，n为为偶偶数数（相相当当于于n的的二二进进制制数数的的最最低低位位n0=0）在在上上半半部部分分，n为为奇奇数数（相相当
25、当于于n的的二二进进制制数数的的最最低低位位 n0=1）在在下下半半部部分分。 下下一一次次则则根根据据次次最最低低位位n1为为“0”或或是是“1”来来分分偶偶奇奇（而而不不管管原原来来的的子子序序列列是是偶偶序序列列还还是是奇奇序序列列）， 如如此此继继续续分分下下去去，直直到到最最后后N个个长长度度为为1的的子子序序列列。 图图4-8的的树树状状图描述了这种分成偶数子序列和奇数子序列的过程。图描述了这种分成偶数子序列和奇数子序列的过程。 第4章 快速傅里叶变换(FFT) 图图4-8 描述倒位序的树状图描述倒位序的树状图 第4章 快速傅里叶变换(FFT) 3.倒位序实现倒位序实现 输入序列先
26、按自然顺序存入存储单元输入序列先按自然顺序存入存储单元,然后经变址运算来然后经变址运算来实现实现倒位序排列倒位序排列。 设输入设输入序列的序号为序列的序号为n,二进制为二进制为(n2 n1 n0 )2 , 倒位序倒位序顺序用顺序用 表示表示,其其倒位序倒位序二进制为二进制为(n0 n1 n2 )2 , 例如例如 ，N=8时时如下表：如下表：表表4-2 码位的倒位序（码位的倒位序（N=8）自然顺序（n） 二进制数 倒位序二进制数 倒位序顺序（） 0123456700000101001110010111011100010001011000110101111104261537第4章 快速傅里叶变换(
27、FFT) 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) 图图 4-9 倒位序的变址处理倒位序的变址处理 (N=8)变址处理方法变址处理方法第4章 快速傅里叶变换(FFT) 4. 蝶形运算两节点的蝶形运算两节点的“距离距离” 以以图图4-5的的8点点FFT为为例例，其其输输入入是是倒倒位位序序的的，输输出出是是自自然然顺顺序序的的。 其其第第一一级级（
28、第第一一列列）每每个个蝶蝶形形的的两两节节点点间间“距距离离”为为1， 第第二二级级每每个个蝶蝶形形的的两两节节点点“距距离离”为为2， 第第三三级级每每个个蝶蝶形形的的两两节节点点“距距离离”为为4。 由由此此类类推推得得，对对N=2L点点FFT，当当输输入入为为倒倒位位序序， 输输出出为为正正常常顺顺序序时时，其其第第m级级运运算算，每每个个蝶蝶形形的的两两节节点点“距距离离”为为2m-1。 第4章 快速傅里叶变换(FFT) 5. WNr的确定的确定 由由于于对对第第m级级运运算算，一一个个DFT蝶蝶形形运运算算的的两两节节点点“距距离离”为为2m-1， 因而式（因而式（4-21）可写成）
29、可写成: （4-22a） （4-22b） 为为了了完完成成上上两两式式运运算算，还还必必须须知知道道系系数数Nr的的变变换换规规律律： 把把式式（4-22）中中蝶蝶形形运运算算两两节节点点中中的的第第一一个个节节点点标标号号值值， 即即k值，表示成值，表示成L位（注意位（注意N=2L）二进制数；）二进制数； 第4章 快速傅里叶变换(FFT) 把把此此二二进进制制数数乘乘上上2L-m，即即将将此此L位位二二进进制制数数左左移移M-m位位（注注意意m是是第第m级级运运算算），把把右右边边空空出出的的位位置置补补零零， 此此数数即即为所求为所求r的二进制数。的二进制数。 从从图图4-5看看出出，WN
30、r因因子子最最后后一一列列有有N/2种种，顺顺序序为为WN0， WN1， ， 其余可类推。其余可类推。 第4章 快速傅里叶变换(FFT) 6.存储单元存储单元 存输入序列存输入序列 需需N个存储单元个存储单元存放系数存放系数 需需N/2个存储单元；个存储单元； 共计共计需需(N+N/2)个存储单元。个存储单元。第4章 快速傅里叶变换(FFT) 四、四、 按时间抽取的按时间抽取的FFT算法的其他形式流图算法的其他形式流图 显显然然，对对于于任任何何流流图图，只只要要保保持持各各节节点点所所连连的的支支路路及及传传输输系系数数不不变变，则则不不论论节节点点位位置置怎怎么么排排列列所所得得流流图图总
31、总是是等等效效的的，所所得得最最后后结结果果都都是是x(n)的的DFT的的正正确确结结果果，只只是是数数据据的的提提取取和和存存放放的的次次序序不不同同而而已已。这这样样就就可可得得到到按按时时间间抽抽取取的的FFT算算法法的的若若干其他形式流图。干其他形式流图。 将将图图4-5中中和和x(4)水水平平相相连连的的所所有有节节点点和和x(1)水水平平相相连连的的所所有有节节点点位位置置对对调调，再再将将和和x(6)水水平平相相连连的的所所有有节节点点与与和和x(3)水水平平相相连连的的所所有有节节点点对对调调，其其余余诸诸节节点点保保持持不不变变，可可得得图图4-11的的流流图。图。 图图4-
32、11与图与图4-5的蝶形相同，运算量也一样，不同点是：的蝶形相同，运算量也一样，不同点是： 第4章 快速傅里叶变换(FFT) 数数据据存存放放的的方方式式不不同同，图图4-5是是输输入入倒倒位位序序、输输出出自自然然顺顺序，图序，图4-11是输入自然顺序、输出倒位序；是输入自然顺序、输出倒位序； 取取用用系系数数的的顺顺序序不不同同，图图4-5的的最最后后一一列列是是按按 的的顺顺序序取取用用系系数数，且且其其前前一一列列所所用用系系数数是是后一列所用系数中具有偶数幂的那些系数（例如后一列所用系数中具有偶数幂的那些系数（例如 ）；图图4-11是是最最后后一一列列是是按按 的的顺顺序序取取用用系
33、系数数，且且其其前前一一列列所所用用系系数数是是后后一一列列所所用用系系数数的的前前一一半半， 这这种种流流图图是是最初由库利和图基给出的时间抽取法。最初由库利和图基给出的时间抽取法。 经经过过简简单单变变换换，也也可可得得输输入入与与输输出出都都是是按按自自然然顺顺序序排排列列的的流图以及其他各种形式的流图流图以及其他各种形式的流图 。第4章 快速傅里叶变换(FFT) 图图 4-10 时间抽取、时间抽取、 输入自然顺序、输入自然顺序、 输出倒位序的输出倒位序的FFT流图流图 第4章 快速傅里叶变换(FFT) 4.4 按频率抽取（按频率抽取（DIF）的基的基 -2 FFT算法（桑德算法（桑德-
34、图基算法）图基算法） 一、一、 算法原理算法原理 仍仍设设序序列列点点数数为为N=2L，L为为正正整整数数。在在把把输输出出X(k)按按k的的奇奇偶偶分分组组之之前前，先先把把输输入入序序列列按按前前一一半半、后后一一半半分分开开（不不是是按按偶偶数、数、 奇数分开），奇数分开）， 把把N点点DFT写成两部分。写成两部分。 k=0, 1, , N-1 第4章 快速傅里叶变换(FFT) 由于由于 ，故故，可得可得 k=0, 1, , N-1 当当k为为偶偶数数时时，(-1)k=1；k为为奇奇数数时时，(-1)k=-1。因因此此，按按k的奇偶可将的奇偶可将X(k)分为两部分分为两部分: 为前一半输
35、入与后一半输入之和的N/2点DFT第4章 快速傅里叶变换(FFT) 为前一半输入与后一半输入之差再与为前一半输入与后一半输入之差再与WNn之积的之积的N/2点点DFT。第4章 快速傅里叶变换(FFT) 图图 4-14 按频率抽取蝶形运算流图符号按频率抽取蝶形运算流图符号 第4章 快速傅里叶变换(FFT) 这样可把一个N点DFT按k的奇偶分解为两个N/2点的DFT。 N=8时，上述分解过程示于图4-15。 图图 4-15 按频率抽取，将按频率抽取，将N点点DFT分解为两个分解为两个N/2点点DFT的组合的组合 第4章 快速傅里叶变换(FFT) 由于由于N=2L，N/2仍是一个偶数，因而可以将每个
36、仍是一个偶数，因而可以将每个N/2点点DFT的输出再分解为偶数组与奇数组，这就将的输出再分解为偶数组与奇数组，这就将N/2点点DFT进一步进一步分解为两个分解为两个N/4 点点DFT。 图图4-16示出了这一步分解的过程。示出了这一步分解的过程。 第4章 快速傅里叶变换(FFT) 图图 4-16 按频率抽取的第二次分解按频率抽取的第二次分解 第4章 快速傅里叶变换(FFT) 这这样样的的分分解解可可以以一一直直进进行行到到第第L次次（N=2L），第第L次次实实际际上上是是做做两两点点DFT，它它只只有有加加减减运运算算。 然然而而，为为了了有有统统一一的的运运算算结结构构，仍仍然然用用一一个个
37、系系数数为为WN0的的蝶蝶形形运运算算来来表表示示， 这这N/2个个两两点点DFT的的N个个输输出出就就是是x(n)的的N点点DFT的的结结果果X(k)。 图图4-16表表示示一一个个N=8 完整的按频率抽取的基完整的按频率抽取的基-2 FFT运算结构。运算结构。 第4章 快速傅里叶变换(FFT) 图图 4-16 按频率抽取的按频率抽取的FFT流图流图 （N=8）第4章 快速傅里叶变换(FFT) 4.5 离散傅里叶反变换的快速计算方法离散傅里叶反变换的快速计算方法(IFFT)一一. .稍微变动稍微变动FFTFFT程序和参数可实现程序和参数可实现IFFTIFFT 比较两式可知比较两式可知,只要只
38、要DFT的每个系数的每个系数 换成换成 ,最后再最后再乘乘 以常数以常数1/N就可以得到就可以得到IDFT的快速算法的快速算法-IFFT。 另外另外,可以将常数可以将常数1/N分配到每级运算中分配到每级运算中, , 也就是每级也就是每级蝶形运算均乘以蝶形运算均乘以1/2。第4章 快速傅里叶变换(FFT) 二二. .不改不改(FFT)(FFT)的程序直接实现的程序直接实现IFFTIFFT 这就是说这就是说,先将先将X(k)取共轭取共轭,即将即将X(k)的虚部乘的虚部乘-1，直接利用，直接利用FFT程序计算程序计算DFT；然后再取一次共然后再取一次共轭；最后再乘轭；最后再乘1/N,即得即得x(n)
39、。所。所以以FFT,IFFT可用可用一个子程序。一个子程序。第4章 快速傅里叶变换(FFT) 一一.线性卷积的长度线性卷积的长度 设一离散线性移不变系统的冲激响应为设一离散线性移不变系统的冲激响应为 ,其输入信其输入信号为号为 . 其输出为其输出为 . 并且并且 的长度为的长度为L点点, 的的 长度为长度为M点点,则：则：4.10 线性卷积的线性卷积的FFT算法算法第4章 快速傅里叶变换(FFT) 二二.用用FFTFFT算算 的步骤：的步骤：第4章 快速傅里叶变换(FFT) 流程图流程图FFTFFTIFFTx(n)h(n)y(n)X(k)H(k)Y(k)第4章 快速傅里叶变换(FFT) 三三.几点说明几点说明 1. 当 M=L 时,用圆周卷积计算线性 卷积的速度快,点数越多,速度越快, N64时,速度增加明显. 2. LM 时,速度增加不太明显,为了 增加速度,采用 (1)重叠相加法 (2) 重叠保留法(从略).
