资源描述
快速快速FFTFFT变换变换第二章第二章 离散傅里叶变换及快速算法离散傅里叶变换及快速算法快速傅里叶变换（FFT）1快速快速FFTFFT变换变换可得可得N=8 DIT FFT算法流图算法流图 2快速快速FFTFFT变换变换 即即DIT FFT运算量与运算量与 Nlog2N 成正比，而直接计算成正比，而直接计算DFT与与 N 2 成正比。成正比。如：如：N=1024，则，则 每级共有每级共有N/2个蝶形，而每个蝶形有一次复乘和两次复加。个蝶形，而每个蝶形有一次复乘和两次复加。3快速快速FFTFFT变换变换如：如：N=8,输入顺序为输入顺序为看输入输出的序号的规律，若将看输入输出的序号的规律，若将n用用3位二进制数位二进制数表示，表示，1、算法特点、算法特点(2)输入反序，输出正序输入反序，输出正序(顺序顺序)输出顺序为输出顺序为4快速快速FFTFFT变换变换2.3.2 按频率抽取的按频率抽取的FFTN=2M 将将x(n)按按n的顺序分成前后两半的顺序分成前后两半一、算法原理：一、算法原理：前半子序列：前半子序列：后半子序列：后半子序列：由定义由定义5快速快速FFTFFT变换变换重写重写DIF算法原理算法原理6快速快速FFTFFT变换变换重写：重写：蝶形蝶形-1DIF算法原理算法原理7快速快速FFTFFT变换变换经顺序分解，将经顺序分解，将N点点DFT按按k的奇偶分成了两个新的序的奇偶分成了两个新的序列的列的N/2点点DFT。当。当N=8时，如下图示：时，如下图示：N/2点点 DFTN/2点点 DFT-1-1-1-1DIF算法原理算法原理8快速快速FFTFFT变换变换-1-1-1-1DIF算法原理算法原理9快速快速FFTFFT变换变换WN0WN2x1(0)x1(1)x1(2)x1(3)x3(0)x3(1)x4(0)x4(1)WN0WN2x2(0)x2(1)x2(2)x2(3)x5(0)x5(1)x6(0)x6(1)DIF算法原理算法原理-1-1-1-110快速快速FFTFFT变换变换继续分解，可得继续分解，可得(经再次分解经再次分解),N=8时的时的DIF流图如下流图如下WN0WN2x1(0)x1(1)x1(2)x1(3)x3(0)x3(1)x4(0)x4(1)X(0)X(4)N/4点点 DFTX(2)X(6)N/4点点 DFTx5(0)WN0WN2x2(0)x2(1)x2(2)x2(3)x5(1)x6(0)x6(1)X(1)X(5)N/4点点 DFTX(3)X(7)N/4点点 DFT-1-1-1-18点点DIF流图流图-1-1-1-111快速快速FFTFFT变换变换-1-1-1-1WN0WN2x1(0)x1(1)x1(2)x1(3)x3(0)x3(1)x4(0)x4(1)X(0)X(4)X(2)X(6)x5(0)WN0WN2x2(0)x2(1)x2(2)x2(3)x5(1)x6(0)x6(1)X(1)X(5)X(3)X(7)WN0WN0WN0WN0-1-1-1-1-1-1-1-18点点DIF流图流图12快速快速FFTFFT变换变换（1）蝶形运算；）蝶形运算；（2）原位计算；）原位计算；（3）序数重排；）序数重排；（4）蝶形类型随迭代次数成倍减少。）蝶形类型随迭代次数成倍减少。按频率抽取法按频率抽取法FFT也有以下运算也有以下运算特点特点：13快速快速FFTFFT变换变换二、时间抽取法与频率抽取法的比较二、时间抽取法与频率抽取法的比较 DIT法与法与DIF法的区别法的区别 1、DIF输输入入是是自自然然顺顺序序，输输出出是是倒倒序序的的，DIT法法正正好相反；好相反；2 2、DIF的的基基本本碟碟形形DIT的的基基本本碟碟形形不不同同，DIF的的复复乘出现在减法之后；乘出现在减法之后；3 3、DIF与与DIT 运算则相同；运算则相同；4 4、DIF法与法与DIT法基本碟形是互为转置的。法基本碟形是互为转置的。14快速快速FFTFFT变换变换-1-1-1-1WN0WN2x1(0)x1(1)x1(2)x1(3)x3(0)x3(1)x4(0)x4(1)X(0)X(4)X(2)X(6)x5(0)WN0WN2x2(0)x2(1)x2(2)x2(3)x5(1)x6(0)x6(1)X(1)X(5)X(3)X(7)WN0WN0WN0WN0-1-1-1-1-1-1-1-1DIT与与DIF比较比较15快速快速FFTFFT变换变换本节结束本节结束总结总结16快速快速FFTFFT变换变换 以上讨论的都是以以上讨论的都是以2为基数的为基数的FFT算法，即算法，即N=2M，这种情况实际上使用得最多。这种情况实际上使用得最多。优点：程序简单，效率高，使用方便优点：程序简单，效率高，使用方便。实实际际应应用用时时，有有限限长长序序列列的的长长度度N很很大大程程度度上上由由人人为为因因素素确确定定，因因此此多多数数场场合合可可取取 N=2M，从从而而直直接接使用以使用以2为基数的为基数的FFT算法。算法。2.3.3 N为组合数的为组合数的FFT算法算法 17快速快速FFTFFT变换变换 如如N不能人为确定不能人为确定,N的数值也不是以的数值也不是以2为基数为基数(N2M)的整数，该情况处理方法有两种的整数，该情况处理方法有两种:补零补零:将将x(n)补零补零,使之满足使之满足N=2M.例例如如N=30,补补上上x(30)=x(31)=0两两点点,使使N=32=25,这这样样可直接采用以可直接采用以2为基数为基数M=5的的FFT程序。程序。2.3.3 N为组合数的为组合数的FFT算法算法 有限长度序列补零后并不影响其频谱有限长度序列补零后并不影响其频谱 X(ej)，只是，只是频谱的采样点数增加了，上例中由频谱的采样点数增加了，上例中由30点增加到点增加到32点，点，所以在许多场合这种处理是可接受的。所以在许多场合这种处理是可接受的。18快速快速FFTFFT变换变换 如要求准确的如要求准确的N点点DFT值值,可可采用任意数为基数的采用任意数为基数的FFT 算法算法,其计算效率低于以其计算效率低于以2为基数为基数FFT算法。算法。如如 N 为复合数，可分解为两个整数为复合数，可分解为两个整数 P 与与 Q 的乘积。的乘积。复合数复合数FFT的基本思想的基本思想是将是将DFT的运算尽量减小。的运算尽量减小。在在 N=PQ 情情况况下下，也也希希望望将将N点点的的DFT分分解解为为P个个Q点点DFT或或Q个个P点点DFT以减少计算量。以减少计算量。2.3.3 N为组合数的为组合数的FFT算法算法 19快速快速FFTFFT变换变换 2.3.3 N为组合数的为组合数的FFT算法算法 x(0)x(3)x(6)x(9)x(12)x(1)x(4)x(7)x(10)x(13)x(2)x(5)x(8)x(11)x(14)则则 x(n)的的N点点DFT为为：可将可将x(n)分解成分解成p1组，每组有组，每组有 q1点组成，且每两点点组成，且每两点相距相距p1点。即：每隔点。即：每隔 p1 点抽取一个数据。点抽取一个数据。通式：通式：20快速快速FFTFFT变换变换N为组合数的为组合数的FFT算法算法21快速快速FFTFFT变换变换而分解后而分解后运算量分析运算量分析22快速快速FFTFFT变换变换运算量分析运算量分析23快速快速FFTFFT变换变换若若N=4m,就是基就是基4FFT算法算法对每个对每个k计算上述计算上述4式只需式只需3次复乘和次复乘和12次复加，因此分解次复加，因此分解一次共需一次共需3N/4次复乘和次复乘和3N次复加，而次复加，而4点点DFT不需要乘法不需要乘法运算，因此分解运算，因此分解m级总的复乘次数为级总的复乘次数为如：如：N=1024，基，基2FFT需乘法次数需乘法次数5120，而基，而基4FFT只需只需3072次次运算量分析运算量分析24快速快速FFTFFT变换变换例：画出例：画出N=6点的点的FFT信号流图信号流图=25快速快速FFTFFT变换变换3点点DFT例：画出例：画出N=6点的点的FFT信号流图信号流图26快速快速FFTFFT变换变换同理：同理：例：画出例：画出N=6点的点的FFT信号流图信号流图27快速快速FFTFFT变换变换具体流图如下：具体流图如下：例：画出例：画出N=6点的点的FFT信号流图信号流图28快速快速FFTFFT变换变换本节结束总结29p经常不断地学习,你就什么都知道。你知道得越多,你就越有力量pStudyConstantly,AndYouWillKnowEverything.TheMoreYouKnow,TheMorePowerfulYouWillBe写在最后Thank You在别人的演说中思考，在自己的故事里成长Thinking In Other PeopleS Speeches，Growing Up In Your Own Story讲师：XXXXXX XX年XX月XX日
展开阅读全文