离散傅里叶变换与快速傅里叶变换课件

2023/8/21大连理工大学1PartII数字信号处理大连理工大学硕士研究生校管课程信号处理与数据分析电子信息与电气工程学部邱天爽2015年11月2023/8/5大连理工大学1PartII大连理工大学硕士2023/8/21大连理工大学2第5章离散傅里叶变换与快速傅里叶变换大连理工大学硕士研究生校管课程信号处理与数据分析电子信息与电气工程学部邱天爽2015年11月2023/8/5大连理工大学2第5章大连理工大学硕士研究生校

内容概要§5.1引言§5.2离散傅里叶变换（DFT）§5.3DFT理论与应用中若干问题§5.4二维傅里叶变换简介§5.5快速傅里叶变换（FFT）§5.6FFT的主要应用内容概要§5.1引言2023/8/21大连理工大学4§5.1引言2023/8/5大连理工大学4§5.1引言2023/8/21大连理工大学5为什么要学习离散傅里叶变换（DFT）？数字信号处理，要求信号是数字化的，也希望信号的频谱或系统的频率响应也是数字化的。实际应用中的信号总是有限时宽的、且为非周期的。希望信号频谱也是有限频宽、且非周期的。考察前面介绍的4种傅里叶级数或傅里叶变换，没有任何一种能够满足这种需求。因此，发展新的傅里叶变换方法以适应数字信号处理实际应用的要求称为数字信号处理理论的一个重要任务。这就为DFT的发展提供了需求和动力。2023/8/5大连理工大学5为什么要学习离散傅里叶变换（D2023/8/21大连理工大学6§5.2离散傅里叶变换（DFT）2023/8/5大连理工大学6§5.2离散傅里叶变换（

5.2.1已有傅里叶变换的简要回顾（1）FS：连续、周期；离散、非周期；大连理工大学75.2.1已有傅里叶变换的简要回顾（1）FS：2023/8/21大连理工大学8（2）DFS：离散、周期；离散、周期；（3）FT：连续、非周期；连续、非周期；

2023/8/5大连理工大学8（2）DFS：离散、周2023/8/21大连理工大学9（4）DTFT：离散、非周期；连续、周期；

2023/8/5大连理工大学9（4）DTFT：离散、

5.2.2由DFS到DFT（1）DFT的导出与定义由上节分析，在已给出的4种傅里叶级数与变换中，只有DFS在时域和频域都是离散的，且均为周期性的。定义新符号：和分别表示周期性信号和频谱。定义矩形序列符号和为有限长序列和可以认为是周期性序列和的一个周期。大连理工大学105.2.2由DFS到DFT（1）DFT的导出与定义大连2023/8/21大连理工大学11再定义：式中，（或）表示对取余数（或对取余数）。这样，有：2023/8/5大连理工大学11再定义：2023/8/21大连理工大学12分析：注意到，在DFS中，时间序列是周期性的，周期为N。另一方面，周期为N的序列只有N点独立样本，其余的都重复。DFS中，实际上只用了的N点数据。这样，可以把N点长的非周期序列看成周期为N的序列的一个周期。

2023/8/5大连理工大学12分析：2023/8/21大连理工大学13离散傅里叶变换（DFT）【假设】设为有限长序列，点数为N，可将其看作周期为N的周期序列的一个周期；而把看作是的周期延拓，即：

称是的主值序列。记为：表示“对取余数”，或对取模值。2023/8/5大连理工大学13离散傅里叶变换（DFT）2023/8/21大连理工大学14【例】设为周期的序列，求两数对的余数。【解】因为：，故：因为：，故：这样：2023/8/5大连理工大学14【例】2023/8/21大连理工大学15DFT的定义：式中，DFS：离散、非周期；离散、非周期2023/8/5大连理工大学15DFT的定义：DFS：离散、2023/8/21大连理工大学16利用加窗函数则DFT定义式改写为：即DFT是DFS的一个周期。2023/8/5大连理工大学16利用加窗函数2023/8/21大连理工大学17（2）DFT的图形解释2023/8/5大连理工大学17（2）DFT的图形解释2023/8/21大连理工大学18说明（参考上页图）(a)长度为T的连续时间信号，其频谱为。(b)时域采样信号：，其频谱仍为同周期脉冲序列。(c)采样，连续时间信号离散化，频谱周期性延拓。(d)频域采样信号。(e)频域采样的结果，频谱离散化，信号周期性延拓。

2023/8/5大连理工大学18说明（参考上页图）2023/8/21大连理工大学19DFT与DTFT及z变换的关系设长为N点，则：其中：

定义在整个z平面；仅在z平面单位圆上取值；

是单位圆上N个等间距点上取值

是的主值周期。2023/8/5大连理工大学19DFT与DTFT及z变换的关2023/8/21大连理工大学20【例5.1】2023/8/5大连理工大学20【例5.1】

5.2.3离散傅里叶变换的性质DFT的性质大连理工大学215.2.3离散傅里叶变换的性质DFT的性质大连理工大学2023/8/21大连理工大学22DFT的性质（续）2023/8/5大连理工大学22DFT的性质（续）2023/8/21大连理工大学23【线性性质】若：则：【序列的圆周位移性质】将延拓为，将位移，取主值区间上的序列值。即：圆周位移：若：则：2023/8/5大连理工大学23【线性性质】2023/8/21大连理工大学24【圆周位移的图形解释】左移=顺时针旋转右移=逆时针旋转2023/8/5大连理工大学24【圆周位移的图形解释】左移=2023/8/21大连理工大学25【对偶性】若：则：【帕色伐尔定理】若：则：2023/8/5大连理工大学25【对偶性】2023/8/21大连理工大学26【圆周共轭对称性】若：则：2023/8/5大连理工大学26【圆周共轭对称性】2023/8/21大连理工大学27【满足圆周共轭对称性的序列】2023/8/5大连理工大学27【满足圆周共轭对称性的序列】2023/8/21大连理工大学28【圆周卷积和性质】若：若：则：2023/8/5大连理工大学28【圆周卷积和性质】2023/8/21大连理工大学29【圆周卷积和图示】把主值周期左边一个周期的数据反折到主值区间。右移，最右边的移至最左边2023/8/5大连理工大学29【圆周卷积和图示】2023/8/21大连理工大学30【圆周相关性质】若：若：则：2023/8/5大连理工大学30【圆周相关性质】2023/8/21大连理工大学31有限长序列的线性卷积和圆周卷积（1）线性卷积非零值区间：，其中和分别为两序列的长度。其中，的非0区间为；的非0区间为线性卷积的长度：

2023/8/5大连理工大学31有限长序列的线性卷积和圆周卷2023/8/21大连理工大学32（2）圆周卷积将看成L点序列，，不足补0.则结论：L点圆周卷积是线性卷积以L为周期的周期延拓序列的主值序列。

若，则L点圆周卷积能代表线性卷积。

2023/8/5大连理工大学32（2）圆周卷积2023/8/21大连理工大学33离散傅里叶变换的逆变换逆变换与正变换的区别：有系数指数有负号具体应用时：2023/8/5大连理工大学33离散傅里叶变换的逆变换2023/8/21大连理工大学34§5.3DFT理论与应用中若干问题2023/8/5大连理工大学34§5.3DFT理论与应2023/8/21大连理工大学35采样定理：若采样定理不满足，则产生混叠，即频率响应周期延拓分量互相重叠。

若信号的频谱无限宽，则需要抗混叠滤波器进行预处理。可选占信号能量98%左右的频带宽度的作为信号的最高频率，从而进一步确定采样频率。

5.3.1频率混叠问题2023/8/5大连理工大学35采样定理：5.3.1频率2023/8/21大连理工大学36频谱泄漏的含义：截断信号的能量扩散到无穷宽的频带中去，称为频谱泄漏。频谱泄漏的原因：在实际应用中，观测信号总是要限制在一定的时间范围内。这相当于信号与矩形窗函数相乘。时域乘积对应于频域卷积，卷积的结果使的频谱发生了变化。

5.3.2频谱泄漏问题2023/8/5大连理工大学36频谱泄漏的含义：截断信号的能2023/8/21大连理工大学37频谱泄漏的图示：2023/8/5大连理工大学37频谱泄漏的图示：2023/8/21大连理工大学38频谱泄漏的危害泄漏的危害：使频谱的分辨率下降；在频谱中引入虚假的频率分量（由窗引起）。减小泄漏的方法：

取更长的数据，即增加窗宽；数据不要突然截断，即不要矩形窗，加各种缓变窗，使窗旁瓣的能量更小。

2023/8/5大连理工大学38频谱泄漏的危害2023/8/21大连理工大学39栅栏效应：因DFT的谱是限制在离散点上的频谱，是一种限制为基频整数倍处的谱，而不是连续的频谱。就像通过“栅栏”观看景象一样，只能在离散点处看到真实景象，称为栅栏效应。

5.3.3栅栏效应2023/8/5大连理工大学39栅栏效应：因DFT的谱是限制2023/8/21大连理工大学40减小栅栏效应的方法增加频域采样点数N；在不改变时域数据的情况下，补0；频率采样为，随着N增大，导致采样点更近，谱线更密。2023/8/5大连理工大学40减小栅栏效应的方法2023/8/21大连理工大学41

分辨率：分辨率有两种常见的含义，其一是指将相邻的两个信号峰或频谱峰分辨开来的能力；其二是指离散信号或离散频谱相邻数据样本间隔的大小。时间分辨率：通过时窗所看到时间的宽度；频率分辨率：通过频窗所看到频率的宽度；或能将信号中两个靠的很近的频谱分开的能力。5.3.4频率分辨率及DFT参数选择2023/8/5大连理工大学41分辨率：5.3.4频率2023/8/21大连理工大学42FT与DFT中的频率分辨率（1）FT中的频率分辨率设信号，时长为T秒，其傅里叶变换的频率分辨率为：2023/8/5大连理工大学42FT与DFT中的频率分辨率2023/8/21大连理工大学43（2）DTFT中的频率分辨率2023/8/5大连理工大学43（2）DTFT中的频率分辨率2023/8/21大连理工大学44（3）DFT中的频率分辨率2023/8/5大连理工大学44（3）DFT中的频率分辨率2023/8/21大连理工大学45总之由以上讨论可知，频率分辨率的概念是与傅里叶变换紧密联系的。频率分辨率的大小反比于信号的实际长度。在数据长度相同的条件下，使用不同的窗函数会在频率的分辨率和频率泄漏之间做不同的取舍。另一方面，通过发展新的信号处理算法也可能进一步改善信号的频率分辨率，我们将在后面章节介绍的现代谱估计方法，由于隐含了对有限数据的外推，可以突破傅里叶变换关于频率分辨率的限制，得到更高的频率分辨率。2023/8/5大连理工大学45总之2023/8/21大连理工大学46举例【例5.3】设的最高频率，采样频率设信号时长，即采样得的信号点数为256点。对做DFT时，。【解】：2023/8/5大连理工大学46举例2023/8/21大连理工大学47【例5.4】若：，且：问：用DFT求频谱时，可否分辨这三个频率。【解】：因：故：不能分辨，可以分辨。若加长数据，即令N=1024，TL=1024×0.1=102.4s

则：故：可以分辨。【程序见书稿】2023/8/5大连理工大学47【例5.4】2023/8/21大连理工大学48结果（a）数据长度为128；（b）数据长度为256；（c）数据长度为512.2023/8/5大连理工大学48结果2023/8/21大连理工大学49在应用中需要注意的问题：若信号最高频率为，则需满足：根据需要的来选择数据长度N：对应的时间长度：2023/8/5大连理工大学49在应用中需要注意的问题：2023/8/21大连理工大学50信号补0的作用：补零不能提高分辨率，因为补零未对原始信号增加新信息；但补零可使数据N为2的整次幂，以便FFT的使用；补零可对插值；插值有助于缓解频谱泄漏。5.3.5信号补0问题2023/8/5大连理工大学50信号补0的作用：5.3.52023/8/21大连理工大学51【例5.5】（a）未补零时的波形图和频谱图（b）补零后的波形图和频谱图2023/8/5大连理工大学51【例5.5】2023/8/21大连理工大学52应用举例【例5.5A】：补0的效果三个信号频率：2023/8/5大连理工大学52应用举例2023/8/21大连理工大学53【例5.5A续】由图(a)，不能看出几个频率；由图(b)，补N个0，仍不明显；由图(c)，补7N个0，效果比较显著，基本可以分辨三个信号频率；由图(d)，补29N个0，效果明显。2023/8/5大连理工大学53【例5.5A续】2023/8/21大连理工大学54信号的时宽与频宽不可能同时缩小，也不可能同时扩大（例：FT的比例变换性质）；信号的时宽与频宽也不能同时为有限值（例：矩形）；时宽和频宽的测量方法：方法1：要求：是实对称、非递增的信号。有：

方法2：

不定原理：uncertaintyprinciple5.3.6信号的时宽与频宽问题2023/8/5大连理工大学54信号的时宽与频宽不可能同时缩2023/8/21大连理工大学55§5.4二维傅里叶变换简介2023/8/5大连理工大学55§5.4二维傅里叶变换2023/8/21大连理工大学56单位脉冲序列单位阶跃序列指数序列5.4.1常用二维离散序列2023/8/5大连理工大学56单位脉冲序列5.4.1常2023/8/21大连理工大学57（1）二维z变换定义：5.4.2二维傅里叶变换的定义2023/8/5大连理工大学57（1）二维z变换定义：5.42023/8/21大连理工大学58（1）二维离散时间傅里叶变换定义：2023/8/5大连理工大学58（1）二维离散时间傅里叶变换2023/8/21大连理工大学59线性性质时域卷积性质时域乘积性质时移性质频移性质帕斯瓦尔定理可分离性质5.4.3二维DTFT的主要性质2023/8/5大连理工大学59线性性质5.4.3二维D2023/8/21大连理工大学60（1）二维DFT的定义：5.4.4二维离散傅里叶变换2023/8/5大连理工大学60（1）二维DFT的定义：5.2023/8/21大连理工大学61（2）2D-DFT与2D-DTFT的关系（3）二维频率的概念2023/8/5大连理工大学61（2）2D-DFT与2D-D2023/8/21大连理工大学62【例5.6】5.4.52D-DFT应用举例2023/8/5大连理工大学62【例5.6】5.4.522023/8/21大连理工大学63结果2023/8/5大连理工大学63结果2023/8/21大连理工大学64【例5.8】

波形图频谱图2023/8/5大连理工大学64【例5.8】2023/8/21大连理工大学65§5.5快速傅里叶变换（FFT）2023/8/5大连理工大学65§5.5快速傅里叶变换2023/8/21大连理工大学66DFT解决了计算机处理时域/频域信号问题；但是，计算量为，若，则1965年，库利（J.W.Cooley）和图基（J.W.Kukey）首次提出了DFT的一种有效的快速算法，称为FFT。其计算量为，若，仅5120次。可以这样说，数字信号处理之所以得到今天这样广泛、迅速的发展，在很大程度上得益于FFT的出现和使用。5.5.1FFT的出现2023/8/5大连理工大学66DFT解决了计算机处理时域/2023/8/21大连理工大学67（1）DFT计算量分析5.5.2DFT的问题及改进途径2023/8/5大连理工大学67（1）DFT计算量分析5.52023/8/21大连理工大学68（2）DFT的周期性、对称性和可约性

的共轭对称性的周期性

的可约性进一步地，可得以上特点显著减小计算量。2023/8/5大连理工大学68（2）DFT的周期性、对称性2023/8/21大连理工大学69（3）DFT的可改进性利用的对称性、周期性和可约性等特性，可以使DFT计算中的某些项合并，也可以将较长序列的DFT计算分解为较短序列的DFT计算，从而减小计算量。快速傅里叶变换（FFT）正是依据上述特性而提出和发展的。其基本算法可以分为两大类，即按时间抽选（decimation-in-time）法和按频率抽选（decimation-in-frequency）法。2023/8/5大连理工大学69（3）DFT的可改进性2023/8/21大连理工大学70（1）算法原理5.5.3时间抽取基2FFT算法2023/8/5大连理工大学70（1）算法原理5.5.32023/8/21大连理工大学71【算法原理】：设序列点数，为正整数。将先按的奇偶分成两组：

这样，可将DFT化为：

2023/8/5大连理工大学71【算法原理】：2023/8/21大连理工大学72按时间抽选的基2FFT算法（续）【算法原理】（续）：根据，上式表示为：其中和分别是和的点DFT。这样：2023/8/5大连理工大学72按时间抽选的基2FFT算法2023/8/21大连理工大学73按时间抽选的基2FFT算法（续2）【算法原理】（续2）：说明：一个点DFT已分解为两个点的DFT；再进行组合成点DFT（上页红色部分，前半段）。

再利用系数的周期性：则有：（蓝色部分，后半段）这样，前半段和后半段的数据都做了DFT。频谱的后半段与前半段相等。2023/8/5大连理工大学73按时间抽选的基2FFT算法2023/8/21大连理工大学74按时间抽选的基2FFT算法（续3）【算法原理】（续3）：再考虑性质：则前半段：后半段：即只要求出前半段和，就可以得到完整的，节省计算量。

2023/8/5大连理工大学74按时间抽选的基2FFT算法2023/8/21大连理工大学75按时间抽选的基2FFT算法（续4）【蝶形信号流图】：上述算法可用下面的蝶形流图表示。2023/8/5大连理工大学75按时间抽选的基2FFT算法2023/8/21大连理工大学76N=8的蝶形信号流图：2023/8/5大连理工大学76N=8的蝶形信号流图：2023/8/21大连理工大学77按时间抽选的基2FFT算法（续5）由于仍为偶数，还可以继续分解。将每个的子序列再按照奇部、偶部分解为两个子序列。例如：将分解如下：

这样：2023/8/5大连理工大学77按时间抽选的基2FFT算法（2023/8/21大连理工大学78按时间抽选的基2FFT算法（续6）这样：2023/8/5大连理工大学78按时间抽选的基2FFT算法（2023/8/21大连理工大学79按时间抽选的基2FFT算法（续6）对也可以继续分解，有：由2个N/4点DFT组合的N/2点DFT：2023/8/5大连理工大学79按时间抽选的基2FFT算法（2023/8/21大连理工大学80按时间抽选的基2FFT算法（续6）将系数统一为，则一个8点的DFT可以分解为4个N/4点DFT，如图。已知分解到2点数据为止。2023/8/5大连理工大学80按时间抽选的基2FFT算法（2023/8/21大连理工大学81【完整的8点FFT流图】

m=0m=1m=2

2023/8/5大连理工大学81【完整的8点FFT流图】2023/8/21大连理工大学82（2）算法特点分析【运算量分析】当数据长度，需要计算量：

复数乘法：复数加法：DFT与FFT计算量之比：2023/8/5大连理工大学82（2）算法特点分析2023/8/21大连理工大学83FFT与DFT计算量对比2023/8/5大连理工大学83FFT与DFT计算量对比2023/8/21大连理工大学84【“级”与“行”的概念】2023/8/5大连理工大学84【“级”与“行”的概念】2023/8/21大连理工大学85【蝶形运算单元与同址运算】原位计算（同址计算），节省存储空间。倒位序规律。好处是节省存储单元。2023/8/5大连理工大学85【蝶形运算单元与同址运算】2023/8/21大连理工大学86【“组”的概念】2023/8/5大连理工大学86【“组”的概念】2023/8/21大连理工大学87【蝶形运算两节点所在行的距离】2023/8/5大连理工大学87【蝶形运算两节点所在行的距离2023/8/21大连理工大学88【因子分布】2023/8/5大连理工大学88【因子分布】2023/8/21大连理工大学89【码位倒置问题】2023/8/5大连理工大学89【码位倒置问题】2023/8/21大连理工大学90【按时间抽选的FFT算法的其他形式流图】（略）FFT算法按时间抽取还有许多其他算法，请同学们自行参考相关书籍进行学习。2023/8/5大连理工大学90【按时间抽选的FFT算法的其2023/8/21大连理工大学91（1）算法原理设，把按奇偶分组，有：5.5.4频率抽取基2FFT算法继续依此分解，最后，有：2023/8/5大连理工大学91（1）算法原理5.5.42023/8/21大连理工大学92【按频率抽选的基2FFT算法流图】2023/8/5大连理工大学92【按频率抽选的基2FFT算法2023/8/21大连理工大学93【例5.9】利用MATLAB编程计算两个正弦信号之和再加上白噪声的FFT，然后求其反变换还原为原始信号。结果：2023/8/5大连理工大学93【例5.9】利用MATLAB2023/8/21大连理工大学94离散傅里叶变换（DFT）实际上是离散时间傅里叶变换（DTFT）的频率采样，是在z平面单位圆上的离散采样。一种与DFT不同的算法称为线性调频z变换（chirpz-transform，简称为CZT），可以计算单位圆上（或非单位圆上）任意一段圆弧上的傅里叶变换。5.5.5线性调频z变换2023/8/5大连理工大学94离散傅里叶变换（DFT）实际2023/8/21大连理工大学95CZT的特点CZT的作用类似于DFT的作用，可以将离散时间信号变换为CZT谱。与DFT和FFT不同，CZT的输入信号长度可以与输出谱的长度不同。CZT具有一定的频率细化的作用，因此经常用在短数据且高分辨率要求的场合。CZT的计算首先将z平面上任意螺线上的z变换采样值的计算、或特定情况下一段频率范围的DFT计算，转化成求线性卷积的运算，再利用FFT算法来快速计算线性卷积，从而得到CZT的结果。2023/8/5大连理工大学95CZT的特点2023/8/21大连理工大学96【例5.10】产生3个不同频率的正弦信号，将其叠加，利用MATLAB编程求混合信号的CZT和FFT。结果CZT可以较自由地选择频谱范围，且可以得到更为精细的频谱结构。2023/8/5大连理工大学96【例5.10】产生3个不同频2023/8/21大连理工大学97§5.6FFT的主要应用2023/8/5大连理工大学97§5.6FFT的主要应2023/8/21大连理工大学98（1）线性卷积与圆周卷积求解LTI系统输出的卷积是线性卷积：FFT给出的卷积是圆周卷积二者输出长度是不同的。故不能直接用FFT线性卷积。5.6.1线性卷积的FFT算法2023/8/5大连理工大学98（1）线性卷积与圆周卷积5.2023/8/21大连理工大学99利用FFT计算线性卷积【算法】设为N点数据，为M点系统。卷积：的点数为，对补0到点L。

用FFT计算卷积的步骤：

2023/8/5大连理工大学99利用FFT计算线性卷积2023/8/21大连理工大学100【计算量】卷积与快速卷积计算量的比较：卷积乘法次数：

FFT乘法次数：

通常，，则：。这时，，常采用分段卷积方法处理。83264128