数字信号处理-课件 第5章 FFT快速傅氏变换

第5章FFT快速傅氏变换22十二月2024§5-6线性卷积的FFT算法§5-4DIF的FFT算法§5-5IFFT算法§5-2DFT的运算量及改进的途径§5-1引言点击进入目录§5-3按时间抽取(DIT)的FFT算法22十二月20245-1引言

DFT在实际应用中很重要:可以计算信号的频谱、功率谱和线性卷积等。直接按DFT变换进行计算，当序列长度N很大时，计算量非常大，所需时间会很长。FFT不是一种新的变换，而是DFT算法的一种改进,这种改进实现了快速计算的目的

22十二月2024§5-2DFT的运算量及改进途径5.2.1DFT的计算量估计两公式基本结构类似，其差别仅在指数的符号不同、及逆变换的因子1/N.22十二月2024

通常x(n)和 都是复数,所以计算一个

X(k)的值需要N次复数乘法运算,和 次复数加法运算.一个X(k)的运算量,如X(1)

计算全部X(k)就要N2次复数乘法运算,N(N-1)次复数加法运算.

当N很大时,运算量将是惊人的,如N=1024,则要完成1048576次(一百多万次)运算.这样,难以做到实时处理.22十二月2024运算量估计结论1.乘法运算的时间是加法的一个量级以上2.DFT运算量与成正比1)N降低运算量的措施:2)利用的有关特性运算量（有效途径）22十二月20245.2.1降低运算量的途径

1.利用的特性得:周期性:可约性:对称性:利用上述特性,可以将有些项合并.22十二月20242.将DFT分解为短序列可以有效降低运算量,提高运算速度.1965年,cooley和Tukey首先提出FFT算法.对于N点DFT,仅需(N/2)log2N次复数乘法运算.

如:N=1024=210

，需要计算的次数是:(1024/2)log2210=512*10=5120次而5120/1048576=4.88%

速度提高20倍22十二月2024§5-3按时间抽取(DIT)FFT算法

—库利-图基算法算法原理按时间抽取基-2FFT算法与直接计算DFT运算量的比较按时间抽取的FFT算法的特点按时间抽取FFT算法的其它形式流程图22十二月2024§5-3按时间抽取(DIT)的FFT算法

—库利-图基算法5.3.1算法原理(基2-FFT)因此，n为偶数时:n为奇数时:1.N点DFT分解为两个N/2点DFT(1)先将按n的奇偶分为两组作DFT,设N=2L,不足时,可补些零。这样有:22十二月2024由于:(n为偶数)

(n为奇数)所以,上式可表示为:22十二月2024(2)两点结论:①X1(k),X2(k)均为N/2点DFT。

其中:12kN②X(k)=X

(k)+W

X

(k)能确定出

X(k)的k=个；即前一半点的结果。22十二月2024(3)X(k)的后一半的确定由于（周期性）,所以:同理:22十二月2024

可见,X(k)的后一半，也完全由X1(k),X2

(k)所确定。

N点DFT可由两个N/2点的DFT来计算.又由于

,所以22十二月2024实现上式运算的流图称作蝶形运算(4)蝶形运算（N/2个蝶形)

前一半

后一半由X1(k)、X2(k)表示X(k)的运算是一种特殊的运算-碟形运算什么是蝶形运算?22十二月2024例1(前一半)

(后一半)1111-1根据蝶形运算算法画出蝶形运算图解:22十二月2024例2以N=8为例,根据碟形图,分析N点DFT经过第一次分解,FFT计算全过程:解:1111-1先复习基本碟形运算:因此,共N/2个蝶形运算k=0,1,2…

均有一个碟形运算22十二月2024N=8,从第一次分解,看FFT计算过程:(1)由x1(n)求X1(k)(2)由x2(n)求X2(k)DFTDFT乘法次数:4

2乘法次数:4222十二月2024(3)由X1(k),X2(k)求X(k)k=0,可求出:k=1,可求出:k=2,可求出:k=3,可求出:每个碟运算1次乘法乘法次数N/2=422十二月2024第一次分解,称为第一级碟形运算X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)NW2NW1WN0-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)NW322十二月2024(1)N/2点的DFT运算量:复乘次数:(4)计算量分析复乘:总共运算量:分析N点序列经过一次奇、偶分组后的乘法计算量：N点DFT的复乘为N2;仅经过一次分解,计算量减少近一半(2)两个N/2点的DFT运算量:复乘次数:

(3)N/2个蝶形运算的运算量:复乘次数:例4N点序列经过一次奇、偶分组后成为了2个N/2点的序列解22十二月2024以N=8为例

DFT分解为两个N/2=4点的DFT的计算过程如下.22十二月2024

由X1(k)和X2(k),计算X(k)的全过程如下:

x1(0)=x(0)

x1(1)=x(2)

x1(2)=x(4)

x1(3)=x(6)

x2(0)=x(1)

x2(1)=x(3)

x2(2)=x(5)

x2(3)=x(7)

第一次分解,称为第一级碟形运算N/2点DFT

X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)NW2NW1WN0-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)N/2点DFT

NW322十二月2024第一次分解之后小结:一个N点的序列,分解成两个N/2点的序列对每一个N/2点的序列的计算,依然采用了传统的DFT算法经一次分解之后,复数乘法次数:N2/2+N/2算法量下降近一半,还需要继续改进算法继续对子序列再分解按第一次分解方法类比,继续分解直至每一序列为2点止.22十二月2024概念:蝶形信号线(节点)之距离什么是蝶形信号线距离?4距离=4NW2NW1WN0NW3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)22十二月2024例5分析N点(8点)序列经过一次奇偶分组后蝶形运算有哪些特点?

x1(0)

x1(1)

x1(2)

x1(3)

N/2点DFT

X1(0)X1(1)X1(2)X1(3)

x2(0)

x2(1)

x2(2)

x2(3)

N/2点DFT

X2(0)X2(1)X2(2)X2(3)1)N个信号线,组成N/2个蝶形.2)每一蝶形节点之间的距离为N/2.NW2NW1WN0NW3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)22十二月2024

由于N=2

L，因此，无论x1(n)还是x2(n),

每一个N/2点的序列可继续分解为两个N/4的子序列,以序列x1(n)为例,可以分解如下:5.3.2序列的第2次分解对N/4点的序列x3(n),x4(n),分别进行DFT运算,得到(偶中偶)(偶中奇)22十二月2024从而可得到X1(k)的前N/4点X1(k)的后N/4点为:22十二月2024第二次分解,每个N/2点的序列分解为2个N/4点的序列第2次分解后,时域序列的排列顺序?第1次分解,时域序列排列顺序先看序列x1(n)对应原序列x(n)设序列x1(n)分解为x3(n)和x4(n)两个序列22十二月2024接下来,再看序列x2(n)上面的顺序,对应原序列x(n)的哪些值呢?x2(n)按序号的奇偶排队如下:设序列x2(n)分解为x5(n)和x6(n)两个序列x5(n)x6(n)22十二月202422十二月2024

(0)=

(0)=(0)

(1)=

(2)=(4)

(0)=

(1)=(2)

(1)=

(3)=(6)

(0)=

(0)=(1)

(1)=

(2)=(5)

(0)=

(1)=(3)

(1)=

(3)=(7)3131414152526262因此x1(n),x2(n)两个N/2点的序列按碟形图进行计算,则有:N/2点DFTN/2点DFTWWWW0123NNNN-1-1-1-1X

(0)X

(1)X

(2)X

(3)X

(0)X

(1)X

(2)X

(3)11122221X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)-1-1-1-1N/4DFTN/4DFTN/4DFTN/4DFTX

(0)X

(1)X

(0)X

(1)334402NWWNX

(0)X

(1)X

(0)X

(1)556602NWWN22十二月2024

结论：第2次分解后,得到4个N/4点DFT

对于N=8点的DFT,N/4点即为2点DFT,因此

22十二月2024

代入展开，可得：

X

(0)X

(1)X

(0)X

(1)3344WN0WN2-1-1X

(0)X

(1)X

(0)X

(1)5566WN0WN2-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)

(0)

(4)

(2)

(6)

(1)

(5)

(3)

(7)X

(0)X

(1)X

(2)X

(3)X

(0)X

(1)X

(2)X

(3)11121222WWWWN0N1N2N3-1-1-1-1因此,8点DFT的FFT的运算流图如下：

第三次分解第二次分解第一次分解第一级运算第二级运算第三级运算-1WN0-1WN0-1WN0-1WN022十二月2024

这种FFT算法,是在时间上对输入序列

的次序是偶数还是奇数进行分解,故称为按时间抽取的算法(DIT)。

22十二月20245.3.2DIT的运算量例6FFT运算计算量估计N=8需三级蝶形运算

N=23=8,N=2L

共需L(L=3)级蝶形运算

每级都由N/2个蝶形运算组成,每个蝶形运算有一次复乘.从一个例题开始,分析FFT运算量22十二月2024

因此,N点的FFT的运算量为:复乘:mF

=（N/2）L=（N/2）log2N（复加:aF=N

L=Nlog2

N）DFT与FFT运算量之比较：N2/(N/2)log2N=2N/log2N

因此，N越大，运算量节省更明显。如教材第5章表5-1所示。22十二月2024

1.倒位序现象

由图可知,输出X(k)按正常顺序排列在存储单元,而输入是按顺序:这种顺序称作倒位序,即二进制数倒位。5.3.3DIT算法的特点22十二月2024

因奇偶分组造成的,以N=8为例分析如下:第1次分组第2次分组第3次分组000011110100110011010101=0=4=2=6=1=5=3=7N=8时，序号需要3位二进制数表示22十二月202401234567自然顺序n二进制

倒位序

倒位顺序n^0

0

00

0

10

1

00

1

11

0

01

0

11

1

01

1

10

0

010

00

1

011

0

0

01

1

0

10

1

11

1

104261537输入数据、中间运算结果和最后输出均用同一存储器。2.原位运算22十二月2024DIT基2-FFT算法与DFT直接计算运算量比较

DIT基-2FFT的信号流图可知，当N=2L时，共有

级蝶形运算；每级都由

个蝶形运算组成，而每个蝶形有

次复乘、

次复加，因此每级运算都需

次复乘和

次复加。LN/2

N/2

12N22十二月2024这样

级运算总共需要：L复数乘法：

复数加法：

直接DFT算法运算量复数乘法：

复数加法：

N2N(N－1)直接计算DFT与FFT算法的计算量之比为M22十二月2024FFT算法与直接DFT算法运算量的比较NN2计算量之比MNN2计算量之比M2414.01281638444836.641644.025665536102464.0864125.45122621442304113.816256328.0102410485765120204.83210288012.82048419430411264372.464404919221.422十二月20243.蝶形运算两节点的距离:2m-1

其中,m表示第m列,且m

=1,…,L

例如N=8=23,

第一级(列)距离为21-1=1,

第二级(列)距离为22-1=2，

第三级(列)距离为23-1=4。

4.的确定

在DIT完整蝶形运算图中，第m级蝶形运算两节点的“距离”为2m-1，因而式（5-23）可写成如下形式对于程序实现，r值的递推算法如下：（1）将上式蝶形运算两节点的第1个节点标号k表示成L位二进制数；（2）将二进制数左移L-m位，右边空位补零(即乘2L-m)（3）将所得二进制数转换为十进制数，该数即为r值。5.3.4DIT其他形式的流图1.DIT正常算法的流程图对于FFT算法流图，若各节点的连接支路以及支路系数不变，则无论各节点和支路如何变形（改变空间位置），其算法和运算量均不会改变。22十二月20242.DIT其它形式的流图对于DIT输出正常顺序,输入倒位序的蝶形运算流图，按如下两个步骤改变支路的物理位置（不改变节点的链接支路）。（1）将第2根水平线和第5根水平线平移互换位置，即x(4)水平相连的所有节点和x(1)水平相连的所有节点（包括输入数据和输出数据节点）互换位置，（2）将第4根水平线和第7根水平线平移互换位置，即x(6)水平相连的所有节点和x(3)水平相连的所有节点互换位置，该互换也包括输入数据和输出数据节点。

可得如下所示蝶形运算流图。2.DIT其它形式的流图DIT基-2FFT算法输入自然顺序、输出倒位序的FFT流图22十二月2024在不改变上图各节点的支路连接数量和连接方式的原则下，继续改变某些节点和支路的空间位置，则可以得到输入和输出均为正常顺序的FFT蝶形运算图,如下所示:2.DIT其它形式的流图

用蝶形图计算FFT,已知序列x(n)如下：

x(n)=[1，2，1，1]x(n)为4点长序列，根据DIT基-2算法，其完整蝶形图如下:虚线左边为第一级蝶形运算，从上往下4个节点的结果如下：1+1=2，1-1=0，2+1=3，2-1=1虚线右边为第二级运算，第二级运算结果如下：例7解:22十二月2024§5-4DIF的FFT算法(桑德—图基算法)5.4.1算法原理1.N点DFT的另一种表达形式22十二月2024

因此

X(k)可表为:

22十二月2024

2.N点DFT按k的奇偶分组可分为两个N/2的DFT

k为偶数时：

当k为偶数,即

k=2r时,(-1)k=1；

当k为奇数,即k=2r+1时(-1)k=-1

。这时

X(k)

可分为两部分：

22十二月2024

可见,上面两式均为N/2的DFT。k为奇数时：22十二月20243.蝶形运算-1蝶形运算图表示法之一22十二月2024蝶形运算图形表示法之二22十二月20244.N=8时,按k的奇偶分解过程X1(0)X1(1)X1(2)X1(3)-1-1-1-1WWWWNNNN0123先蝶形运算，后N/2点DFT运算:22十二月2024

5.类比DIT算法分解过程如此进行下去,直至分解为2点DFT

将N/2点DFT继续按k的奇偶分解为两个N/4点的DFT22十二月2024

(0)

(1)

(2)

(3)

(4)

(5)

(6)

(7)-1WWWWNNNN0123WWWWNNNN0202N=8点的DIF的FFT流图分析第一次分解第二次分解第三次分解第一级运算第二级运算第三级运算-1-1-1-1-1-1-1-1-1-1-1-1X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)例8解:22十二月2024由上述分析可知,N=8需三级蝶形运算N=23=8,由此可知,N=2L

共需L级蝶形运算而且每级都由N/2个蝶形运算

组成,每个蝶形运算有一次复乘。6.DIF算法的运算量22十二月2024

因此,N点的FFT的运算量为复乘:mF=（N/2）L=（N/2）log2N（复加:aF=NL=Nlog2N）DFT与FFT运算量之比较：N2/(N/2)log2N=2N/log2N

因此，N越大，运算量节省更明显。22十二月2024

1.

原位运算

每级(列)都是由N/2个蝶形运算构成,即:

-1WNr5.4.2DIF算法的特点22十二月20242.蝶形运算两节点的距离

一般公式为2L-m=N/2m

例如N=23=8

：

(1)m=1时的距离为

8/2=4；

(2)m=2

时的距离为

8/4=2;

(3)m=3

时的距离为

8/8=1。22十二月2024r的求法：

k=(n2n1n0),左移m-1位,右边空出补零,得(r)2,亦即(r)2=(k)2

2m-1.例如,N=8:(1)m=1,k=2,k=(010)2

左移0位,(r)2=(010)2=2;(2)m=2,k=1,k=(001)2

左移1位,(r)2=(010)2=2;(3)m=2,k=0,k=(001)2

左移1位,(r)2=(010)2=2.3.

的计算

由于DIF蝶形运算的两节点的距离为

N/2m,

所以蝶形运算可表为：22十二月20241.相同点

(1)都要求序列长度满足条件N=2L(2)均需要L次分解，均包含L级运算

(3)总运算量相同,均为（N/2)

Log2N次复乘

(4)编程时都可以进行原位运算；5.4.3DIF与DIT算法的比较比较如下:22十二月20242.不同点

(1)如无特别说明，DIT算法的输入为倒位序,输出为自然顺序；

DIF算法正好与DIT算法相反。但经过改进DIT算法也有输入为自然顺序,输出为倒位序的情况。22十二月2024(2)蝶形运算不同用矩阵表示=11a.DIT先乘法运算，后求和运算22十二月2024b.DIF用矩阵表示=11先求和运算，后乘法运算22十二月2024(3)两种蝶形运算的关系

互为转置（矩阵）；

将流图的所有支路方向都反向,交换输入和输出，即可得到另一种蝶形。

a.(DIT)11b.(DFT)1122十二月20245.4.4IFFT算法1.观察DFT和IDFT运算的差异

22十二月2024

比较以上两式可知，正变换和反变换差别为：

（1）正、反变换求和式指数符号不同，分别为：和

（2）反变换系数（常数）1/N，正变换系数为1。

结论：在DFT快速算法的基础上，考虑以上两点即可得到IDFT快速算法。

22十二月20241)可以将常数1/N分配到每级蝶型运算中,∵,也就是每级蝶形运算乘法运算均乘以1/2。2.IFFT快速算法之一（以DIF为例）2)将换为，即每级蝶型运算的乘法因子换为。正好等于IFFT快速算法中的因子1/N。22十二月2024

X(0)(0)

X(1)(4)

X(2)(2)

X(3)(6)

X(4)(1)

X(5)(5)

X(6)(3)

X(7)(7)-1-1-1-1WWWWNNNN0-1-2-3-1-1-1-1WWWWNNNN0-20-2-1-1-1-1WWWWNNNN0000N=8时IDFT流图如下：22十二月20243.IFFT快速算法之二

22十二月20243.IFFT快速算法之二

22十二月2024

即：

1）先将X(k)取共轭,直接利用FFT程序计算DFT；

2）求得DFT后再取一次共轭；并乘以1/N,即得x(n)。结论：

1)在FFT程序的基础上,在给定的已知数据处增加一组循环语句，求X(k)的共轭；

2)在得出结果处增加一组循环语句，对结果求共轭并乘以1/N;22十二月2024

§5-5

基4-FFT算法5.5.1基-4FFT算法原理

基-2FFT算法的原理是将N点的序列一分为二，一个N点DFT被分解为两个N/2点DFT的组合，再将N/2点DFT又一分为二，分解为4个N/4点的DFT，直至全部分解为两点DFT为止。基-4FFT的思路与基-2FFT的思路基本类似，不同点是将N点的序列一分为四，再对各子序列继续一分为四，直至分解到全部子序列为4点为止。22十二月2024因此，类似于DIT基-2的分解过程，DIT基-4快速算法先将长度为N=4L的序列x(n)，按如下方式分为四个子序列：因此，DFT变换公式改变为如下形式5.5.1基-4FFT算法原理

22十二月20245.5.1基-4FFT算法原理

根据WN的可约性，上式可以进一步化为

根据N/4点DFT公式，上式可以表示为22十二月2024其中：类似DIT基-2算法的第一次分解，上只能计算出X(k)前四分之一的值,其余值的计算需根据WN的周期性以及有限长序列隐含的周期性,类似DIT基2算法的方法，可得如下公式：22十二月2024由此可得基-4算法的基本碟形图如下：22十二月2024DIT基-4快速算法基本蝶形运算图。为了加深理解，可以根据DIT基-2算法原理进行类比。为了深入理解基-4FFT算法原理，以N=16为例分析基-4快速运算流图的规律。由于N=16=42，即L=2，流图如下所示：由于仅需2次分解，经过第一次分解之后，对于4个N/4点的DFT，各子序列长度均为4点，正好是DIT基-4快速运算的基本单元。根据基-4算法的原则，四点长的子序列DFT采用基-2FFT运算，这是基-4FFT的最后一次分解。由此可得,当N=16=42时基-4算法的完整碟形运算图如下根据原理可得第一列左上角4点基-4快速算法的蝶形运算如下图。x(n)经2次分解后，输入为正常顺序，输出为二进制倒位序图中虚线框内为一个4点基-4FFT流图的基本单元22十二月2024

§5-6

线性卷积的FFT算法5.6.1线性卷积传统计算方法

设一离散线性移不变系统的冲激响应为

,其