数字信号处理（第2版）课件 第4章-快速傅里叶变换（FFT）

1第4章快速傅里叶变换（FFT）4.5FFT算法的应用4.3按频率抽取（DIF）的基2-FFT算法4.2按时间抽取（DIT）的基2–FFT算法4.1DFT的运算量分析4.4线性调频z变换（Chirp-z）算法4.6FFT的MATLAB实现24.1DFT的运算量分析一个长度为N的有限长序列x[n]的DFT为由于x[n]可为复数，则直接计算DFT量需要复数乘法复数加法一个X[k]N次N-1次N个X[k]N2次N(N-1)

次34.1DFT的运算量分析若用实数运算来完成DFT，则有

每个复数乘法需要4次实数乘法和2次实数加法，并且每个复数加法需要2次实数加法。因此实数乘法实数加法一个X[k]4N次4N-2次N个X[k]4N2次N(4N-2)

次44.1DFT的运算量分析N

复乘

复加1625624032102499264409640321281638416256

102410485761047552

如果每次复数乘法需要100us，每次复数加法需要20us，来计算N=1024点DFT，则需要54.1DFT的运算量分析利用了系数WNkn的对称性和周期性来改善DFT计算效率对称性2.周期性合并n和（N-n）项

：64.1DFT的运算量分析且

其他项可做类似的合并，这样，乘法的次数大概可以减少1/2。但仍面临着正比于N2的大量计算。

离散傅里叶变换的高效运算方法都称为快速傅里叶变换，即FFT。FFT算法的基本思想是将一个长度为N的序列，依次分解为若干较短序列，充分利用DFT计算中的系数WNkn的周期性和对称性，将这些短序列对应的DFT进行适当的组合，达到减少运算量的目的。74.2按时间抽取（DIT）的基2–FFT算法4.2.1

算法原理

设x[n]点数为

，其中

为整数，即N为2的整数幂，若不满足，可以补零来达到，这种FFT也称基2–FFT。84.2按时间抽取（DIT）的基2–FFT算法由于94.2按时间抽取（DIT）的基2–FFT算法式中利用系数的周期性同理104.2按时间抽取（DIT）的基2–FFT算法由此(4.2-8)再考虑系数,则,上式可以写作(4.2-9)114.2按时间抽取（DIT）的基2–FFT算法图4.2-1时间抽取蝶形运算结构

可见，每一个蝶形运算需要一次复数乘法

及两次复数加法运算。12例图4.2-2按时间抽取，将一个N点DFT分解为两个N/2点DFT计算的信号流图134.2按时间抽取（DIT）的基2–FFT算法同理144.2按时间抽取（DIT）的基2–FFT算法将系数统一为,则可得图4.2-4

将一个N点DFT分解为四个N/4点DFT计算的信号流图154.2按时间抽取（DIT）的基2–FFT算法2点序列的DFT164.2按时间抽取（DIT）的基2–FFT算法图4.2-6按时间抽取，输入倒位序、输出自然顺序的8点FFT流图174.2按时间抽取（DIT）的基2–FFT算法4.2.2

DIT—FFT算法特点1.蝶形结构运算次分解，就构成

级运算过程。图中，m表示第m级蝶形运算，

。2.运算量每一个蝶形需要一次复数乘法和两次复数加法。184.2按时间抽取（DIT）的基2–FFT算法N点的DIT-FFT计算量为复数乘法：复数加法：例：

如果每次复数乘法需要100us，每次复数加法需要20us，来计算N=1024点DFT，则需要直接运算则需要125.809s。194.2按时间抽取（DIT）的基2–FFT算法--------输入信号上节点;--------输入信号下节点;--------输出信号上节点;--------输出信号下节点;j=i+dm

dm--------第m级的蝶距;sm--------第m级的蝶形组数;--------蝶形结构的W因子。20m12…v-1v12……

N/2N/4…214.2按时间抽取（DIT）的基2–FFT算法214.2按时间抽取（DIT）的基2–FFT算法例：若N=64，问第4级的中有几组蝶形运算流图？每组有多少

基本蝶形？并确定该级的权系数的种类。(1)(2)(每组8个基本蝶形)(3)或解：224.2按时间抽取（DIT）的基2–FFT算法3.原位运算

按时间抽取FFT算法流图中，可以看出每一级的蝶形运算的输入数据与以后的运算无关，因而不需要保留。在蝶形运算中，每一个输出数据Xm[l]可以直接存放在原来存储输入数据Xm-1[l]的单元中，即每一级蝶形运算输入和输出都存储在同一地址的存储单元中，这就称为原位（或同址）运算。原位运算只需要N个复数的存储单元，节省了大量的存储单元。234.2按时间抽取（DIT）的基2–FFT算法4.序数重排FFT的输出是按先后自然顺序排列的，而输入数据不是按照自然顺序，而是按倒位序排列的。

倒位序，首先将序号n用二进制码表示（如n2n1n0），然后将该二进制倒位，形成倒位序二进制数（n0n1n2），最后再将倒位序二进制数转换成十进制数。例：N=8，采用三位二进制码表示，n=6=(110)

2倒位序的二进制为

：(011)

2=6244.2按时间抽取（DIT）的基2–FFT算法十进制数二进制数倒位序二进制数倒位序顺序0000000010011004201001023011110641000011510110156110011371111117表4.1自然顺序和二进制倒位序254.2按时间抽取（DIT）的基2–FFT算法5.系数WNr的确定

对

点的DIT-FFT运算来讲，第

级运算，用N/2点的DFT合成N点DFT，系数因子用

；第

级运算，用N/4合成N/2点DFT，系数因子用

；第

级运算，用N/8合成N/4点DFT，系数因子用

；依此类推，可得所有m级运算的系数因子。-1-1-1-1-1-1-1-1X[0]X[1]X[2]X[3]X[4]X[5]X[6]X[7]X[8]X[9]X[10]X[11]X[12]X[13]X[14]X[15]-1-1-1-1-1-1-1-1WN3WN0WN1WN2WN4WN5WN6WN7-1-1-1-1-1-1-1-1WN0WN2WN4WN6WN0WN2WN4WN6-1-1-1-1-1-1-1-1WN0WN4WN0WN4WN0WN4WN0WN4x[0]x[8]x[4]x[12]x[2]x[10]x[6]x[14]x[1]x[9]x[5]x[13]x[3]x[11]x[7]x[15]WN0WN0WN0WN0WN0WN0WN0WN026274.2按时间抽取（DIT）的基2–FFT算法4.2.3按时间抽取FFT算法的其他形式流图图4.2-8按时间抽取，输入自然顺序、输出倒位序的8点FFT流图284.3按频率抽取（DIF）的基2–FFT算法4.3.1

算法原理28

仍设x[n]点数为

，

为整数，N为2的整数幂，首先将时间序列x[n]按n的顺序分为前后两部分，得。因分别计算偶序号频率样本X[2r]和奇序号频率样本X[2r+1]294.3按频率抽取（DIF）的基2–FFT算法由于304.3按频率抽取（DIF）的基2–FFT算法类似由于则314.3按频率抽取（DIF）的基2–FFT算法令有图4.3-1频率抽取蝶形运算结构324.3按频率抽取（DIF）的基2–FFT算法图4.3-2按频率抽取，将一个N点DFT分解为两个N/2点DFT计算的信号流图334.3按频率抽取（DIF）的基2–FFT算法图4.3-3

将一个N点DFT分解为四个N/4点DFT计算的信号流图344.3按频率抽取（DIF）的基2–FFT算法图4.3-4按频率抽取，输入自然顺序、输出倒位序的8点FFT流图354.3按频率抽取（DIF）的基2–FFT算法4.3.2

DIF—FFT算法特点1.蝶形结构运算2.运算量每一个蝶形需要一次复数乘法和两次复数加法。次分解，就构成

级运算过程。364.3按频率抽取（DIF）的基2–FFT算法N点的DIF-FFT计算量为复数乘法：复数加法：3.原位运算

按频率抽取FFT算法流图仍是原位运算，每一级蝶形的输入和输出在运算前后可以存储在同一地址的存储单元中。4.序数重排

按频率抽取FFT算法的输入是自然顺序，而输出是按位反转的倒位序。可见，按频率抽取的FFT算法和按时间抽取的FFT算法是两种等价的FFT运算。374.3按频率抽取（DIF）的基2–FFT算法5.系数WNr的确定

对

点的DIF-FFT运算来讲，第1级运算，将N点DFT分解为两个N/2点的DFT，系数因子

；第2级运算，将N/2点DFT分解为两个N/4点的DFT进行计算，系数因子

；第3级运算，将N/4点DFT分解为两个N/8点的DFT，系数因子

；依此类推，可得所有m级运算的系数因子。38m12…v-1v12……N/2N/4…214.3按频率抽取（DIF）的基2–FFT算法394.3按频率抽取（DIF）的基2–FFT算法4.3.3按频率抽取FFT算法的其他形式流图图4.3-6按频率抽取，输入倒位序、输出自然顺序的8点FFT流图404.4线性调频z变换（Chirp-z）算法4.4.1算法原理设N点序列x[n]，其z变换为对z变换在单位圆上采样，即DFT沿着z平面上的一条螺线作等分角取样，各取样点zk

为这里M为任意整数，A为起始点位置，表示为

。414.3线性调频z变换（Chirp-z）算法参数螺线内缩螺线外伸一段圆弧表示螺旋线上相邻两抽样点之间的等分角。——序列x[n]的线性调频z变换424.3线性调频z变换（Chirp-z）算法4.4.2线性调频z变换的快速算法利用布鲁斯坦等式令则434.3线性调频z变换（Chirp-z）算法交换变量k和n，相当于序列g[n]与h[n]卷积，然后再乘以,得，角频率

随时间n线性增长，称为Chirp信号444.5FFT算法的应用4.5.1

用FFT计算IDFT直接利用FFT的算法再次取共轭，有454.5FFT算法的应用IFFT实现步骤是：1.对X[k]取共轭，即虚部乘以-1，得到

；2.利用FFT程序计算；3.再对运算结果取一次共轭变换，并乘以常数

，

即可得到x[n]。464.5FFT算法的应用4.5.2

实序列的DFT计算（1）用一次N点FFT计算两个长度为N的实序列的N点DFT

序列x[n]和y[n]是长度为N的实序列，要求一次N点FFT求两个实序列的DFTX[k]和Y[k]。1.构成复序列2.对g[n]进行一次N点FFT运算3.利用DFT的圆周共轭对称性474.5FFT算法的应用（2）用一次N点FFT计算一个长度为2N的实序列的2N点DFT

令v[n]是长度为2N的实序列，将其偶数序号和奇数序号的样本值分别组成两个N点的实序列，即

根据上例，由x[r]和y[r]构成复序列g[n]，再对g[n]进行一次N点FFT运算，由圆周共轭对称性求出x[r]和y[r]的N点DFTX[k]和Y[k]。则v[n]的2N点DFTV[k]为：484.5FFT算法的应用即类似于按时间抽取的FFT算法494.5FFT算法的应用4.5.3

用FFT实现线性卷积（1）线性卷积的FFT实现流程图

若某FIR数字滤波器的单位样值响应为h[n]，，输入信号为x

[n]，，系统的输出

当圆周卷积和的点数N满足图4.5-1两个有限长序列线性卷积的FFT实现框图504.5FFT算法的应用（2）有限长序列和无限长序列的线性卷积当输入信号x

[n]是无限长的，或者比单位样值响应h[n]长得多，可采用分段卷积的方法，将x

[n]分割成与h[n]长度相当的段，再对信号进行分段卷积处理，有两种分段卷积的处理方法：重叠相加法和重叠保留法。重叠相加法设h[n]长度为N2，将x[n]分解成长度为N1的段，两者数量级相当xi[n]表示x[n]的第i段514.5FFT算法的应用图4.5-2输入信号及其分段524.5FFT算法的应用x[n]和h[n]的线性卷积为其中53图4.5-3重叠相加法示意图544.5FFT算法的应用重叠相加法用FFT实现的步骤，1.h[n]补零，至N点，即：2.将x[n]分段，第i段xi[n]补零，至N点，3.分别求出xi[n]和h[n]的N点DFT，由FFT算法实现

5.N点IDFT，由IFFT算法实现，6.重叠部分相加：4.554.5FFT算法的应用重叠保留法仍将x[n]分为长N1的段xi[n]，不同点在于，不在末端补零，而是在每一段序列前端补上前一段序列的(N2-1)点，组成(N1

+N2-1)点的序列。第一段的数据前应该补上(N2-1)个零值点。

一个(N1+N2-1

)点的序列与一个N2点的序列做(N=

N1+N2-1)点的圆周卷积时，其结果中的前(N2-1)个点是混叠部分，而其余点与线性卷积相同。由此重叠保留法即将输入段xi[n]和h[n]的圆周卷积舍掉前(N2-1)个点，将各相邻段留下来的样本衔接起来，就构成了最终的输出。56图4.5-5重叠保留法示意图574.6FFT的MATLAB实现Matlab为计算离散快速傅里叶变换，提供了一系列丰富的数学函数，主要有fft，ifft，fft2，ifft2，fftn，ifftn和fftshift，ifftshift等。例4.6-1已知：

和。试用Matalb实现由DFT计算两个序列的循环卷积，并讨论什么情况下，可以得到线性卷积结果。解：线性卷积584.6FFT的MATLAB实现x1=[2,