数字信号处理-使用Python分析与实现 课件 第4章 快速傅里叶变换

1第4章快速傅里叶变换李蓉艳同济大学电子与信息工程学院2024年12月第4章快速傅里叶变换2快速傅里叶变换4.1DFT计算量4.2时间抽取FFT加法次数乘法次数WN的性质4.3频率抽取FFT4.7线性调频z变换按时间奇偶分组蝶形先复乘后加减抽样频率频率分辨率信号时间长度4.6FFT的应用FFT计算卷积和相关重叠相加法离散频率值逼近模拟信号频谱信号流图特点乘法和加法次数按频率奇偶分组蝶形先加减后复乘信号流图特点乘法和加法次数重叠保留法4.7离散余弦变换频谱分析DCT原理DCT的计算本章重点-FFT的应用3快速傅里叶变换（FastFourierTransform,FFT）是一种高效计算离散傅里叶变换（DFT）的算法。它通过巧妙的数学分解，降低了DFT的计算复杂度，极大提升了处理大规模数据的效率。熟练掌握使用FFT进行卷积和相关计算的方法，熟练掌握利用FFT进行频谱分析的方法。理解线性调频z变换和离散余弦变换的原理，以及与DFT的关系。44.1DFT的计算量

复数乘法复数加法

实数乘法实数加法一次复乘42一次复加25

基2FFT算法：时间抽取（DecimationInTime，DIT）频率抽取（DecimationInFrequency，DIF）64.2时间抽取基2FFT算法

7

令4.2时间抽取基2FFT算法

8

4.2时间抽取基2FFT算法98点DFT分解为两个4点DFT，再分解为四个2点的DFT

4.2时间抽取基2FFT算法10算法特点

在编程时，可以将每级蝶形单元的输出仍放在输入数组中。同址运算

4.2时间抽取基2FFT算法113.输入倒位序，输出自然顺序

二进制倒位序

二进制

4.2时间抽取基2FFT算法1283264128256512102420486410244096163846553626214410485764194304128019244810242304512011264DFT乘法次数/FFT乘法次数5.3312.821.3336.5764113.78204.8372.36

4.DIT-FFT和DFT运算量比较每个蝶形有1次复数乘法和2次复数加法

共有复数乘法次数

共有复数加法次数

4.2时间抽取基2FFT算法135.其他DIT-FFT的运算结构对信号流图来说，只要保持各节点所连的支路及其传输系数不变，则不论节点位置在同一列中如何排列，所得流图都是等效的，因而可有等效的DIT-FFT流图结构。按时间抽选，输入输出皆为自然顺序的FFT流图4.2时间抽取基2FFT算法14按时间抽选，各级具有相同几何形状，输入自然顺序，输出倒位序的FFT流图按时间抽选，各级具有相同几何形状，输入自然顺序，输出倒位序的FFT流图4.2时间抽取基2FFT算法154.3频率抽取基2FFT算法

16

令

DIF的蝶形运算单元4.3频率抽取基2FFT算法17则

继续分解下去，直到最终分解为两点的DFT。4.3频率抽取基2FFT算法18按频率抽选的8点FFT运算流图4.3频率抽取基2FFT算法19DIF的算法特点：

DIF与DIT对比

204.4离散傅里叶逆变换的快速算法

DFT正变换和逆变换运算结构相似

21

因此

计算步骤:4.4离散傅里叶逆变换的快速算法22

则有

计算步骤:

4.4离散傅里叶逆变换的快速算法23*4.5基4FFT算法4.5.1时间抽取基4FFT

24

继续抽取直到变成4点的DFT为止。

在嵌入式系统中，一般提供基2FFT算法，如果计算速度不满足要求，可以采用基4FFT算法。每个基4蝶形运算需要

3次复数乘法

算法类型复数乘法次数复数加法次数基2FFT基4FFT*4.5基4FFT算法254.5.2频率抽取基4FFT

分别令

有

把一个16点的DFT分解为四个4点的DFT；

264.6线性卷积的FFT算法

用FFT线性卷积的步骤：

27当一个序列长度远远大于另一个短序列长度的情况对长序列进行分段，每一段分别与短序列进行卷积，再进行组合得到卷积结果。4.6.1

重叠相加法

28

4.6.1

重叠相加法29

304.6.2重叠保留法

31

4.6.2重叠保留法32

334.7线性相关的FFT算法利用圆周相关定理求线性相关

344.8线性调频z变换需要对某一段频带密集采样；有时需要对非单位圆上进行取样；只需要计算某一段频带内的频谱值。线性调频z变换（ChirpZ-Transform,CZT）：采用螺旋线取样计算更大范围的z变换采样值适合需要特殊取样的情况输入序列个数和输出序列数可以不相等DFT不适合的情况：35

CZT算法原理

36CZT计算公式

37

4.8线性调频z变换384.8.3使用FFT计算线性调频z变换

394.9离散余弦变换离散余弦变换（DiscreteCosineTransform,DCT）是DFT的一种特殊形式。广泛应用于语音和图像信号压缩。

镜像扩展

DFT

40

离散余弦变换公式

4.9离散余弦变换414.9.2DCT的矩阵计算

DCT写成矩阵形式

42求矩阵逆运算可以得到逆DCT

4.9.2DCT的矩阵计算43离散余弦逆变换公式为

序列分解为不同频率的余弦信号之和。DCT只使用了余弦分量，而DFT以复数的形式同时使用余弦和正弦分量。

4.9离散余弦变换44

45

将DFT和DCT的一部分数值赋零值，然后恢复原序列，可以看到DCT恢复的信号更接近原序列，说明DCT具有更好的能量压缩特性，