第二章-离散傅里叶变换及其快速算法05课件

第二章离散傅里叶变换及快速算法

快速傅里叶变换（FFT）1可得N=8DITFFT算法流图

2

即DITFFT运算量与Nlog2N成正比，而直接计算DFT与

N2成正比。如：N=1024，则每级共有N/2个蝶形，而每个蝶形有一次复乘和两次复加。3如：N=8,输入顺序为看输入输出的序号的规律，若将n用3位二进制数表示，

1、算法特点(2)输入反序，输出正序(顺序)输出顺序为42.3.2按频率抽取的FFTN=2M将x(n)按n的顺序分成前后两半一、算法原理：前半子序列：后半子序列：由定义5重写DIF算法原理6重写：蝶形-1DIF算法原理7经顺序分解，将N点DFT按k的奇偶分成了两个新的序列的N/2点DFT。当N=8时，如下图示：N/2点DFTN/2点DFT-1-1-1-1DIF算法原理8-1-1-1-1DIF算法原理9WN0WN2x1(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继续分解，可得(经再次分解),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-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（1）蝶形运算；（2）原位计算；（3）序数重排；（4）蝶形类型随迭代次数成倍减少。按频率抽取法FFT也有以下运算特点：13二、时间抽取法与频率抽取法的比较

DIT法与DIF法的区别1、DIF输入是自然顺序，输出是倒序的，DIT法正好相反；2、DIF的基本碟形DIT的基本碟形不同，DIF的复乘出现在减法之后；

3、DIF与DIT运算则相同；4、DIF法与DIT法基本碟形是互为转置的。

14-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本节结束总结16

以上讨论的都是以2为基数的FFT算法，即N=2M，这种情况实际上使用得最多。

优点：程序简单，效率高，使用方便。实际应用时，有限长序列的长度N很大程度上由人为因素确定，因此多数场合可取N=2M，从而直接使用以2为基数的FFT算法。

§2.3.3N为组合数的FFT算法

17

如N不能人为确定,N的数值也不是以2为基数(N≠2M)的整数，该情况处理方法有两种:

①补零:将x(n)补零,使之满足N=2M.

例如N=30,补上x(30)=x(31)=0两点,使N=32=25,这样可直接采用以2为基数M=5的FFT程序。

§2.3.3N为组合数的FFT算法

有限长度序列补零后并不影响其频谱X(ejω)，只是频谱的采样点数增加了，上例中由30点增加到32点，所以在许多场合这种处理是可接受的。18②如要求准确的N点DFT值,可采用任意数为基数的FFT算法,其计算效率低于以2为基数FFT算法。如N为复合数，可分解为两个整数P与Q的乘积。

复合数FFT的基本思想是将DFT的运算尽量减小。在N=PQ情况下，也希望将N点的DFT分解为P个Q点DFT或Q个P点DFT以减少计算量。

§2.3.3N为组合数的FFT算法

19

§2.3.3N为组合数的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点抽取一个数据。通式：20N为组合数的FFT算法21而分解后运算量分析22运算量分析23若N=4m,就是基－4FFT算法对每个k计算上述4式只需3次复乘和12次复加，因此分解一次共需3N/4次复乘和3N次复加，而4点DFT不需要乘法运算，因此分解m级总的复乘次数为如：N=1024，基－2FFT需乘法次数5120，而基－4FFT只需3072次运算量分析24例：画出N=6点的FFT信号流图=253点DFT例：画出N=6点的FFT信号流图26同理：例：画出N=6点的FFT信号流图27具体流图如下：例：画出N=6点的FFT信号流图28本节结束总结29经常不断地学习,你就什么都知道。你知道得越多,你就越有力量StudyConstantly,AndYouWillKnowEverything.TheMoreYouKn