《教学课件第七讲快速傅里叶变换FFT》由会员分享，可在线阅读，更多相关《教学课件第七讲快速傅里叶变换FFT（44页珍藏版）》请在金锄头文库上搜索。
1、第七讲第七讲 快速傅里叶变换快速傅里叶变换 (FFT) (FFT)Q&A办公室办公室: 51971617: 51971617手手 机：机：Email: Email: 本本讲讲在在分分析析直直接接计计算算DFT的的特特点点的的基基础础上上介介绍绍DFT的的快快速速算算法法-快快速速傅傅里里叶叶变变换换(FFT)；同同时时简简要要介介绍绍了了FFT算算法法的的发发展展历历程程；此此外外还还要要介介绍绍FFT的的两两种种最最常常用用的的算算法法基基于于时时间间抽抽取取的的FFT（DIT：库库利利图图基基算算法法）和和基基于于频频率率抽取的抽取的FFT（DIF：桑德图基算法）。：桑德图基算法）。一、直
2、接计算一、直接计算DFTDFT存在的问题存在的问题N点序列点序列x(n)的的DFT变换定义为：变换定义为：计计算算X(k)的的运运算算量量：需需要要N2次次复复数数乘乘法法，N(N1)次复数加法。在次复数加法。在N较大时计算量很大。较大时计算量很大。例例如如：N1024时时, 需需要要1,048,576次次复复数数乘乘法法, 即即4,194,304次实数乘法次实数乘法对对于于象象雷雷达达、通通信信、声声纳纳等等需需要要实实时时处处理理的的信信号号，因因为为其其运运算算量量更更大大，所所以以无无法法满满足足信信号号处处理理的的实实时时性要求。迫切需要有新的算法。性要求。迫切需要有新的算法。 二、
3、二、DFT运算的特点运算的特点实实际际上上，DFT运运算算中中包包含含有有大大量量的的重重复复运运算算。在在WN 矩矩阵阵中中，虽虽然然其其中中有有N2个个元元素素，但但由由于于WN的的周周期期性性，其其中中只只有有N个个独独立立的的值值，即即 ，且且这这N个个值值也也有有一一些些对对称称关关系系。总总之之，WN因因子子具具有有如如下所述周期性及对称性：下所述周期性及对称性：1.1.对称性对称性2.2.周期性周期性由上述特性还可得出：由上述特性还可得出：利利用用上上述述对对称称特特性性，可可使使DFT运运算算中中有有些些项项可可以以合合并并，这这样样，可可使使乘乘法法次次数数减减少少大大约约一
4、一半半；利利用用WN矩矩阵阵的的对对称称性性及及周周期期性性，可可以以将将长长序序列列的的DFT分分解解为为短序列的短序列的DFT，N越小，运算量能够减少。越小，运算量能够减少。例例如如，对对于于四四点点的的DFT，直直接接计计算算需需要要16次次复复数数乘乘法，根据上述特性可以有以下形式的算法：法，根据上述特性可以有以下形式的算法：第二列和第三列交换，则：第二列和第三列交换，则：则有：则有：由此得出：由此得出：从从上上例例可可知知，通通过过应应用用对对称称性性和和周周期期性性，4点点的的DFT实际上只需要进行一次复数乘法。实际上只需要进行一次复数乘法。三、三、FFT发展简介发展简介FFT的的
5、实实质质：快快速速傅傅里里叶叶变变换换(FFT)并并不不是是一一种种新新的的变变换换，是是为为了了改改进进和和提提高高离离散散傅傅里里叶叶变变换换(DFT)运运算算速速度度基基于于DFT运运算算特特点点而而发发展展起起来来的的DFT快快速算法，其实质还是速算法，其实质还是DFT。FFT发发展展的的原原因因：DFT是是信信号号分分析析与与处处理理中中的的一一种种重重要要变变换换，广广泛泛应应用用于于通通信信、图图像像处处理理、雷雷达达及及声声纳纳等等领领域域，由由于于其其计计算算量量与与变变换换区区间间长长度度N的的平平方方成成正正比比，在在N较较大大时时，计计算算量量很很大大，使使得得直直接接
6、应用应用DFT进行实时处理信号是不现实的。进行实时处理信号是不现实的。FFT的发展历程：的发展历程：1965年年，J. W. Cooley和和J. W. Tukey巧巧妙妙应应用用DFT中中W因因子子的的周周期期性性及及对对称称性性提提出出了了最最早早的的FFT，这这是是基基于于时时间间抽抽取取的的FFT。具具有有里里程程碑碑式式的的贡贡献献(运运算算量量缩短两个数量级缩短两个数量级)1966年，年，G. Sand提出了基于频率抽取的提出了基于频率抽取的FFT算法算法1975年年，Winogard提提出出WFTA法法；1977年年Kolha和和Parks提出素因子算法（提出素因子算法（PFA）
7、1984年年，P. Dohamel和和H. Hollmann提提出出分分裂裂基基快快速速算算法法，进进一一步步减减少少了了计计算算量量，提提高高了了计计算算速速度度（目目前最理想的算法）前最理想的算法）FFT的各种算法的各种算法纵观纵观FFT的发展历程，的发展历程，FFT算法分成算法分成两大类两大类：(1) 针针对对N等等于于2的的整整数数次次幂幂的的算算法法，如如基基2算算法法、基基4算法、实因子算法和分裂基算法算法、实因子算法和分裂基算法(2)针针 对对 N不不 等等 于于 2的的 整整 数数 次次 幂幂 的的 算算 法法 ， 其其 以以Winograd为为 代代 表表 的的 一一 类类
8、算算 法法 (素素 因因 子子 法法 PFA、Winograd算法算法WFTA)简要介绍库利简要介绍库利-图基算法和桑得图基算法和桑得-图基算法图基算法设设序序列列x(n)的的长长度度为为N，且且满满足足N2M，M为为自自然然数，按数，按n的奇偶将的奇偶将x(n)分解为两个分解为两个N/2的子序列：的子序列：x1(r)=x(2r), r=0,1,2,N/2-1x2(r)=x(2r+1) r=0,1,2,N/2-1则则x(n)的的DFT为：为：1.基本原理基本原理四、按时间抽取四、按时间抽取(DIT)的的FFT库利库利-图基算法图基算法因为因为 ，所以：，所以：上式中上式中X1(k)和和X2(k
9、)分别为分别为x2(r)和和x2(r)的的N/2点点DFT，即，即由由于于X1(k)和和X2(k)均均以以N/2为为周周期期，且且 ，以以X(k)又可表示为：又可表示为：即将一个即将一个N点的点的DFT分解成为两个分解成为两个N/2点的点的DFT。上述运算可用右下图来表示，称为蝶形运算符号。上述运算可用右下图来表示，称为蝶形运算符号。从右图可知，要完成一从右图可知，要完成一个蝶形运算需要进行一个蝶形运算需要进行一次复数相乘和两次复数次复数相乘和两次复数相加运算。相加运算。下图是下图是N8时的一个分解运算图。时的一个分解运算图。从从上上图图可可知知，经经过过一一次次分分解解后后，计计算算一一个个
10、N点点的的DFT共需要计算两个共需要计算两个N/2点点FFT和和N/2个蝶形运算。个蝶形运算。计计算算一一个个N/2点点DFT需需要要(N/2)2复复数数乘乘和和N/2(N/2-1)次次复复数数加加法法。所所以以按按刚刚才才的的方方法法计计算算N点点DFT总总的的运运算算量量为为2(N/2)2+N/2=N(N+1)/2N2/2(N1时时)复复数数次乘法和次乘法和N(N/2-1)+2N/2=N2/2次复数加法运算。次复数加法运算。由由此此可可见见，仅仅仅仅经经过过一一次次分分解解就就能能使使运运算算量量减减少少近近一半！一半！因为因为N/2仍然是偶数，可以作进一步的分解：仍然是偶数，可以作进一步
11、的分解：与第一次分解相同，将与第一次分解相同，将x1(r)按奇偶分解成两个按奇偶分解成两个N/4的子序列的子序列x3(l)和和x4(l), 即：即：则，则，X1(k)又可表示为：又可表示为：同理，同理，X3(k)和和X4(k)的周期性和的周期性和WN的对称性，到的对称性，到最后我们能够得到：最后我们能够得到：同理可得：同理可得：其中：其中：这这样样，又又将将N/2点点的的DFT分分解解为为两两个个N/4点点的的DFT。依依次次类类推推，经经过过M-1次次分分解解，最最后后将将N点点DFT分分解解成成N/2个个2点点DFT。一一个个完完整整的的8点点DFT-FFT运运算算流流图如下图所示。图如下
12、图所示。2.运算量的比较运算量的比较从上述分析过程可知，在从上述分析过程可知，在N2M时，每一级都由时，每一级都由N/2个蝶形运算构成，即每级都需要个蝶形运算构成，即每级都需要N/2次复数乘次复数乘和和N次复数加，所以总的复数乘的次数为：次复数加，所以总的复数乘的次数为：总的复数加的次数为：总的复数加的次数为：直接计算时复数乘的次数为直接计算时复数乘的次数为N2，加为，加为N(N-1)次。当次。当N1时，时， ，使运算量大大减少。，使运算量大大减少。以以N1024为例，其运算量与直接计算的比例为：为例，其运算量与直接计算的比例为：即即运运算算效效率率提提高高了了200多多倍倍。易易知知N越越大
13、大，优优越越性性越越明明显显。另另外外，在在N2048时时，直直接接运运算算需需要要3个个小时，而采用小时，而采用FFT则只需不到一分钟就能完成！则只需不到一分钟就能完成！3.DITFFT的运算规律的运算规律(1)原位计算原位计算根根据据运运算算流流图图可可知知，DIT-FFT的的运运算算很很有有规规律律。N2M点点的的FFT共共进进行行M级级运运算算，每每级级运运算算有有N/2个个蝶蝶形形运运算算构构成成；同同一一级级中中，每每个个蝶蝶形形的的两两个个输输入入数数据据只只对对计计算算本本蝶蝶形形有有用用，并并且且每每个个蝶蝶形形的的输输入入、输输出出数数据据节节点点又又同同在在一一条条水水平
14、平线线上上，这这意意味味着着计计算算完完一一个个蝶蝶形形后后所所得得数数据据可可立立即即存存入入原原输输入入数数据据所所占占用用的的存存贮贮单单元元，这这样样，经经过过M级级运运算算后后，原原来来存存放放输输入入序序列列数数据据的的N个个存存贮贮单单元元中中并并依依次次存存放放了了X(k)的的N个个值值。这这种种利利用用同同一一存存贮贮单单元元存存贮贮计计算算输输入入、输输出出数据的方法称为原位（址）计算。数据的方法称为原位（址）计算。 (0)=(0)=X X0 0(0)(0) X X1 1(0)(0) X X2 2(0) X(0) X3 3(0)(0)=X(0) =X(0) (4)=(4)=
15、X X0 0(1)(1) X X1 1(1) X(1) X2 2(1) X(1) X3 3(1)(1)=X(1)=X(1) (2)=(2)=X X0 0(2)(2) X X3 3(2)(2)=X(2)=X(2) (6)=(6)=X X0 0(3)(3) X X3 3(3)(3)=X(3)=X(3) (1)=(1)=X X0 0(4)(4) X X1 1(4) X(4) X2 2(4) X(4) X3 3(4)(4)=X(4)=X(4) (5)=(5)=X X0 0(5)(5) X X3 3(5)(5)=X(5)=X(5) (3)=(3)=X X0 0(6)(6) X X3 3(6)(6)=X(
16、6)=X(6) (7)=(7)=X X0 0(7)(7) X X1 1(7) X(7) X2 2(7) X(7) X3 3(7)(7)=X(7)=X(7)WWWWN0N0N0N0-1-1-1-1WWWWN0N2N0N2-1-1-1-1WWWWNNNN0123.输入数据、中间运算结果和最后输出均用同一存储器。输入数据、中间运算结果和最后输出均用同一存储器。(2)旋转因子的变化规律旋转因子的变化规律在每个蝶形的运算过程中，都要乘以因子在每个蝶形的运算过程中，都要乘以因子 ，称，称其为旋转因子，其为旋转因子，p称为旋转因子指数。但各级的旋称为旋转因子指数。但各级的旋转因子和循环方式都有所不同。转因子
17、和循环方式都有所不同。旋旋转转因因子子与与运运算算级级数数有有一一定定的的关关系系，若若用用L表表示示运运算算级级数数，对对于于N2M的的一一般般情情况况，第第L级级的的旋旋转转因子为：因子为： 从从运运算算流流图图可可以以看看出出，原原位位计计算算时时，FFT的的输输出出X(k)是是按按正正常常顺顺序序排排列列在在存存储储单单元元中中，即即按按X(0)，X(1),，X(7)的的顺顺序序排排列列，但但是是这这时时输输入入x(n)都都不不是是按按自自然然顺顺序序存存储储的的，这这看看起起来来好好象象是是“混混乱乱无无序序”的的，实实际际上上是是有有规规律律的的，我我们们称称之之为倒位序。为倒位序
18、。 造造成成倒倒位位序序的的原原因因是是输输入入x(n)按按标标号号n的的偶偶奇的不断分组而造成。奇的不断分组而造成。(3)倒位序规律倒位序规律倒位序实现倒位序实现 输输入入序序列列先先按按自自然然顺顺序序存存入入存存储储单单元元, ,然然后后经经变变址址运运算算来来实实现现倒倒位位序序排排列列，设设输输入入序序列列的的序序号号为为n,n,二二进进制制为为(n(n2 2 n n1 1 n n0 0 ) )2 2 , ,倒倒位位序序顺顺序序用用 表示表示, ,其倒位序二进制为其倒位序二进制为(n(n0 0 n n1 1 n n2 2 ) )2 2 。A(1) A(2) A(3) A(4) A(5
19、) 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)变址处理方法变址处理方法存储单元存储单元自然顺序自然顺序变址变址倒位序倒位序 0 00 0 0 0 0 00 0 0 0 0 0 0 0 1 01 0 0 0 1 11 1 0 0 0 4 0 4 2 02 0 1 1 0 00 0 1 1 0 2 0 2 3 03 0 1 1 1 11 1 1 1 0 6 0 6 4 14 1 0 0 0 00 0 0 0 1 1 1 1 5 15 1 0 0 1 11 1
20、 0 0 1 5 1 5 6 16 1 1 1 0 00 0 1 1 1 3 1 3 7 17 1 1 1 1 11 1 1 1 1 7 1 7 自然顺序自然顺序n n 二进制二进制n n n n n n 倒位序二进制倒位序二进制n n n n n n 倒位顺序倒位顺序n n2 1 0 0 1 2例如例如 ，N=8时如下表：时如下表： 4.4.蝶形运算两节点的距离蝶形运算两节点的距离:2:2m-1m-1 其中其中,m,m表示第表示第m m列列, ,且且m =1, ,Lm =1, ,L 例如例如N=8=2N=8=23 3 , ,第一级第一级( (列列) )距离为距离为2 21-11-1=1,=1
21、, 第二级第二级( (列列) )距离为距离为2 22-12-1=2=2， 第三级第三级( (列列) )距离为距离为2 23-13-1=4=4。五、按频率抽取五、按频率抽取(DIF)的的FFT桑德桑德-图基算法图基算法库库利利图图基基法法是是将将输输入入序序列列按按其其顺顺序序是是奇奇数数还还是是偶偶数数来来分分解解为为越越来来越越短短的的序序列列；桑桑德德图图基基法法是是把把输输出出序序列列X(k)按按其其顺顺序序的的偶偶奇奇来来分分解解为为越越来来越越短短的的序列。序列。1.原理原理设设序序列列x(n)长长度度为为N2M，首首先先将将x(n)前前后后对对半半分分开，得到两个子序列，其开，得到
22、两个子序列，其DFT可表示为：可表示为： 由于由于 故故 因此因此 X(k)X(k)可表示为可表示为 2.N2.N点点DFTDFT按按k k的奇偶分组可分为两个的奇偶分组可分为两个N/2N/2的的DFTDFT 当当k k为偶数为偶数, ,即即 k=2r k=2r时时,(-1),(-1)k k =1 =1； 当当k k为奇数为奇数, ,即即 k=2r+1 k=2r+1 时时 (-1) (-1)k k =-1 =-1 。 这时这时 X(k)X(k) 可分为两部分：可分为两部分： k k为偶数时：为偶数时： 可见,上面两式均为N/2的DFT。k k为奇数时：为奇数时：-1-13.3.蝶形运算蝶形运算
23、-1-1-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 01 12 23 34.N=84.N=8时时, ,按按k k的奇偶分解过程的奇偶分解过程 先蝶形运算，后先蝶形运算，后DFT:DFT: 5. 5.仿照仿照DITDIT的方法的方法 再将再将N/2N/2点点DFTDFT按按k k的奇偶分解为两个的奇偶分解为两个N/4N/4点的点的DFT,DFT,如此进行下去如此进行下去, ,直至分解为直至分解为2 2点点DFTDFT。 以下是以下是8 8点的点的DIF-DFTDIF-DFT流程：流程： x(0) X(0) X(0) x(1) X(4) X(4) x(2) X(2)
24、 X(2) x(3) X(6) X(6) x(4) X(1) X(1) x(5) X(5) X(5) x(6) X(3) X(3) x(7) X(7) X(7)-1-1-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 01 12 23 3-1-1-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 02 20 02 2-1-1-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 00 00 00 0 B B. .原位运算原位运算 每级每级( (列列) )都是由都是由N/2N/2个蝶形运算构成个蝶形运算构成, ,即即 -1-1
25、W WN Nr rC.C.蝶形运算两节点的距离蝶形运算两节点的距离 一般公式为一般公式为2 2L-mL-m =N/2 =N/2m m 例如例如 N=2 N=23 3 =8 =8 ： (1)m=1 (1)m=1 时的距离为时的距离为 8/2=4 8/2=4； (2)m=2 (2)m=2 时的距离为时的距离为 8/4=2; 8/4=2; (3)m=3 (3)m=3 时的距离为时的距离为 8/8=1 8/8=1。1.1.相同点相同点 (1) (1)进行原位运算；进行原位运算； (2) (2)运算量相同运算量相同, ,均为（均为（N/2) LogN/2) Log2 2N N次复乘、次复乘、N LogN
26、 Log2 2N N次复加。次复加。2.2.不同点不同点 (1)DIT (1)DIT输入为倒位序输入为倒位序, ,输出为自然顺序；输出为自然顺序； DIF DIF正好与此相反。但正好与此相反。但DITDIT也有输入为自然顺序也有输入为自然顺序, ,输出为倒位序的情况。输出为倒位序的情况。D.DIFD.DIF法与法与DITDIT法的异同法的异同(2)(2)蝶形运算不同蝶形运算不同A.A.DITDIT用矩阵表示=11B.B.DIFDIF用矩阵表示=11(3)(3)两种蝶形运算的关系互为转置（矩阵）；两种蝶形运算的关系互为转置（矩阵）； 将将流流图图的的所所有有支支路路方方向向都都反反向向, ,交交
27、换换输输入入和和输出，即可得到另一种蝶形。输出，即可得到另一种蝶形。 A.A. DIT DITB.B.DIFDIF1111FFT算算法法，同同样样可可以以适适用用于于离离散散博博里里叶叶反反变变换换(IDFT)运运算算，并并简简称称为为IFFT，即即快快速速博博里里叶叶反反变变换，从换，从IDFT公式看：公式看：而而DFT公式公式比比较较以以上上两两式式可可知知，只只要要把把DFT运运算算中中的的每每一一个个系系数数 换换成成 ，并并且且最最后后再再乘乘以以常常数数1/N, 则则六、六、IDFT的快速算法的快速算法-IFFT以以上上所所有有时时间间抽抽取取或或频频率率抽抽取取的的FFT算算法法都都可可以以拿来运算拿来运算IDFT。此外，有一种直接采用此外，有一种直接采用FFT程序计算程序计算IFFT的方法。的方法。对对 取共轭，取共轭，则：则： 两边同时再取共轭，有：两边同时再取共轭，有：上上述述情情况况表表明明：在在进进行行IDFT运运算算的的时时候候，可可以以先先将将X(k)取取共共轭轭，直直接接调调用用FFT子子程程序序，然然后后再再取取共共轭并乘以轭并乘以1/N就可得到序列就可得到序列x(n)。此此方方法法虽虽然然两两次次取取共共轭轭，但但由由于于可可以以与与FFT共共用用一一程序，因而使用十分方便。程序，因而使用十分方便。
