05 第3章 离散傅里叶变换及其快速算法.pptx

第1页：第3章离散傅里叶变换及其快速算法

第3章离散傅里叶变换及其快速算法

第3章离散傅里叶变换及其快速算法 引言 周期序列的傅里叶级数变换及其性质 离散傅里叶变换的定义与物理意义 离散傅里叶变换的性质 DFT与序列的Z变换、DTFT以及DFS的关系 频域采样定理 快速傅里叶变换 模拟信号的频谱分析 DFT的矩阵表示与DFT、FFT的MATLAB实现。

第2页：本章教学目的与要求

• 【本章教学目的与要求】 掌握周期序列离散傅里叶级数（DFS）的定义与性质。
• 熟练掌握离散傅里叶变换（DFT）的物理意义及其与序列的傅里叶变换、Z变换的关系。
• 深入理解频域采样的有关理论。
• 熟练掌握按时间抽选的基-2 FFT和按频率抽选的基-2FFT的基本思想和方法。
• 掌握运用FFT算法计算离散傅里叶反变换的方法及实现。
• 学会应用MATLAB实现DFT、FFT，对信号进行频谱分析。

第3页：本章知识结构

【本章知识结构】。

第4页：3.1引言：DFT的必要性

• 引言 序列的傅里叶变换和Z变换都是时域离散信号与系统分析设计的重要数学工具，但是这两种变换的结果都是连续函数，无法应用计算机进行处理。
• 由于数字计算机只能够计算有限长离散序列，因此有限长序列在数字信号处理中非常重要。
• 为了便于数值处理，时间函数是离散的频谱函数也是离散的离散傅里叶变换（Discrete Fourier Transform，简称DFT）与其快速算法（Fast Fourier Transform，FFT）得到广泛的应用，在各种数字信号处理的算法中起着核心作用。
• 案例FFT变换方法在频谱分析仪中的应用。
• 频谱分析仪频谱分析仪主要用于分析信号中所包含的频率成分，也就是分析信号的频谱分布。
• 利用滤波、跟踪锁相或快速傅里叶变换等技术，应用一个或多个微处理器进行控制、误差修正和数据处理。
• 频谱分析通过FFT方法计算DFT，得到信号的离散频谱，再经平方运算获得功率谱。

第5页：3.2.1周期序列的离散傅里叶级数

周期序列的离散傅里叶级数周期序列是无限长序列，不是绝对可和的，所以不能用变换表示，因为在任何Ｚ值下，其变换都不收敛，即,为任意整数。是一个周期为Ｎ的周期序列，即设。

第6页：复指数序列的级数展开

复指数序列的形式为因而可展成如下的离散傅里叶级数，即（3-2）。

第7页：DFS系数的求解

这要利用复正弦序列的正交特性，即式（3-2）两端同乘以，然后在到的一个周期内求和，则得到下面求解系数。

第8页：DFS系数推导（换元）

把r换成k,可得。

第9页：DFS变换对

DFS变换对

也是一个以N为周期的周期序列，即定义,周期序列的傅里叶级数变换对为为了表示方便。

第10页：时域离散与频域周期的关系

• 背景资料一个域的离散必然造成另外一个域的周期延拓，即时域中离散造成频域的周期延拓，同样频域中的离散也必定造成时域的周期延拓。
• 在频域中将有限长序列（采样时间间隔为，采样频率为）的傅里叶变换进行离散化，频域的离散化造成时间函数也呈周期性，所以级数应限制在一个周期内。
• 频域采样间隔为，即令,则，因而序列的傅里叶变换为。

第11页：时域与频域的离散周期对应

因此有:时间函数是离散的，频率是离散的，所以有时间函数的周期为。

第12页：傅里叶变换对示意图

傅里叶变换对示意图图3.2离散周期的时间函数及其周期离散的频谱函数。

第13页：3.2.2离散傅里叶级数的性质

离散傅里叶级数的性质1.线性性质设和是周期皆为N的周期序列，各自DFS为或2.序列的移位。

第14页：周期卷积

周期卷积

.周期卷积如果频域中周期同为的序列满足条件则有证明由离散傅里叶级数反变换的定义可得由DFS变换的定义式可以得到其中，，都是以为周期的函数，所以有。

第15页：周期卷积的等价表达式

将间的变换关系代入式（3-12）,得经变量简单换元，可得等价的表达式。

第16页：两周期序列的周期卷积示意

图3.3两个周期序列（N=7）的周期卷积。

第17页：时域乘积与频域周期卷积

同样，由于DFS和IDFS变换的对称性，可以证明时域周期序列的乘积对应着频域周期序列的周期卷积。即如果则4.对偶性。

第18页：3.3离散傅里叶变换的定义

• 离散傅里叶变换的定义与物理意义 3.3.1离散傅里叶变换的定义在实际应用中，把无限长的周期序列送给计算机处理是不现实的，也是不必要的。
• 在3.2节讨论过，周期序列实际上只有有限个序列值有意义，它和有限长序列有着本质的联系。
• 实际上，可以把长度为的有限长序列看成周期为的周期序列的一个周期，这样，利用离散傅里叶级数计算周期序列的一个周期，也就计算了有限长序列的离散傅里叶变换。
• 本节将根据周期序列和有限长序列之间的这种本质关系，由周期序列的离散傅里叶级数表示推导出有限长序列的离散频域表示，即离散傅里叶变换（DFT）。

第19页：DFT的推导三步骤

• 由3.2节讨论的两者之间的关系，离散傅里叶变换可以按三个步骤由DFS推导出来：(1)将有限长序列延拓成周期序列。
• (2)求周期序列的DFS。
• (3)从DFS中取出一个周期便可得到有限长序列的DFT。
• 具体进行推导如下：设为有限长序列，长度为，即只在到N-1点上有值，其他时。
• 为了引用周期序列的概念，把它看成周期为的周期序列的一个周期，而把看成的以为周期的周期延拓，即表示成。

第20页：有限长序列及其周期延拓

图3.4有限长序列及其周期延拓。

第21页：DFS与IDFS的定义式

DFS与IDFS的定义式

周期序列的傅里叶级数变换DFS和傅里叶级数反变换IDFS的定义式为:频域的周期序列也可以看成是对有限长序列的周期延拓，而有限长序列可看成是周期序列的主值序列，即。

第22页：DFT与IDFT的表达式

上式中k，n在整个区间上都成立，当然在区间[0，N-1]上也成立，即存在下列表达式例3-1试计算长度为的序列的离散傅里叶变换。解：由欧拉公式可得。

第23页：例3-2 序列的10点IDFT

例3-2已知序列求其10点的IDFT解：将序列表示为写成这种形式，就容易确定离散傅里叶反变换。由于一个单位冲激序列的DFT为常数。

第24页：常数序列的DFT

同样，一个常数的DFT是一个单位冲激（采样）序列：所以。

第25页：3.3.2 DFT的物理意义

• 离散傅里叶变换的物理意义对于离散非周期信号的，其离散时间傅里叶变换DTFT[x(n)]是周期为的数字角频率的连续函数。
• 在频域中对连续频谱进行等间隔采样取值，得到离散的周期序列值。
• 根据频域采样定理，如果信号为点的有限长序列，则可以表示为有限项的复指数信号的线性组合，即有限长点序列的表达式为:其中。

第26页：例3-3 DTFT与DFT的比较

• 例3-3已知某长度为的离散时间信号1）计算信号的离散时间傅里叶变换和离散傅里叶变换，并比较两者之间的关系。
• 离散傅里叶变换的物理意义是序列的离散时间傅里叶变换的等间隔采样值的主值序列，其采样间隔为。
• 对于长度为的时域序列，都可以用项虚指数信号的线性加权表示。
• 不同的序列只是加权系数不同，该点的加权系数就是序列对应的频域序列。

第27页：序列补零后的频谱变化

序列补零后的频谱变化

（2）若对序列后补零，得到序列计算其离散时间傅里叶变换和离散傅里叶变换，有何结论。解：(1)根据离散时间傅里叶变换定义可得。

第28页：N=4序列的DFT计算

根据离散傅里叶变换的公式可以得到长度N=4的序列的离散傅里叶变换。

第29页：补零对DTFT与DFT的影响

）将序列补零为点的序列，则其离散时间傅里叶变换为:离散傅里叶变换：比较序列的离散时间傅里叶变换与序列的离散傅里叶变换，可以看到。

第30页：序列关系对比图

图3.5序列的关系图3.6序列的关系。

第31页：3.4离散傅里叶变换的性质

• 离散傅里叶变换的性质有限长序列的离散傅里叶变换可以从频域采样的角度进行理解，也可以从周期序列的DFS进行推导，因而DFT的许多性质与DFS性质存在相似之处。
• 本节讨论离散傅里叶变换(DFT)的一些性质，它们在本质上和周期序列的离散傅里叶级数（DFS）概念有关，而且是由有限长序列及其离散傅里叶变换表示式隐含的周期性得出的。
• 以下讨论的序列都是N点有限长序列，用DFT[.]示N点的DFT，且设1线性性质设两个有限长序列分别为和，则。

第32页：圆周移位的计算步骤

• 具体计算步骤为：（1）将以为周期进行周期延拓得到周期序列。
• （2）将加以移位得到。
• （3）对移位的周期序列取主值区间（到）上的序列值，即。
• 所以一个有限长序列的圆周移位序列依然是一个长度为的有限长序列，这一过程可用图3.7来表示。
• 一个长度为的有限长序列的圆周移位定义为2圆周移位。

第33页：圆周移位过程示意图

图3.7圆周移位过程示意图。

第34页：圆周移位后的DFT

则圆周移位后的DFT为式中证明利用周期序列DFS的移位性质加以证明再利用周期序列的DFS变换与有限长序列的离散傅里叶变换DFT之间的关系可以得到:设是长度为N的有限长序列，是圆周移位，即。

第35页：圆周移位的频域相移

• 这表明，有限长序列的圆周移位在离散频域中引入一个和频率成正比的线性相移,而对频谱的幅度没有影响。
• 对于频域有限长序列，也可以看成是分布在一个等分的圆周上，所以对的圆周移位，利用频域与时域的对偶关系，可以证明有以下性质：若则这就是调制特性。
• 它说明，时域序列的相位调制等效于频域的圆周移位。

第36页：时域圆周卷积定理

.圆周卷积(1)时域圆周卷积定理设和都是点数为N的有限长序列，且有若则证明:这个卷积相当于周期序列和作周期卷积后再取其主值序列。先将进行周期延拓，得。

第37页：圆周卷积的计算步骤

• 根据DFS的周期卷积公式由于为主值区间，，因此。
• 将上式经过简单换元，即可证明。
• 圆周卷积计算过程可以用图3.8来表示，分为如下五步。
• 1)周期延拓：先作和，将在参变量坐标上延拓成周期为的周期序列。
• 2)翻转：将翻转成。
• 3)移位和取主值：将移位并取主值序列得到。

第38页：圆周卷积示意

• )相乘：将相同值与相乘。
• 5)相加：将（4）中得到的乘积累加起来，便得到圆周卷积。
• 图3.8圆周卷积过程示意图。

第39页：频域圆周卷积定理

• （2）频域圆周卷积定理利用时域与频域的对称性，可以证明圆周卷积定理。
• 若，皆为点有限长序列则即时域序列相乘，其乘积的DFT等于各个序列DFT的圆周卷积再乘以1/N。
• 可以看出，它和周期卷积过程基本相似，只不过这里的圆周卷积要进行周期延拓和取主值序列运算。
• 特别要注意，两个长度小于等于N的序列的N圆周卷积长度仍为N，这与一般的线性卷积不同。
• 圆周卷积用符号来表示。
• 圆圈内的N表示所作的是N点圆周卷积，记为。

第40页：线性卷积与圆周卷积

• .有限长序列的线性卷积与圆周卷积时域圆周卷积在频域上相当于两序列的DFT的乘积，因而采用快速傅里叶变换（FFT）算法来计算圆周卷积，计算速度可以大大加快。
• 但是，在许多实际问题中常需要计算线性卷积，例如，一个FIR滤波器的输出等于输入与滤波器的单位采样响应的线性卷积。
• 如果找到线性卷积和圆周卷积之间的关系，就能够用圆周卷积来计算线性卷积而加快计算速度。
• 因此，讨论圆周卷积在什么条件下与线性卷积相等以及如何用圆周卷积运算来代替线性卷积运算的问题就非常重要。
• 设是点的有限长序列（），是点的有限长序列（）。
• 它们的线性卷积为。

第41页：线性卷积的非零区间

• 的非零区间为，的非零区间为,将两个不等式相加，得。
• 在上述区间外，不是就是，因而。
• 所以是点有限长序列，即线性卷积的长度等于参与卷积的两序列的长度之和减1。
• 例如，图3.9所示，为的矩形序列，为的矩形序列，则它们的线性卷积为点的有限长序列。

第42页：线性卷积与圆周卷积对比图

图3.9线性卷积与圆周卷积。

第43页：圆周卷积代替线性卷积的条件

• 再来看与的圆周卷积。
• 先讨论长度为点的圆周卷积，再讨论为何值时，圆周卷积才能代替线性卷积。
• 设两序列的点圆周卷积，这就要将与都看成是点的序列。
• 在这个序列值中，只有前个是非零值，后个均为补充的零值。
• 同样，只有前个是非零值，后个均为补充的零值。
• 则为了进行其圆周卷积的计算，必须先将序列与以为周期进行周期延拓，即(3-30)。

第44页：圆周卷积的周期延拓混叠

将它们代入到式(3-30)，得到。

第45页：例3-4 序列的10点DFT

• 前面已经分析了具有个非零值。
• 因此可以看到，如果周期卷积的周期，那么的周期延拓就必然有一部分非零序列值要交叠起来，从而出现混叠现象。
• 只有在时，才没有混叠现象。
• 这时，在的周期延拓中，每一个周期内，前个序列值正好是的全部非零值，也正是，而剩下的个点上的序列值则是补充的零值。
• 所以点圆周卷积是线性卷积以为周期的周期延拓序列的主值序列。
• 亦即，圆周卷积等于线性卷积而不产生混叠的必要条件为满足此条件后就有即。

第46页：例3-4 频域圆周移位求解

• 例3-4一个有限长序列为（1）计算序列的10点离散傅里叶变换。
• （2）若序列的DFT为式中，是的10点离散傅里叶变换，求序列。
• （3）若序列的10点离散傅里叶变换是。
• 式中，是的10点DFT，是的10点DFT求序列。

第47页：例3-4 求解过程

例3-4 求解过程

解（1）由离散傅里叶变换的的定义式（3-24）得（2）由时域圆周移位定理可得，频域中相当于时域中序列移位位，且,所以有（3）频域中对应时域中是的圆周卷积，利用圆周卷积与线性卷积的关系，可先求得线性卷积的数值。

第48页：复共轭序列的DFT

复共轭序列的DFT

.共轭对称性设为的复共轭序列，长度为，（1）复共轭序列的DFT则式中，证明将离散傅里叶变换的定义式中的变量用来代替并取共轭，得到:由圆周卷积与线性卷积的关系得到圆周卷积的数值为。

第49页：DFT的共轭对称性

DFT的共轭对称性

因为的隐含周期性，故。用同样的方法可以证明（2）DFT的共轭对称性设有限长序列的长度为点，则它的圆周共轭对称分量和圆周共轭反对称分量分别定义为:则两者满足:(3-35)(3-36)。

第50页：圆周共轭对称分量

如同任何实函数都可以分解成偶对称和奇对称分量一样，任何有限长序列都可以表示成其圆周共轭对称分量和圆周共轭反对称分量之和,即:圆周共轭对称分量和圆周共轭反对称分量的DFT分别为:（3-37）（3-38）。

第51页：共轭对称性质证明

• 证明：首先证明（3-37）式的正确性，由式（3-35）得利用式可得则（3-37）式得证。
• 同理可证式（3-38）。
• 若用，分别表示有限长序列的实部及虚部，即。

第52页：实部DFT与圆周共轭对称分量

式中，是的圆周共轭对称分量，且，为的圆周共轭反对称分量，且。则有(3-41)（3-42）式中，（3-40）（3-39）证明由式（3-41）可以得到。

第53页：实数序列DFT的计算量优化

• 这说明，复序列实部的DFT等于序列DFT的圆周共轭对称分量。
• 同理可证式（3-42）说明复序列虚部的DFT等于序列DFT的圆周共轭反对称分量。
• （3）实信号DFT变换设信号是长度为的实序列，其点DFT用表示，由离散傅里叶变换的定义式可以得到序列具有共轭对称性质，即（3-43）将序列表示成极坐标的形式，由的共轭性质说明序列的模以偶对称，相位以点奇对称，即。

第54页：一次DFT求两个实数序列

• 知识拓展由实数序列的共轭对称性质计算实数序列的DFT,可以减少计算量。
• 运用该性质能够用一次复数序列的点的离散傅里叶变换,计算两个不同实数序列的点的DFT或计算点实数序列的DFT。
• （1）设序列均为长度为的实数序列，将两序列按下式构造序列（3-45）对式（3-45）进行N点的DFT运算，得到所以（3-46）（3-47）。

第55页：序列与其DFT的奇偶虚实关系

这样只需要计算一个复数序列的点DFT，得到，利用（3-46)（3-47）就容易得到实数序列的DFT,显然减少了运算量（2）2N点实数序列的DFT，可以用N点复数序列的DFT得到。设是2N点的实数序列，将序列按照序列的奇偶点数进行分组，分解为两个长度均为点的序列，即:由构造长度为的复数序列，即利用式（3-46）、（3-47）得到序列的离散傅里叶变换，由可以得到实数序列的点的DFT,即。

第56页：表3-1 序列与DFT的奇偶虚实关系

• 证明如下：利用的周期性，可以计算得到序列。
• 综上所述，可以归纳证明与的奇、偶，虚、实关系，见表3-1。
• 利用这些关系，可以减少DFT的运算量。

第57页：表3-1说明与注意

表3-1说明与注意

表3-1序列及其DFT的奇、偶，虚、实关系注意，这里对有限长序列或的奇偶是指把序列排在一个圆周上，对为对称中心的奇偶对称。

第58页：DFT形式下的帕塞瓦定理

.DFT形式下的帕塞瓦定理设长度为的序列的点DFT为,则有（3-48）证明：首先计算设,代入上式可以得到即上述结论得证。

第59页：3.5 DFT与z变换、DTFT的关系

DFT与序列的Z变换、DTFT及DFS的关系 3.5.1DFT与序列的傅里叶变换、Z变换的关系如果是一个点的有限长序列，对进行变换(3-49)比较变换与序列的傅里叶变换、序列的离散傅里叶变换，我们可以看到，当时序列的变换与序列的傅里叶变换相等，即(3-50)式(3-50)表明序列的傅里叶变换的取值与序列的变换在单位圆的圆周上的连续取值相等。而当时，序列的z变换与序列的离散傅里叶变换相等，即。

第60页：序列z变换与DFT的关系式

• (3-51)序列的变换与序列的离散傅里叶变换之间的关系可以表示为下式(3-52)式(3-52)表明，序列可以看作是序列的傅里叶变换在主值区间的点等间隔抽样，采样间隔为。
• 显而易见，DFT的变换区间长度不同，表示对在区间的采样间隔和采样点数不同，所以DFT的变换结果也不同。
• 图3.10说明了序列的变换与序列的离散傅里叶变换、离散时间傅里叶变换之间的关系。

第61页：DFT与DTFT、z变换关系图

图3.10 DFT与序列傅里叶变换、变换的关系。

第62页：3.5.2 DFT与DFS的关系

• DFT与DFS变换之间的关系DFS是周期序列的离散傅里叶级数变换，DFT是有限长序列的离散傅里叶变换，对比DFS和DFT的定义，会发现DFS和DFT之间的密切关系。
• 首先利用长度为的有限长序列构造一个周期序列。
• 将以为周期进行周期延拓，形成周期为的周期序列，用下式表示（3-53）(3-54)毫无疑问，当时，上式中就是有限长序列以为周期的延拓序列，而序列是周期序列的主值序列。
• 由周期序列的DFS以及有限长序列的DFT的定义式来分析二者的关系，DFS变换与IDFS的定义式为。

第63页：例3-5 序列的DFS变换

例3-5 序列的DFS变换

（3-55）DFT变换与IDFT的定义式为例3-5有限长序列求其以为周期序列的DFS变换及序列的离散傅里叶变换，将计算结果进行比较。

第64页：序列以5为周期延拓

解将序列以5为周期进行周期延拓得到周期序列，如图3.11所示。图3.11序列与周期序列周期序列的傅里叶级数变换为。

第65页：DFS与DTFT样本值的关系

• 显然的取值就是序列的离散时间傅里叶变换在频率处的样本序列值。
• 上式表明只有在和时才有非零的DFS的系数。
• 利用离散傅里叶变换的定义式直接求得的离散傅里叶变换。

第66页：有限长序列与周期序列的联系

• 对比有限长序列和周期序列的联系，两序列的差别似乎很小，因为利用这两个关系式可以直接从其中一个构造出另一个。
• 然而在研究DFT的性质以及改变对的影响时，这种差别是很重要的。
• 信号时域采样理论实现了信号时域的离散化，使我们能用数字技术在时域对信号进行处理。
• 而离散傅里叶变换理论实现了频域离散化，因而开辟了用数字技术在频域处理信号的新途径，从而推进了信号的频谱分析技术向更深、更广的领域发展。

第67页：3.6频域采样定理

• 频域采样定理在3.5节中已经讲到，周期序列的离散傅里叶级数的系数的值和的一个周期的变换在单位圆的个均分点上的采样值相等，也可以说系数与序列的离散时间傅里叶变换在频域的等间隔采样值相等，这就实现了频域的采样。
• 在时域中，时域采样定理表明，在一定条件下，可以通过时域离散采样重建或恢复原来的连续信号。
• 那么，在频域中采样后，满足哪些条件可以恢复出原来信号的频谱函数呢。
• 设一个任意绝对可和的非周期序列，其变换为。

第68页：频域采样的前提条件

• 由于绝对可和，所以其傅里叶变换存在且连续，变换的收敛域包含单位圆的圆周。
• 如果对在平面单位圆的圆周上，即频率之间个频率点上对序列的傅里叶变换进行等间隔采样，得到频域离散周期序列（3-57）现在讨论的问题在于，这样在平面单位圆的圆周上进行采样之后的序列值能不能恢复出序列。
• 为此，由周期序列求其离散傅里叶级数反变换，令其为把（3-57）代入上式，可以得到。

第69页：频域采样与周期延拓

• 由于所以(3-58)式（3-58）说明，由序列得到的周期序列是原非周期序列的以为周期的延拓序列。
• 在1.5节中介绍了时域抽样造成频域的周期延拓，从公式（3-58）可以看到频域采样同样造成时域中的周期延拓。
• 所以有以下结论：（1）如果序列不是有限长序列，则时域周期延拓后，必定会造成时域中信号的混叠，产生假信号。
• 当增加时信号衰减越快，或频域采样越密，误差就越小。

第70页：频域采样点数不足的影响

• ）如果信号是有限长序列，且点数为，当频域采样点数不够密集时，即,序列以为周期进行延拓，就会产生混叠，从中就不能不失真地恢复出信号。
• 如果,则能够从中不失真地恢复出信号。
• （3）如果时域中序列的点数小于或等于,则可以利用序列的变换在平面单位圆的圆周上的等分采样值精确地表示。
• 因此，频域采样定理可以表述为：如果时域中原序列为点的有限长序列，对其频谱在频率区间上等间隔采样点，得到序列。
• 当时才能有频域采样序列恢复出序列。
• 否则将产生时域混叠失真。

第71页：频域采样值恢复原序列

既然频域采样序列的个采样值能够不失真地恢复出，那么这个采样值也一定能够完全地表达设有限长序列的Z变换为由于将其代入的表达式中，得到（3-59）。

第72页：频域内插公式

• 式（3-59）就是用频域中的个频率采样值来表示的内插公式。
• 它可以表示为（3-60）式中(3-61）式（3-61）称为内插函数，令（3-61）式分子等于零，可以得到该函数的零点分母等于零，有一个极点。
• 可以看出内插函数在平面单位圆的圆周的个等分点有个零点和一个极点，第个极点与其第个零点相抵消。
• 因而插值函数仅仅在处不为零，其他个零点处皆为零。
• 如图3.12所示。

第73页：内插函数的零极点分布

图3.12内插函数的零极点分布图由序列的变换和频率响应之间的关系，得到。

第74页：内插函数与频率响应

其中(3-62)所以有将式（3-62）表示成更方便的形式其中(3-63)(3-64)。

第75页：频域插值函数的幅度与相位

图3.13频域插值函数的幅度特性与相位特性（）频域插值函数的幅度特性和相位特性如图3.13所示。

第76页：插值函数的相位特性

（3-65）其中，相位呈线性相移加上一个的一个整数倍的相移变化，每隔的整数倍相位翻转，因而每隔的整数倍的相位要加上。因而，可以知道，满足以下关系。

第77页：内插函数的采样点特性

• 式（3-65）说明，函数在采样点上时。
• 在其他非采样点上时，函数。
• 频率特性是由个函数分别与相乘后求和。
• 所以很明显可以看出，在每一个采样点上精确地等于，即在这里，一般情况下，和都是复数。
• 在各采样点上的与相等，各采样点之间的值由各采样点的加权函数在所求点上的值的叠加得到，如图3.14所示。

第78页：由内插函数求得的序列示意

图3.14由内插函数求得的的示意图。

第79页：3.7直接计算DFT的运算量

快速傅里叶变换１．直接计算DFT的运算量设长度为点有限长序列，其DFT为（3-66）反变换(IDFT)为（3-67）两式的差别之存在于的指数不同，以及差一个常数因子，所以下面只讨论DFT的运算量，IDFT具有与DFT完全相同的运算量。

第80页：减少运算量的改进途径

• ．改进途径下面讨论减少运算量的途径。
• 仔细观察DFT的运算就可以看出，利用系数（旋转因子）的以下固有特性，就可以减少运算量。
• （1）的对称性（2）的周期性（3）的可约性利用这些特性，DFT运算中有些项便可以合并，并能将长序列的DFT分解为短序列的DFT进行运算。
• 而前面已经讲到，DFT的运算量与成正比的，所以越小越有利，因而小点数序列的DFT的运算量要小。

第81页：3.7.2按时间抽选基-2FFT原理

• 按时间抽选的基-2FFT算法1．算法原理设序列点数为正整数，若不满足这个条件，可以补若干个零值点，以达到这一要求。
• 这种为2的整数幂的FFT称为基2-FFT。
• 按时间抽选(DIT)的基2-FFT算法的基本出发点是，利用旋转因子的对称性和周期性，将一个长序列的DFT分解为一些点数逐次变小的DFT来计算。
• 分解过程遵循两条规则：1）对时间进行奇偶分解。
• 2）对频率进行前后分解。
• 设序列长度为，且满足为正整数。
• 按的奇偶把分解为两个点的子序列则可将DFT化为。

第82页：序列按奇偶分解

==（3-68）=上式说明，将序列按照的奇偶性分解为两个点的序列，从而点序列的离散傅里叶变换分解为两个点序列的离散傅里叶变换来实现。用序列分别表示的点的DFT,即（3-69）(3-70)。

第83页：N点DFT的分解计算

• 所以(3-71)利用和序列隐含的周期性可以得到(3-72)这样将点的序列DFT变换分解为计算两个点的DFT变换，代入（3-71）式可以求得前一半项数的结果，再计算（3-72）式,得到的后一半（）项数的结果。
• 式（3-71）、（3-72）的运算可以用信号流程图表示出来，如图3.15所示。
• 图形形状形如蝴蝶结，我们称之为蝶形信号流程图。
• 图中各支路的传递系数标注在支路的一侧，没有标注系数时，该支路系数为1。

第84页：按时间抽选的蝶形运算流程

图3.15按时间抽选的蝶形运算流程图采用这种算法，将点的序列的DFT的运算分解过程用图3.16表示。图3.16按时间抽选，将点DFT分解为2个点DFT。

第85页：蝶形运算的逐级分解

将进行分解为：（3-73）且（3-74）其中由于,因而N/2仍旧是偶数，可以进一步把每个点的子序列再按奇偶进行分组为两个点的子序列。

第86页：8点DFT分解为4点DFT

图3.17给出当时，将一个点DFT分解为点的DFT，由这两个点的DFT组合成点的DFT的运算流程图。图3.17两个点的DFT组合成点的DFT。

第87页：2点DFT的蝶形运算

2点DFT的蝶形运算

也可以进行同样的分解，得到：其中按照定义式分别求取的数值，得到序列的快速FFT运算的碟形流程图，如图3.18。

第88页：8点DIT-FFT运算流程图

图3.18时DIT的FFT运算流程图。

第89页：原位运算

• 按时间抽选的FFT的运算规律与软件实现的方法(1)原位运算由图3.18可以看出，DIT-FFT运算很有规律。
• 点的FFT由级运算，每级由个蝶形运算组成。
• 同一级中，每级蝶形运算的两个输入点只对计算本级的蝶形运算有用，而且每个蝶形运算的输入、输出数据在同一条水平线上，这就意味着计算完一个蝶形运算后，所得到的输出数据可以立即作为下一级蝶形运算的输入数据，因此可以将上一级蝶形运算的输出数据直接覆盖上一级蝶形运算的输入数据，即将计算得到的输出数据存入原输入数据所占用的存储单元。
• 这样经过级蝶形运算后，原来存放输入序列数据的个存储单元便依次存放了的个数值。
• 这种利用统一存储单元存储蝶形运算的输入、输出数据的方法称为原位运算。

第90页：旋转因子的指数变化规律

• （2）旋转因子的指数的变化规律点的DIT-FFT蝶形运算图中，每一级都有个蝶形，每一个蝶形都要乘以，称其为旋转因子。
• 但是蝶形运算级数不同形式及循环方式也不同。
• 用表示由左向右的运算级数,由图3.17可以看出，蝶形图中第级共有个不同的因子，当时各级蝶形运算的各级旋转因子表示为：时，时时对于的一般情况下，第级的旋转因子为由于。

第91页：蝶形运算规律

所以(3-75)(3-76)（3）蝶形运算规律从图3.18中可以看出这种运算很有规律，其每一级（每列）计算都有个蝶形运算构成，每一个蝶形运算完成下述基本的迭代运算：（3-77）式中表示第列迭代，表示数据所在的行数，即为蝶形结的运算节点的距离，由图3.18可以看出DIT蝶形运算的蝶形结的运算两节点间的距离为。式（3-77）的蝶形运算如图3.19所示。

第92页：DIT蝶形运算结构图

• 图3.19 DIT的蝶形运算结构图(4)倒位序规律由图3.17可以看出，按照原位计算时，FFT的输出是按照顺序位输出的，即按照的顺序排列，但这时输入序列不是按自然顺序排列的，而是按的顺序存入存储单元的，看起来杂乱无序，实际上是有规律的，称之为倒位序。
• 造成倒位序的原因是输入序列按照序列标号的奇偶不断分组。
• 这种不断分成偶数子序列和奇数组序列的过程可以用图3.20所示的二进制树状图来说明。

第93页：倒位序规律

图3.20描述倒位序的二进制树状图。

第94页：编程实现的规律

• （5）编程实现的思想观察图3.18，可以归纳出编程实现有用的规律：在第级蝶形运算中，每个蝶形运算的两数据之间相隔个点。
• 同一旋转因子对应着个蝶形结。
• 编程实现时，先从第一级（输入端）开始，逐级进行，共进行级运算。
• 在进行第级运算时，依次求出个不同的旋转因子，每求出一个旋转因子，就计算完它所对应的所有个蝶形。
• 这样，我们可以用三重循环实现DIT-FFT运算，程序框图如图3.21.。

第95页：DIT-FFT运算和程序框图

图3.21 DIT-FFT运算和程序框图。

第96页：3.7.3按频率抽取基-2FFT原理

• 按频率抽取的基-2FFT算法1算法原理这种按频率抽取(DIF)的基-2FFT算法推导过程遵循两个规则：1）对时间进行前后分解。
• 2）对频率进行偶奇分解设序列点数为，为正整数，同按时间抽取（DIT）的基-2FFT算法相同，若不满足这个条件，可以人为地加上若干个零值点，达到这一要求。
• 按规则1）把输入序列按前一半、后一半分开（不是按偶数、奇数分开），把点DFT写成两部分。

第97页：DIF算法的推导

序列的离散傅里叶变换中，由于，所以式（3-78）可以写成(3-79)按照为奇数还是偶数将频域中序列分成偶数组序列和奇数组序列。用表示偶数组序列，表示奇数组序列，则有(3-80a)(3-80b)。

第98页：DIF蝶形运算关系

令:(3-81)即有(3-82)式（3-81）式表示的运算关系可以用图3.22的蝶形运算来表示。图3.22 DIF的蝶形运算流程图。

第99页：8点序列DIF蝶形流程图

按照上述算法，可以绘制得到点的序列的蝶形运算流程图，如图3.23所示。图3.23 8点序列的DIF的蝶形运算图。

第100页：按频率抽选FFT的运算特点

• 按频率抽选的FFT的运算特点（1）原位运算按频率抽选的的基-2快速算法特点与按时间抽选的算法基本相同。
• 从图3.22可以看出它也是通过个蝶形运算完成，每个蝶形结构完成下述基本的迭代运算：（3-83）式中，表示第列迭代，为数据所在的行数，此式的迭代运算如图3.24所示，与按时间抽选一样，也是由一次复数乘法和两次复数加法组成，从图3.23看出这一流程图仍是原位运算。
• 图3.24按频率抽选蝶形运算结构图。

第101页：蝶形运算的距离

• ）蝶形运算的距离从图3.22看出，计算第一级（列）蝶形运算时（），一个蝶形的两个节点“距离”为4。
• 第二列时（），蝶形的两个节点的“距离”为2。
• 第三列时（），蝶形的两个节点的“距离”为1。
• 由于数据点数与蝶形运算的级数之间存在关系,所以可以推出蝶形运算的两个节点的“距离”为。
• 3）旋转因子的指数的确定对于第级蝶形运算，一个蝶形运算的两个节点间的“距离”为，则上式（3-83）的第级的一个蝶形运算可以表示为（3-84）。

第102页：旋转因子指数的确定

• 对于不同级数的迭代运算中旋转因子的指数因子如何确定，可以有严格的数学关系推导得到，在这里直接给出结论。
• 确定的方法为：（1）将（3-84）式中蝶形运算的两个节点中的第一个节点标号（值），表示成位二进制数。
• （2）将此二进制数左移位，把空出的位置补零。
• （3）将该二进制数表示成10进制数，即得到旋转因子的指数。
• 3按时间抽选和按频率抽选的FFT的区别两种FFT算法可以进行转换，将DIT的蝶形运算流程图进行转置就可以得到DIF的蝶形运算图，反之，亦然。

第103页：3.7.4 IDFT的快速计算

离散傅里叶反变换（IDFT）的快速计算上面的FFT变换算法也同样适用于离散傅里叶反变换（IDFT）运算，即快速傅里叶反变换（IFFT）。离散傅里叶反变换的公式为（3-85）式（3-85）与离散傅里叶变换的公式区别在于的指数是负的，将式（3-85）变换如下：(3-86)经过变换后，式（3-86）中的指数变成了正的，与离散傅里叶变换的形式一样，就可以应用FFT变换的程序来计算IFFT了。

第104页：3.8模拟信号的频谱分析

• 模拟信号的频谱分析 3.8.1公式推导及参数选择假设模拟信号的持续时间（观察时间）为，它的傅里叶变换为（3-87）的最高频率是。
• 用高于的采样频率对该模拟信号进行采样，得到离散序列，采样间隔为，在时间区间内共采样点。
• 对式（3-87）作零阶近似（）得到（3-88）再对进行等间隔采样，设在区间同样采样点，采样间隔为，得到（3-89）。

第105页：频谱分析的参数关系

• 将及式代入（3-89）中，得到(3-90)(3-91）上式表明由模拟信号时域采样得到点抽样序列，经过DFT(FFT)，再乘以，就是模拟信号在频域的采样。
• 式中代表在区间上第点的采样值，对应模拟频域就是区间上第点的采样值。
• 由式（3-91）还可以得到（3-92）式(3-91)和式(3-92)组成一对DFT，由经DFT反变换，再除以，得到原采样序列。
• 将分别代入频域插值公式和时域插值公式求得连续时间信号的频谱函数及。

第106页：频谱分析的参数选择

• 在对模拟信号进行频谱分析时，有几个重要的参数要选择，即采样频率，频率分辨率，频谱分析范围及采样点数。
• 采样频率决定于信号的最高截止频率,因此需要预先知道信号的最高截止频率。
• 是频域的采样间隔，是用DFT分析频谱时，能够分辨的两个频率分量最小的间隔，因此称为频率分辨率。
• 显然应根据频谱分析的要求确定。
• 信号的最高频率不应该超过，因此频谱分析范围是。
• 采样点数和对信号的观察时间有关，但又和频率分辨率有关。
• 下面给出几个参考公式（3-93）为了使用FFT，要求采样点数服从2的整数次幂。
• 实际上，模拟信号一般为无限长，既要提高频率分辨率，又要照顾到频谱分析范围不减小，必须增加观察时间。

第107页：例3-6 频谱分辨率与记录时间

• 例题3-6对模拟信号进行频谱分析，要求频谱分辨率，信号最高频率。
• 试计算（1）最小的记录时间长度、最大采样间隔、最小采样点数及谱分析范围。
• （2）如果信号的最高频率不变，采样频率不能降低，如何改变参数将频谱分辨率提高1倍。
• 解：（1）由式（3-93）可得:(2)要将频率分辨率提高1倍，采样频率不能降低，只有通过增加时间，增加采样点数实现。
• 最小记录时间和最小采样频率计算如下。

第108页：3.8.2周期信号的谱分析

• 用DFT(FFT)对周期信号进行谱分析假设由模拟信号采样得到周期序列，其周期为，对进行傅里叶变换，得到的频谱为:(3-94)式中，由此可见，以为周期的周期序列有次谐波，可用主值区[0，2π]上的条谱线表示。
• 第条谱线位于处，谱线的强度为。
• 如果截取的主值区，得到，再对进行点DFT，得到因此，可以截取的主值区，作点DFT,用得到的表示的频谱的有效的频谱成分。

第109页：例3-7 周期信号频谱分析

• 例题3-7已知模拟信号，其中，试用DFT分析信号频谱。
• 解：这是一个周期信号，信号周期为。
• 对信号进行采样的最小采样频率为，取采样频率为,并且取采样时间为一个周期，即0.5ms,采样点数为,即一个周期中取8点，采样后序列可以用下式表示。

第110页：8点DFT幅度曲线

• 对上式可以进行8点的DFT计算，得到，它的幅度曲线如图3.25a所示。
• 8点的数字频率为。
• 对应的模拟频率为。
• 当时，具体的模拟频率为。
• 信号刚好在的谱线上。
• 如果对该周期信号不按照周期的倍数截取，假设取。
• 仍按进行采样，共采样12点，作12点DFT，得到的幅度曲线如图3.25b所示。

第111页：3.8.3谱分析的误差

• 用DFT对模拟信号进行谱分析的误差1.频谱混叠如果采样频率不满足采样定理，会在附近引起频谱混叠，造成频谱分析误差。
• 一般模拟信号只要有不连续点，它的频谱函数总会拖着很长的尾巴，并不是陡截止的，因此，采样频率要选择的适当高一些，但总还会存在轻微的频谱混叠。
• 另外信号中总会或多或少的有干扰或噪声，这也是引起频谱混叠的原因。
• 在进行谱分析时，应该注意因频谱混叠引起的误差。
• 2.截断效应模拟信号的傅里叶变换是在区间上的一种积分运算，实际中观察到的模拟信号一般是有限长的，没有观察到的那部分只能认为是零，这相当于将模拟信号截取一部分进行分析。
• 即使能得到无限长的模拟信号，也只能截断，因为DFT是一种有限点的离散傅里叶变换。
• 因截断引起的误差现象称为截断效应。

第112页：矩形窗截断的影响

式中，起对信号截断的作用，称它为矩形窗。对上式进行傅里叶变换，得到（3-96）其中，（3-97）式(3-97)中，（3-95）假设对模拟信号进行采样得到采样序列，对它截取一段，长度为，得到采样序列。

第113页：加窗前后的幅度谱对比

图3.26矩形窗的幅度谱图3.27加矩形窗前、后的幅度谱矩形窗的幅度谱用矩形窗将它截断前后的幅度谱。

第114页：DFT计算离散谱的栅栏效应

• 一般信号的频谱是频率的连续函数（周期信号除外），但用DFT(FFT)计算出的频谱是离散谱，当DFT的点数较多时，离散谱的包络才接近于信号的频谱，这只能是近似的．Ｎ点DFT(FFT)得到的只是Ｎ个采样点的频谱值，两点之间的频谱值是不知道的，就好像被栅栏遮住一样，因此这种现象被称为栅栏效应。
• 为了减轻栅栏效应可以增加DFT（FFT）的变换点数，即对信号频谱进行更多点的采样。
• 如果采样点数不能再增多，可以通过信号的尾部加零的方法加大DFT(FFT)的变换点数。

第115页：3.9 DFT的矩阵表示

3.9 DFT的矩阵表示

DFT的矩阵表示与DFT、FFT的MATLAB实现 DFT的矩阵表示有限长序列的离散傅里叶变换DFT也可以用矩阵形式表示，DFT定义式可以表示成向量形式。其中，向量由频域序列的个DFT的系数构成，即向量由时域序列的个样本值构成，即。

第116页：IDFT矩阵与DFT矩阵

是由离散傅里叶反变换的系数构造成的的IDFT矩阵（3-99）系数矩阵Ｄ是由离散傅里叶变换的系数构造成的的DFT矩阵，表示为(3-98)。

第117页：3.9.2 MATLAB计算序列DFT

• 用MATLAB计算序列的DFT根据上述DFT和IDFT的矩阵表示式，可以直接利用MATLAB矩阵运算求取序列的DFT或IDFT。
• 但直接计算DFT计算量很大，计算速度太慢。
• MATLAB提供了用快速傅里叶变换算法FFT计算DFT的函数FFT，其调用格式如下：IFFT函数计算IDFT，其调用格式与FFT函数相同。

第118页：序列FFT与补零的MATLAB实现

• 设，取采样间隔，采样点数为（1）对进行采样得到序列，求其FFT变换。
• （2）将（1）中序列补零补至200点，求其FFT变换。
• （3）数据采样点数为200点，即，分析高密度频谱与高分辨率频谱之间的差异。