第5章-快速傅里叶变换课件

5.1减少DFT运算量的基本途径5.2按时间抽取（DIT）的基-2FFT算法5.3按频率抽取（DIF）的基-2FFT算法返回到本章向导5.4离散傅里叶反变换（IDFT）的快速算法第5章快速傅里叶变换5.5FFT实例分析5.1减少DFT运算量的基本途径5、快速傅立叶变换

1.问题的提出

返回到本节向导

其DFT变换对为：DFT和IDFT运算的差别：相差一个常数1/N

；对N

点有限长序列；旋转因子的指数符号不同；所以我们只分析DFT的运算量；5.1减少DFT运算量的基本途径5、快速傅立叶变换

1.问题的提出

返回到本节向导

结果：采用FFT算法计算DFT；计算每一个需要

N

次复数乘法和次复数加法；由于是N点序列；需要次复数乘法和次复数加法；在

N

值较大时，运算速度将大幅度提高！因此直接计算整个DFT需要N2次复数乘法和次复数加法；当

时，直接计算DFT的运算量为N2数量级！5.1减少DFT运算量的基本途径5.快速傅立叶变换

1.问题的提出

返回到本节向导

一方面可以将某些项合并；

直接计算DFT和采用基2FFT计算DFT的运算量比较

：112645120230410244481928032124194304104857626211465536163844096102425664N2204810245122561286432168N2.减少运算量的基本途径在DFT运算中，利用旋转因子的性质：另一方面可以不断地将长序列分解为短序列的组合，用短序列的

DFT

计算来代替长序列

DFT；5.1减少DFT运算量的基本途径5快速傅立叶变换返回到本节向导由于直接计算DFT的运算量与序列长度N的平方（N2）成正比，这样显然可以减少运算量；

2.减少运算量的基本途径旋转因子的主要性质为：⑴周期性：⑵对称性：⑶可约性：由此可得：5.1减少DFT运算量的基本途径5快速傅立叶变换返回到本节向导FFT算法在这一思路基础上发展而成；

2.减少运算量的基本途径分为：按频率抽取（DIF——Decimation-In-Frequency）法；按时间抽取（DIT——Decimation-In-Time）法：其中：基-2FFT是最基本的FFT算法，它要求FFT的点数N=2L（L为正整数）；如果序列长度不满足这一条件，需要用后补零值点的方法来补齐。5快速傅立叶变换返回到本节向导1.基本原理则的DFT转化为：5.2按时间抽取的基-2FFT算法5快速傅立叶变换返回到本节向导1.基本原理由于是N点DFT，因此前式只表示出了的前一半值；

的后一半值可以表示为：这样就将N点DFT分解为两个N/2点的DFT！只要求出区间的和；

就可以求出区间的全部的值；5.2按时间抽取的基-2FFT算法5.2按时间抽取的基-2FFT算法5快速傅立叶变换返回到本节向导是在时域将序列逐次分解为长度减半的奇序号子序列和偶序号子序列，用子序列的DFT来实现整个序列DFT；1.基本原理N

点有限长序列，首先按奇、偶序号将分解为两个长度为的子序列：5快速傅立叶变换返回到本节向导1.基本原理该式的运算可以用蝶形运算信号流图符号表示；

即：可以看出，要完成一个蝶形运算，需要一次复数乘法和两次复数加法。5.2按时间抽取的基-2FFT算法5快速傅立叶变换返回到本节向导1.基本原理经过第一次分解：DFT的运算量基本上减少了一半；

5.2按时间抽取的基-2FFT算法第一次分解：8点DFT分解为两个4点DFT5快速傅立叶变换返回到本节向导1.基本原理

经过第二次分解：一个N点DFT分解为四个N/4点DFT，运算量进一步减半；对于剩下的两点DFT有：5.2按时间抽取的基-2FFT算法第二次分解：4点DFT分解为两个2点DFT5快速傅立叶变换返回到本节向导1.基本原理

表明：2点DFT也可以表示为一个蝶形运算；即：N点DFT的最后一次分解是将N/2个2点DFT分解为N个1点DFT；2点DFT分解为两个1点DFT5.2按时间抽取的基-2FFT算法5快速傅立叶变换返回到本节向导1.基本原理

一个N=8点的按时间抽取基-2FFT运算流图如图：5.2按时间抽取的基-2FFT算法5快速傅立叶变换返回到本节向导2.算法规律

⑴“级”的概念时域序列的分解过程为：先将N点DFT分解为两个N/2点DFT；再分解为四个N/4点DFT；进而是八个N/8点DFT，直至N/2个2点DFT；最后是N个1点DFT；每分解一次称为一“级”运算！对于点DFT，共有级运算；例如N=8时，8点DFT分成3级从左到右依次为第1级、第2级和第3级，5.2按时间抽取的基-2FFT算法5快速傅立叶变换返回到本节向导2.算法规律

⑵蝶形单元DFT各级的运算都是由蝶形运算构成的；每一级中都含有N/2个蝶形单元；每个蝶形单元有两个节点（i，j）参加运算；前一级（第m-1级）蝶形单元的输出是后一级（第m级）蝶形单元的输入；每一个蝶形单元的运算需要一次复数乘法和两次复数加法；

完成级蝶形运算共需要的运算量为：复数乘法：复数加法：5.2按时间抽取的基-2FFT算法5快速傅立叶变换返回到本节向导2.算法规律

⑶蝶形单元的节点距离每级中蝶形单元两节点（i，j）间的距离不等；第1级蝶形单元的节点距离为1；第2级蝶形单元的节点距离为2；第3级为4；第m（m=1,2,…,L）级蝶形单元的节点距离为；即：……，依此类推；5.2按时间抽取的基-2FFT算法5快速傅立叶变换2.算法规律

⑷“组”的概念每一级的N/2个蝶形单元通常分为若干组；……，依此类推；同级的每一组都具有相同的结构和分布；⑸旋转因子的分布第L级（即第一次分解）蝶形单元的旋转因子为；第L-1级（即第二次分解）为；返回到本节向导第m级蝶形单元的旋转因子为：

5.2按时间抽取的基-2FFT算法5快速傅立叶变换返回到本节向导2.算法规律

⑹倒位序

，

变换后的输出序列按照自然顺序排列；但输入序列却已不再是自然顺序；原因：由于按奇、偶序号不断分解而产生的；5.2按时间抽取的基-2FFT算法5快速傅立叶变换返回到本节向导

⑹倒位序

，

——就是将自然顺序的二进制位倒置；将输入序列的这种排列顺序称为倒位序；

即将倒置为；用二进制树状图来描述5.2按时间抽取的基-2FFT算法5快速傅立叶变换

⑺原位运算整个运算过程中，每一级蝶形运算的输入和输出在运算前后都存储在同一组存储单元中，直至最后输出；返回到本节向导每一级的蝶形运算有N个节点（从第一行开始依次为节点0、1、……、N-1）和N/2个蝶形单元；每两个节点只参加一个蝶形单元的运算；而与同级的其它蝶形单元无关；中间不需要占用其它存储单元！原位运算特点：以节省存储单元，降低设备成本！5.2按时间抽取的基-2FFT算法5快速傅立叶变换

⑺原位运算返回到本节向导按自然顺序存放在存储单元中的输入序列值，只要将某些单元的内容对调即可得到按倒位序存储的输入序列值；倒位序的变址处理5.2按时间抽取的基-2FFT算法补充：按时间抽取的FFT算法的其他形式流图对于任何流图，只要保持各节点所连的支路及传输系数不变，则不论节点位置怎么排列所得流图总是等效的，所得最后结果都是x(n)的DFT的正确结果，只是数据的提取和存放的次序不同而已。这样就可得到按时间抽取的FFT算法的若干其他形式流图。和x(4)水平相连的所有节点和x(1)水平相连的所有节点位置对调，再将和x(6)水平相连的所有节点与和x(3)水平相连的所有节点对调，其余诸节点保持不变，可得下图的流图。5快速傅立叶变换5快速傅立叶变换①数据存放的方式不同，原图是输入倒位序、输出自然顺序，变换后是输入自然顺序、输出倒位序；②取用系数的顺序不同，原图的最后一列是按 的顺序取用系数，且其前一列所用系数是后一列所用系数中具有偶数幂的那些系数（例如 ）；变换后是最后一列是按的顺序取用系数，且其前一列所用系数是后一列所用系数的前一半，5快速傅立叶变换5快速傅立叶变换返回到本节向导1.基本原理

N

点有限长序列，将输入序列按n的顺序分为前后两部分：注意：式中用的是而不是；所以仍是N点DFT！5.3按频率抽取的基-2FFT算法5快速傅立叶变换返回到本节向导1.基本原理

由于；所以；有：当k为偶数时；当k为奇数时；将按k为奇偶分解为两个N/2点子序列，即：代入5.3按频率抽取的基-2FFT算法5快速傅立叶变换返回到本节向导1.基本原理

令：显然，和均为N/2点序列；代入5.3按频率抽取的基-2FFT算法5快速傅立叶变换返回到本节向导1.基本原理

其运算可以用蝶形运算信号流图符号表示为：上页得到的公式按频率抽取的蝶形运算信号流图符号5.3按频率抽取的基-2FFT算法5快速傅立叶变换把一个N点DFT按k的奇偶分解为两个N/2点的DFT了。

N=8时，图（1）按频率抽取的第一次分解5快速傅立叶变换与时间抽取法的推导过程一样，由于N=2M，N/2仍是一个偶数，因而可以将每个N/2点DFT的输出再分解为偶数组与奇数组，这就将N/2点DFT进一步分解为两个N/4点DFT。这两个N/4点DFT的输入也是先将N/2点DFT的输入上下对半分开后通过蝶形运算而形成的，图（2）示出了这一步分解的过程。按频率抽取的第二次分解5快速傅立叶变换按频率抽取的第三次分解5快速傅立叶变换5快速傅立叶变换返回到本节向导2.算法规律

按频率抽取基-2FFT算法和按时间抽取基-2FFT算法类似；

共有级运算；每级有N/2个蝶形单元；所以：两种算法的运算量相同！——也都是原位运算！5.3按频率抽取的基-2FFT算法DIT-FFT与DIF-FFT的基本蝶形单元之间、FFT运算流图之间都是转置的关系；两种FFT算法的运算量相同，运算过程也类似，在实际应用中可以任意选用5快速傅立叶变换返回到本节向导由离散傅立叶变换的定义：

5.4离散傅里叶反变换（IDFT）的快速算法就可以按照前面的DIT-FFT和DIF-FFT来实现IDFT的快速运算，即IFFT算法；

正变换：反变换：只要将DFT运算中的系数换成最后再乘以常数1/N

；但用这种方法得到的IFFT算法需要稍稍改动FFT的程序和系数！5快速傅立叶变换返回到本节向导为了不改变FFT程序就可以计算IFFT；：

5.4离散傅里叶反变换（IDFT）的快速算法

将IDFT表达式两边取共轭：则有：表明：只要对取共轭作为输入；就可以直接利用FFT程序，最后将输出再取一次共轭，并乘以常数1/N即可得到序列！5.5.1用DFT对连续时间信号进行频谱分析

1.用

DFT

近似分析连续时间信号的频谱返回到本章向导其频谱为：

设连续时间非周期信号信号；

⑴对进行时域抽样

得到序列

成立！⑵对截取N点得有限长序列；

5.5.1用DFT对连续时间信号进行频谱分析

1.用

DFT

近似分析连续时间信号的频谱返回到本章向导⑵对截取N点得有限长序列；

近似为⑶时域的离散化导致频域周期延拓

近似为表明：若；

则用分析只差一个常数；

5.5.1用DFT对连续时间信号进行频谱分析

2.用IDFT近似分析连续时间信号返回到本章向导在已知频谱的情况下；

可以用IDFT近似分析其时域信号；

分析过程与前面类似：

①以（或）为间隔对频谱进行等间隔抽样并截取N点，得有限长序列：

（

则IDFT能够分析的频谱的最高频率为：（或）；

5.5.1用DFT对连续时间信号进行频谱分析

2.用IDFT近似分析连续时间信号返回到本章向导

时域信号近似为：②频域离散化导致时域周期延拓延拓周期

对时域信号的抽样间隔为：

5.5.1用DFT对连续时间信号进行频谱分析因为DFT对应的数字域频率间隔为Δω=2π/N，且模拟频率Ω和数字频率ω间的关系为ω=ΩΤ，其中Ω=2πf。所以，离散的频率函数第k点对应的模拟频率为:数字域频率间隔Δω=2π/N对应的模拟域谱线间距为谱线间距，又称频谱分辨率（单位：Hz）。F是指可分辨两频率的最小间距。如设某频谱分析的F=5Hz，那么信号中频率相差小于5Hz的两个频率分量在此频谱图中就分辨不出来。5.5.1用DFT对连续时间信号进行频谱分析F为谱线间距，又称频谱分辨率（单位：Hz）。T为采样时间间隔（单位：s）；fs为采样频率（单位：Hz）；tp为截取连续时间信号的样本长度（记录长度，单位：s）；在实际应用中,要根据信号最高频率fh和频谱分辨率F的要求，来确定T、tp和N的大小。5.5.1用DFT对连续时间信号进行频谱分析（1）首先，由采样定理，为保证采样信号不失真，fs≥2fh(fh为信号频率的最高频率分量，也就是前置低通滤波器阻带的截止频率)，即应使采样周期T满足（2）由频谱分辨率F和T确定N,（3）最后由N,T确定最小记录长度，tp=NT。例：有一频谱分析用的FFT处理器，其采样点数必须是2的整数幂，假定没有采用任何特殊的数据处理措施，已给条件为:①频率分辨率≤10Hz;②信号最高频率≤4kHz。试确定以下参量：

(1)最小记录长度tp；

(2)最大采样间隔T（即最小采样频率）；

(3)在一个记录中的最少点数N。

5.5.1用DFT对连续时间信号进行频谱分析解：(1)由分辨率的要求确定最小长度tp

(2)从信号的最高频率确定最大可能的采样间隔T（即最小采样频率fs=1/T）。(3)最小记录点数N应满足

5.5.1用DFT对连续时间信号进行频谱分析

3.用DFT近似分析连续时间信号频谱时出现的问题返回到本章向导

⑴混叠失真

对连续时间信号进行频谱分析时，为了避免混叠失真，必须满足抽样定理；

一般应取抽样频率

对频谱很宽或无限宽的连续时间信号，一般采用预滤波法；

在抽样前滤除不必要的的高频分量！

以避免抽样频率过高实现困难或频谱混叠！在用DFT对信号频谱进行近似分析时，它所能够分析的信号频谱的最高频率和频率分辨力之间存在着矛盾；

5.5.1用DFT对连续时间信号进行频谱分析

3.用DFT近似分析连续时间信号频谱时出现的问题返回到本章向导

⑴混叠失真

因此，必须兼顾最高频率和频率分辨力；其唯一办法就是增加记录长度的抽样点数；⑵频谱泄漏用DFT分析连续时间信号持续时间很长或无限长的频谱时，必须进行信号的截取！即要满足：

以得到有限长得到N点有限长序列

5.5.1用DFT对连续时间信号进行频谱分析

返回到本章向导

由序列傅里叶变换的卷积和定理可知，时域的乘积对应于频域的卷积和，⑵频谱泄漏频谱的泄漏有可能使得最高频率超过奈奎斯特频率，从而造成混叠失真；在时域相当：又由于的频谱为Sa()函数而且无限长；的频谱相对于原信号频谱出现拖尾，造成频谱扩散；

——频谱泄漏一般采用变化缓慢的窗函数（如升余弦函数等）取代矩形窗函数来进行截取！5.5.1用DFT对连续时间信号进行频谱分析

返回到本章向导

DFT计算的频谱是离散的；⑶栅栏效应就好象通过一个“栅栏”看景象一样；而相邻谱线之间的频谱无从知晓！减小栅栏效应的方法：谱线只限制在基频（频域抽样间隔）的整数倍处；

这就不能反映原信号的全部频谱特性！这种现象称为栅栏效应

增加频域的抽样点数，减小抽样间隔，使谱线变密

5.5.1用DFT对连续时间信号进行频谱分析fs=400;T=1/fs;To=0.04;N=To*fs;设：分别选择0.04S、0.16S和0.32S三种截取长度，用DFT对连续时间信号作频谱分析的程序为：

N1=[N,4*N,8*N];st=['|X1(jf)|';'|X4(jf)|';'|X8(jf)|'];form=1:3;n=1:N1(m);xn=cos(200*pi*n*T)+sin(100*pi*n*T);Xk=fft(xn,4096);fk=[0:4095]/4096/T;subplot(3,2,2*m-1);返回到本章向导5.5.1用DFT对连续时间信号进行频谱分析ylabel(st(m,:));ifm==1title('矩形窗截取');endend

plot(fk,abs(Xk)/max(abs(Xk)));程序的执行结果如图

5.5.2线性卷积和的分段计算法返回到本节向导

问题的提出：为了能用DFT计算线性卷积和，需要将两序列

和

后补零值点加长为；

当和的值相差很大时，这不仅加大了计算量，而且时延也可能不满足处理要求

；

解决的方法：采用分段卷积和的计算方法

基本思路为：先将长序列分段，使各分段的长度与短序列相近；

然后分别计算各分段与短序列的线性卷积和；最后按照一定的方式将各分段的线性卷积和组合起来；

5.5.2线性卷积和的分段计算法返回到本节向导

就可以得到原长序列与短序列的线性卷积和；每段长度为M点，M与N的数量级相同；1.重叠相加法假设共分r段（最后一段若不足M点，可以后补零值点来补齐），即：

设：为N点有限长序列；

为L0点有限长序列；

且有：现将均匀分段；

5.5.2线性卷积和的分段计算法返回到本节向导

表明：首先要计算分段卷积和，然后把各分段卷积和的结果相加；这种分段卷积法也因此称为重叠相加法则与的线性卷积和为：分段卷积和是点有限长序