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

第第4 4章章 离散傅里叶变换离散傅里叶变换5.1 5.1 减少减少减少减少DFTDFT运算量的基本途径运算量的基本途径运算量的基本途径运算量的基本途径5.2 5.2 按时间抽取（按时间抽取（按时间抽取（按时间抽取（DITDIT）的基）的基）的基）的基-2 FFT-2 FFT算法算法算法算法5.3 5.3 按频率抽取（按频率抽取（按频率抽取（按频率抽取（DIFDIF）的基）的基）的基）的基-2 FFT-2 FFT算法算法算法算法 返回到本章向导返回到本章向导返回到本章向导返回到本章向导5.4 5.4 离散傅里叶反变换（离散傅里叶反变换（离散傅里叶反变换（离散傅里叶反变换（IDFTIDFT）的快速算法）的快速算法）的快速算法）的快速算法第第5 5章章 快速傅里叶变换快速傅里叶变换5.5 FFT5.5 FFT实例分析实例分析实例分析实例分析第第4 4章章 离散傅里叶变换离散傅里叶变换5.1 减少减少DFT运算量运算量的基本途径的基本途径5 5、快速傅立叶变换、快速傅立叶变换 1.1.问题的提出问题的提出问题的提出问题的提出 返回到本节向导返回到本节向导返回到本节向导返回到本节向导 其其DFT变换对为：变换对为：DFT和和IDFT运算的差别：运算的差别：相差一个常数相差一个常数 1/N；对对N 点有限长序列点有限长序列 ；旋转因子旋转因子 的指数符号不同；的指数符号不同；所以我们只分析所以我们只分析DFT的运算量；的运算量；第第4 4章章 离散傅里叶变换离散傅里叶变换5.1 减少减少DFT运算量运算量的基本途径的基本途径5 5、快速傅立叶变换、快速傅立叶变换 1.1.问题的提出问题的提出问题的提出问题的提出 返回到本节向导返回到本节向导返回到本节向导返回到本节向导 结果：结果：采用采用FFT算法计算算法计算DFT；计算每一个计算每一个 需要需要 N 次复次复数乘法和数乘法和 次复数加法；次复数加法；由于由于 是是 N 点序列；点序列；需要需要 次复数乘法和次复数乘法和 次复数加法；次复数加法；在在在在 N N 值较大时，运算速度将大幅度提高！值较大时，运算速度将大幅度提高！值较大时，运算速度将大幅度提高！值较大时，运算速度将大幅度提高！因此直接计算整个因此直接计算整个DFT需要需要 N2次复数乘法和次复数乘法和 次复数加法；次复数加法；当当 时，直接计算时，直接计算DFT的运算量为的运算量为N2 数量级！数量级！第第4 4章章 离散傅里叶变换离散傅里叶变换5.1 减少减少DFT运算量运算量的基本途径的基本途径5.5.快速傅立叶变换快速傅立叶变换 1.1.问题的提出问题的提出问题的提出问题的提出 返回到本节向导返回到本节向导返回到本节向导返回到本节向导 一方面可以将某些项合并一方面可以将某些项合并一方面可以将某些项合并一方面可以将某些项合并；直接计算直接计算DFT和采用基和采用基2 FFT计算计算DFT的运算量比较的运算量比较：112645120230410244481928032124194304104857626211465536163844096102425664N2204810245122561286432168N2.2.减少运算量的基本途径减少运算量的基本途径减少运算量的基本途径减少运算量的基本途径 在在DFT运算中，利用旋转因子运算中，利用旋转因子 的性质：的性质：另一方面可以不断地将长序列分解为短序列的组另一方面可以不断地将长序列分解为短序列的组合，用短序列的合，用短序列的 DFT 计算来代替长序列计算来代替长序列 DFT ；第第4 4章章 离散傅里叶变换离散傅里叶变换5.1 减少减少DFT运算量运算量的基本途径的基本途径5 5 快速傅立叶变换快速傅立叶变换返回到本节向导返回到本节向导返回到本节向导返回到本节向导由于直接计算由于直接计算DFT的运算量与序列长度的运算量与序列长度N 的平方的平方（N 2）成正比，这样显然可以减少运算量；）成正比，这样显然可以减少运算量；2.2.减少运算量的基本途径减少运算量的基本途径减少运算量的基本途径减少运算量的基本途径 旋转因子的主要性质为：旋转因子的主要性质为：旋转因子的主要性质为：旋转因子的主要性质为：周期性：周期性：对称性：对称性：可约性：可约性：由此可得：由此可得：第第4 4章章 离散傅里叶变换离散傅里叶变换5.1 减少减少DFT运算量运算量的基本途径的基本途径5 5 快速傅立叶变换快速傅立叶变换返回到本节向导返回到本节向导返回到本节向导返回到本节向导FFTFFT算法在这一思路基础上发展而成；算法在这一思路基础上发展而成；算法在这一思路基础上发展而成；算法在这一思路基础上发展而成；2.2.减少运算量的基本途径减少运算量的基本途径减少运算量的基本途径减少运算量的基本途径 分为：分为：按频率抽取（按频率抽取（DIFDecimation-In-Frequency）法；）法；按时间抽取（按时间抽取（DITDecimation-In-Time）法）法 ：其中：基其中：基-2 FFT 是最基本的是最基本的 FFT 算法，它要算法，它要求求 FFT 的点数的点数 N=2L（L为正整数）；为正整数）；如果序列长度不满足这一条件，需要用如果序列长度不满足这一条件，需要用后补零值点的方法来补齐。后补零值点的方法来补齐。第第4 4章章 离散傅里叶变换离散傅里叶变换5 5 快速傅立叶变换快速傅立叶变换返回到本节向导返回到本节向导返回到本节向导返回到本节向导1.1.基本原理基本原理基本原理基本原理 则则 的的DFT转化为：转化为：5.2 按时间抽取的按时间抽取的基基-2 FFT算算法法 第第4 4章章 离散傅里叶变换离散傅里叶变换5 5 快速傅立叶变换快速傅立叶变换返回到本节向导返回到本节向导返回到本节向导返回到本节向导1.1.基本原理基本原理基本原理基本原理 由于由于 是是 N 点点 DFT，因此前式，因此前式只表示出了只表示出了 的前一半值；的前一半值；的后一半值可以表示为：的后一半值可以表示为：这样就将这样就将 N 点点 DFT 分解为两个分解为两个 N/2 点的点的 DFT！只要求出只要求出 区间的区间的 和和 ；就可以求出区间就可以求出区间 的全部的全部 的值；的值；5.2 按时间抽取的按时间抽取的基基-2 FFT算算法法 第第4 4章章 离散傅里叶变换离散傅里叶变换5.2 按时间抽取的按时间抽取的基基-2 FFT算算法法 5 5 快速傅立叶变换快速傅立叶变换返回到本节向导返回到本节向导返回到本节向导返回到本节向导 是在时域将序列逐次分解为长是在时域将序列逐次分解为长度减半的奇序号子序列和偶序号度减半的奇序号子序列和偶序号子序列，用子序列的子序列，用子序列的 DFT 来实现来实现整个序列整个序列 DFT；1.1.基本原理基本原理基本原理基本原理 N 点有限长序列点有限长序列 ，首先按奇、偶序号将首先按奇、偶序号将 分解为两个长度分解为两个长度 为的子序列：为的子序列：第第4 4章章 离散傅里叶变换离散傅里叶变换5 5 快速傅立叶变换快速傅立叶变换返回到本节向导返回到本节向导返回到本节向导返回到本节向导1.1.基本原理基本原理基本原理基本原理 该式的运算可以用蝶形运算信号流图符号表示；该式的运算可以用蝶形运算信号流图符号表示；即：即：即：即：可以看出，要完成一个蝶形运算，需要一次可以看出，要完成一个蝶形运算，需要一次复数乘法和两次复数加法。复数乘法和两次复数加法。5.2 按时间抽取的按时间抽取的基基-2 FFT算算法法 第第4 4章章 离散傅里叶变换离散傅里叶变换5 5 快速傅立叶变换快速傅立叶变换返回到本节向导返回到本节向导返回到本节向导返回到本节向导1.1.基本原理基本原理基本原理基本原理 经过第一次分解：经过第一次分解：DFT的运算量基本上减少了一半；的运算量基本上减少了一半；5.2 按时间抽取的按时间抽取的基基-2 FFT算算法法 第一次分解：第一次分解：8点点DFT分解为两个分解为两个4点点DFT 第第4 4章章 离散傅里叶变换离散傅里叶变换5 5 快速傅立叶变换快速傅立叶变换返回到本节向导返回到本节向导返回到本节向导返回到本节向导1.1.基本原理基本原理基本原理基本原理 经过第二次分解经过第二次分解：一个：一个 N 点点 DFT 分解为四个分解为四个 N/4点点DFT，运算量进一步减半；，运算量进一步减半；对于剩下的两点对于剩下的两点 DFT 有：有：5.2 按时间抽取的按时间抽取的基基-2 FFT算算法法 第二次分解：第二次分解：4点点 DFT 分解为两个分解为两个2点点 DFT 第第4 4章章 离散傅里叶变换离散傅里叶变换5 5 快速傅立叶变换快速傅立叶变换返回到本节向导返回到本节向导返回到本节向导返回到本节向导1.1.基本原理基本原理基本原理基本原理 表明：表明：2点点DFT也可以表示为一个蝶形运算；也可以表示为一个蝶形运算；即：即：即：即：N 点点 DFT 的最后一次分解是将的最后一次分解是将 N/2 个个 2 点点 DFT分解为分解为 N 个个 1 点点 DFT；2点点 DFT 分解为两个分解为两个 1 点点 DFT 5.2 按时间抽取的按时间抽取的基基-2 FFT算算法法 第第4 4章章 离散傅里叶变换离散傅里叶变换5 5 快速傅立叶变换快速傅立叶变换返回到本节向导返回到本节向导返回到本节向导返回到本节向导1.1.基本原理基本原理基本原理基本原理 一个一个N=8点的按时间抽取基点的按时间抽取基-2 FFT运算流图如图：运算流图如图：5.2 按时间抽取的按时间抽取的基基-2 FFT算算法法 第第4 4章章 离散傅里叶变换离散傅里叶变换5 5 快速傅立叶变换快速傅立叶变换返回到本节向导返回到本节向导返回到本节向导返回到本节向导2.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 按时间抽取的按时间抽取的基基-2 FFT算算法法 第第4 4章章 离散傅里叶变换离散傅里叶变换5 5 快速傅立叶变换快速傅立叶变换返回到本节向导返回到本节向导返回到本节向导返回到本节向导2.2.算法规律算法规律算法规律算法规律 蝶形单元蝶形单元 DFT 各级的运算都是由蝶形运算构成的各级的运算都是由蝶形运算构成的；每一级中都含有每一级中都含有N/2个蝶形单元个蝶形单元；每个蝶形单元有两个节点每个蝶形单元有两个节点（i，j）参加运算参加运算；前一级（第前一级（第m-1级）蝶形单元的输出是后一级）蝶形单元的输出是后一级（第级（第m级）蝶形单元的输入级）蝶形单元的输入；每一个蝶形单元的运算需要一次复数每一个蝶形单元的运算需要一次复数每一个蝶形单元的运算需要一次复数每一个蝶形单元的运算需要一次复数乘法和两次复数加法；乘法和两次复数加法；乘法和两次复数加法；乘法和两次复数加法；完成完成 级蝶形运算共需要的运算量为：级蝶形运算共需要的运算量为：复数乘法：复数乘法：复数加法：复数加法：5.2 按时间抽取的按时间抽取的基基-2 FFT算算法法 第第4 4章章 离散傅里叶变换离散傅里叶变换5 5 快速傅立叶变换快速傅立叶变换返回到本节向导返回到本节向导返回到本节向导返回到本节向导2.2.算法规律算法规律算法规律算法规律 蝶形单元的节点距离蝶形单元的节点距离 每级中蝶形单元两节点（每级中蝶形单元两节点（i，j）间的距离不等；）间的距离不等；第第 1 级蝶形单元的节点距离为级蝶形单元的节点距离为 1；第第 2 级蝶形单元的节点距离为级蝶形单元的节点距离为 2；第第 3 级为级为 4；第第m（m=1,2,L）级蝶形）级蝶形单元的节点距离为单元的节点距离为 ；即：即：即：即：，依此类推；，依此类推；5.2 按时间抽取的按时间抽取的基基-2 FFT算算法法 第第4 4章章 离散傅里叶变换离散傅里叶变换5 5 快速傅立叶变换快速傅立叶变换2.2.算法规律算法规律算法规律算法规律 “组组”的概念的概念 每一级的每一级的 N/2 个蝶形单元通常分为若干组个蝶形单元通常分为若干组；，依此类推；，依此类推；同级的每一组都具有相同的结构和同级的每一组都具有相同的结构和 分布分布；旋转因子旋转因子 的分布的分布 第第 L 级（即第一次分解）蝶形单元的旋转因级（即第一次分解）蝶形单元的旋转因子为子为 ；第第L-1级（即第二次分解）为级（即第二次分解）为 ；返回到本节向导返回到本节向导返回到本节向导返回到本节向导第第 m 级蝶形单元级蝶形单元的旋转因子为：的旋转因子为：5.2 按时间抽取的按时间抽取的基基-2 FFT算算法法 第第4 4章章 离散傅里叶变换离散傅里叶变换5 5 快速傅立叶变换快速傅立叶变换返回到本节向导返回到本节向导返回到本节向导返回到本节向导2.2.算法规律算法规律算法规律算法规律 倒位序倒位序 ，变换后的输出序列变换后的输出序列 按照自然顺序排列按照自然顺序排列；但输入序列但输入序列 却已不再是自然顺序；却已不再是自然顺序；原因：由于按奇、偶序号不断分解而产生的原因：由于按奇、偶序号不断分解而产生的；5.2 按时间抽取的按时间抽取的基基-2 FFT算算法法 第第4 4章章 离散傅里叶变换离散傅里叶变换5 5 快速傅立叶变换快速傅立叶变换返回到本节向导返回到本节向导返回到本节向导返回到本节向导 倒位序倒位序倒位序倒位序 ，就是将自然顺序的二进制位倒置；就是将自然顺序的二进制位倒置；将输入序列的这种排列顺序称为倒位序；将输入序列的这种排列顺序称为倒位序；即将即将 倒置为倒置为 ；用二用二用二用二进制进制进制进制树状树状树状树状图来图来图来图来描述描述描述描述 5.2 按时间抽取的按时间抽取的基基-2 FFT算算法法 第第4 4章章 离散傅里叶变换离散傅里叶变换5 5 快速傅立叶变换快速傅立叶变换 原位运算原位运算原位运算原位运算 整个运算过程中，每一级蝶形运算的输入和输出整个运算过程中，每一级蝶形运算的输入和输出在运算前后都存储在同一组存储单元中，直至最在运算前后都存储在同一组存储单元中，直至最后输出；后输出；返回到本节向导返回到本节向导返回到本节向导返回到本节向导每一级的蝶形运算有每一级的蝶形运算有 N 个节点个节点（从第一行开始依次为节点（从第一行开始依次为节点0、1、N-1）和和N/2 个个蝶形单元；蝶形单元；每两个节点只参加一个蝶形单元的运算；每两个节点只参加一个蝶形单元的运算；而与同级的其它蝶形单元无关；而与同级的其它蝶形单元无关；中间不需要占用其它存储单元！中间不需要占用其它存储单元！中间不需要占用其它存储单元！中间不需要占用其它存储单元！原位运算原位运算原位运算原位运算 特点：以节省存储单元，降特点：以节省存储单元，降低设备成本！低设备成本！5.2 按时间抽取的按时间抽取的基基-2 FFT算算法法 第第4 4章章 离散傅里叶变换离散傅里叶变换5 5 快速傅立叶变换快速傅立叶变换 原位运算原位运算原位运算原位运算 返回到本节向导返回到本节向导返回到本节向导返回到本节向导按自然顺序存放在存储单元中的输入序列按自然顺序存放在存储单元中的输入序列值，只要将某些单元的内容对调即可得到值，只要将某些单元的内容对调即可得到按倒位序存储的输入序列值；按倒位序存储的输入序列值；倒位序的变址处理倒位序的变址处理 5.2 按时间抽取的按时间抽取的基基-2 FFT算算法法 第第4 4章章 离散傅里叶变换离散傅里叶变换补充：补充：按时间抽取的按时间抽取的FFT算法的其他形式流图算法的其他形式流图对于任何流图，只要保持各节点所连的支路及传输系数不变，则对于任何流图，只要保持各节点所连的支路及传输系数不变，则不论节点位置怎么排列所得流图总是等效的，所得最后结果都是不论节点位置怎么排列所得流图总是等效的，所得最后结果都是x(n)的的DFT的正确结果，只是数据的提取和存放的次序不同而已。的正确结果，只是数据的提取和存放的次序不同而已。这样就可得到按时间抽取的这样就可得到按时间抽取的FFT算法的若干其他形式流图。算法的若干其他形式流图。和和x(4)水平相连的所有节点和水平相连的所有节点和x(1)水平相连的所有节点位置对调，水平相连的所有节点位置对调，再将和再将和x(6)水平相连的所有节点与和水平相连的所有节点与和x(3)水平相连的所有节点对调，水平相连的所有节点对调，其余诸节点保持不变，可得下图的流图。其余诸节点保持不变，可得下图的流图。5 5 快速傅立叶变换快速傅立叶变换第第4 4章章 离散傅里叶变换离散傅里叶变换5 5 快速傅立叶变换快速傅立叶变换第第4 4章章 离散傅里叶变换离散傅里叶变换 数据存放的方式不同，原图是输入倒位序、输出自然顺序，变换后是输入自然顺序、输出倒位序；取用系数的顺序不同，原图的最后一列是按 的顺序取用系数，且其前一列所用系数是后一列所用系数中具有偶数幂的那些系数（例如 ）；变换后是最后一列是按 的顺序取用系数，且其前一列所用系数是后一列所用系数的前一半，5 5 快速傅立叶变换快速傅立叶变换第第4 4章章 离散傅里叶变换离散傅里叶变换5 5 快速傅立叶变换快速傅立叶变换返回到本节向导返回到本节向导返回到本节向导返回到本节向导1.1.基本原理基本原理基本原理基本原理 N 点有限长序列点有限长序列 ，将输入序列将输入序列 按按n的顺序分为前后两部分：的顺序分为前后两部分：注意：式中用的是注意：式中用的是注意：式中用的是注意：式中用的是 而不是而不是而不是而不是 ；所以仍是所以仍是所以仍是所以仍是 N N 点点点点 DFTDFT！5.3 按频率抽取的按频率抽取的基基-2 FFT算算法法 第第4 4章章 离散傅里叶变换离散傅里叶变换5 5 快速傅立叶变换快速傅立叶变换返回到本节向导返回到本节向导返回到本节向导返回到本节向导1.1.基本原理基本原理基本原理基本原理 由于由于 ；所以所以 ；有：有：当当 k 为偶数时为偶数时 ；当当 k 为奇数时为奇数时 ；将将 按按 k为奇偶分解为两个为奇偶分解为两个 N/2 点子序列，即：点子序列，即：代代代代入入入入5.3 按频率抽取的按频率抽取的基基-2 FFT算算法法 第第4 4章章 离散傅里叶变换离散傅里叶变换5 5 快速傅立叶变换快速傅立叶变换返回到本节向导返回到本节向导返回到本节向导返回到本节向导1.1.基本原理基本原理基本原理基本原理 令：令：令：令：显然，显然，和和 均为均为 N/2 点序列；点序列；代代代代入入入入5.3 按频率抽取的按频率抽取的基基-2 FFT算算法法 第第4 4章章 离散傅里叶变换离散傅里叶变换5 5 快速傅立叶变换快速傅立叶变换返回到本节向导返回到本节向导返回到本节向导返回到本节向导1.1.基本原理基本原理基本原理基本原理 其运算可以用蝶形运算信号流图符号表示为：其运算可以用蝶形运算信号流图符号表示为：上页得到的公式上页得到的公式按频率抽取的蝶形运算信号流图符号按频率抽取的蝶形运算信号流图符号 5.3 按频率抽取的按频率抽取的基基-2 FFT算算法法 第第4 4章章 离散傅里叶变换离散傅里叶变换5 5 快速傅立叶变换快速傅立叶变换把一个把一个N点点DFT按按k的奇偶分解为两个的奇偶分解为两个N/2点的点的DFT了。了。N=8时，时，图（1）按频率抽取的第一次分解 第第4 4章章 离散傅里叶变换离散傅里叶变换5 5 快速傅立叶变换快速傅立叶变换与时间抽取法的推导过程一样，由于与时间抽取法的推导过程一样，由于N=2M，N/2仍是一个偶数，仍是一个偶数，因而可以将每个因而可以将每个N/2点点DFT的输出再分解为偶数组与奇数组，这就的输出再分解为偶数组与奇数组，这就将将N/2点点DFT进一步分解为两个进一步分解为两个N/4 点点DFT。这两个这两个N/4点点DFT的的输入也是先将输入也是先将N/2点点DFT的输入上下对半分开后通过蝶形运算而形的输入上下对半分开后通过蝶形运算而形成的，图（成的，图（2）示出了这一步分）示出了这一步分解的过程。解的过程。第第4 4章章 离散傅里叶变换离散傅里叶变换按频率抽取的第二次分解按频率抽取的第二次分解 5 5 快速傅立叶变换快速傅立叶变换第第4 4章章 离散傅里叶变换离散傅里叶变换按频率抽取的第三次分解按频率抽取的第三次分解 5 5 快速傅立叶变换快速傅立叶变换第第4 4章章 离散傅里叶变换离散傅里叶变换5 5 快速傅立叶变换快速傅立叶变换返回到本节向导返回到本节向导返回到本节向导返回到本节向导2.2.算法规律算法规律算法规律算法规律 按频率抽取基按频率抽取基按频率抽取基按频率抽取基-2FFT-2FFT算法和按时算法和按时算法和按时算法和按时间抽取基间抽取基间抽取基间抽取基-2FFT-2FFT算法类似；算法类似；算法类似；算法类似；共有共有 级运算；级运算；每级有每级有 N/2 个蝶形单元；个蝶形单元；所以：两种算法的运算量相同！所以：两种算法的运算量相同！所以：两种算法的运算量相同！所以：两种算法的运算量相同！也都是原位运算！也都是原位运算！5.3 按频率抽取的按频率抽取的基基-2 FFT算算法法 DIT-FFT与与DIF-FFT的基本蝶形单元之间、的基本蝶形单元之间、FFT运算流图之间都是转置的关系；运算流图之间都是转置的关系；两种两种FFT算法的运算量相同，运算过程也类似，算法的运算量相同，运算过程也类似，在实际应用中可以任意选用在实际应用中可以任意选用 第第4 4章章 离散傅里叶变换离散傅里叶变换5 5 快速傅立叶变换快速傅立叶变换返回到本节向导返回到本节向导返回到本节向导返回到本节向导由离散傅立叶变换的定义：由离散傅立叶变换的定义：由离散傅立叶变换的定义：由离散傅立叶变换的定义：5.4 离散傅里叶反变换离散傅里叶反变换（IDFT）的快速算）的快速算法法 就可以按照前面的就可以按照前面的DIT-FFT和和DIF-FFT来实现来实现IDFT的快速运算，即的快速运算，即IFFT算法；算法；正变换：正变换：反变换：反变换：只要将只要将DFT运算中的系数运算中的系数 换换换换 成成成成最后再乘以常数最后再乘以常数1/N；但用这种方法得到的但用这种方法得到的IFFT算法需要稍稍改动算法需要稍稍改动FFT的程序和系数！的程序和系数！第第4 4章章 离散傅里叶变换离散傅里叶变换5 5 快速傅立叶变换快速傅立叶变换返回到本节向导返回到本节向导返回到本节向导返回到本节向导为了不改变为了不改变为了不改变为了不改变FFTFFT程序就可以计算程序就可以计算程序就可以计算程序就可以计算 IFFTIFFT；：；：；：；：5.4 离散傅里叶反变换离散傅里叶反变换（IDFT）的快速算法）的快速算法 将将 IDFT 表达式两边取共轭：表达式两边取共轭：则有：则有：表明：表明：只要对只要对 取共轭作为输入；取共轭作为输入；就可以直接利用就可以直接利用FFT程序，最后将输出程序，最后将输出再取一次共轭，并乘以常数再取一次共轭，并乘以常数 1/N 即可得即可得到序列到序列 ！第第4 4章章 离散傅里叶变换离散傅里叶变换5.5.1 5.5.1 用用 DFT DFT 对连续时间信号进行频谱分析对连续时间信号进行频谱分析 1.1.用用用用 DFTDFT 近似分析连续时间信号的频谱近似分析连续时间信号的频谱近似分析连续时间信号的频谱近似分析连续时间信号的频谱 返回到本章向导返回到本章向导返回到本章向导返回到本章向导其频谱为：其频谱为：设连续时间非周期信号信号设连续时间非周期信号信号 ；对对 进行时域抽样进行时域抽样 得到序列得到序列 成立！成立！成立！成立！对对 截取截取N点得有限长序列点得有限长序列 ；第第4 4章章 离散傅里叶变换离散傅里叶变换5.5.1 5.5.1 5.5.1 5.5.1 用用用用 DFT DFT 对连续时间信号进行频谱分析对连续时间信号进行频谱分析对连续时间信号进行频谱分析对连续时间信号进行频谱分析 1.1.用用用用 DFTDFT 近似分析连续时间信号的频谱近似分析连续时间信号的频谱近似分析连续时间信号的频谱近似分析连续时间信号的频谱 返回到本章向导返回到本章向导返回到本章向导返回到本章向导 对对 截取截取N点得有限长序列点得有限长序列 ；近似为近似为近似为近似为 时域的离散化导致频域周期延拓时域的离散化导致频域周期延拓 近似为近似为近似为近似为表明表明表明表明：若：若 ；则用则用则用则用 分析分析分析分析 只差一个常数只差一个常数只差一个常数只差一个常数 ；第第4 4章章 离散傅里叶变换离散傅里叶变换5.5.1 5.5.1 5.5.1 5.5.1 用用用用 DFT DFT 对连续时间信号进行频谱分析对连续时间信号进行频谱分析对连续时间信号进行频谱分析对连续时间信号进行频谱分析 2.2.用用用用IDFTIDFT近似分析连续时间信号近似分析连续时间信号近似分析连续时间信号近似分析连续时间信号 返回到本章向导返回到本章向导返回到本章向导返回到本章向导在已知频谱在已知频谱 的情况下；的情况下；可以用可以用IDFT近似分析其时域信号近似分析其时域信号 ；分析过程与前面类似：分析过程与前面类似：以以 （或（或 ）为间隔对频谱）为间隔对频谱 进进行等间隔抽样并截取行等间隔抽样并截取N点，得有限长序列：点，得有限长序列：（则则 IDFT能够分析的能够分析的 频谱的最高频率为：频谱的最高频率为：（或（或 ）；）；第第4 4章章 离散傅里叶变换离散傅里叶变换5.5.1 5.5.1 5.5.1 5.5.1 用用用用 DFT DFT 对连续时间信号进行频谱分析对连续时间信号进行频谱分析对连续时间信号进行频谱分析对连续时间信号进行频谱分析 2.2.用用用用IDFTIDFT近似分析连续时间信号近似分析连续时间信号近似分析连续时间信号近似分析连续时间信号 返回到本章向导返回到本章向导返回到本章向导返回到本章向导 时域信号时域信号 近似为：近似为：频域离散化导致时域周期延拓频域离散化导致时域周期延拓 延拓周期延拓周期 对时域信号的抽样间隔为：对时域信号的抽样间隔为：第第4 4章章 离散傅里叶变换离散傅里叶变换5.5.1 5.5.1 5.5.1 5.5.1 用用用用 DFT DFT 对连续时间信号进行频谱分析对连续时间信号进行频谱分析对连续时间信号进行频谱分析对连续时间信号进行频谱分析因为因为DFT对应的数字域频率间隔为对应的数字域频率间隔为=2/N，且模拟频率，且模拟频率和数和数字频率字频率间的关系为间的关系为=，其中其中=2f。所以，离散的频率。所以，离散的频率函数函数第第k点对应的模拟频率为点对应的模拟频率为:数字域频率间隔数字域频率间隔=2/N对应的模拟域谱对应的模拟域谱线间距为线间距为 谱线间距，又称频谱分辨率谱线间距，又称频谱分辨率（单位：（单位：HzHz）。）。F是指可分辨两频率的最小间距。如设某频谱分析的是指可分辨两频率的最小间距。如设某频谱分析的F=5Hz，那么信号中，那么信号中频率相差小于频率相差小于5 Hz的两个频的两个频率分量在此频谱图中就分辨不出来。率分量在此频谱图中就分辨不出来。第第4 4章章 离散傅里叶变换离散傅里叶变换5.5.1 5.5.1 5.5.1 5.5.1 用用用用 DFT DFT 对连续时间信号进行频谱分析对连续时间信号进行频谱分析对连续时间信号进行频谱分析对连续时间信号进行频谱分析F为谱线间距，又称频谱分辨率（单位：为谱线间距，又称频谱分辨率（单位：Hz）。）。T为采样时间间隔（单位：为采样时间间隔（单位：s）；）；fs为采样频率（单位：为采样频率（单位：Hz）；）；tp为截取连续时间信号的样本长度（记录长度，单位：为截取连续时间信号的样本长度（记录长度，单位：s）；）；在实际应用中在实际应用中,要根据信号最高频率要根据信号最高频率f fh h和频谱分辨率和频谱分辨率F F的要求，的要求，来确定来确定T T、t tp p和和N N的大小。的大小。第第4 4章章 离散傅里叶变换离散傅里叶变换5.5.1 5.5.1 5.5.1 5.5.1 用用用用 DFT DFT 对连续时间信号进行频谱分析对连续时间信号进行频谱分析对连续时间信号进行频谱分析对连续时间信号进行频谱分析（1）首先，由采样定理，为保证采样信号不失真，）首先，由采样定理，为保证采样信号不失真，fs2fh(fh为为信号频率的最高频率分量，也就是前置低通滤波器阻带的截止频信号频率的最高频率分量，也就是前置低通滤波器阻带的截止频率率)，即应即应使采样周期使采样周期T满足满足（2）由频谱分辨率由频谱分辨率F和和T确定确定N,（3）最后由最后由N,T确定最小记录长度，确定最小记录长度，tp=NT。第第4 4章章 离散傅里叶变换离散傅里叶变换例：有一频谱分析用的例：有一频谱分析用的FFTFFT处理器，其采样点数必须是处理器，其采样点数必须是2 2的整数幂，的整数幂，假定没有采用任何特殊的数据处理措施，已给条件为假定没有采用任何特殊的数据处理措施，已给条件为:频率分辨率频率分辨率10 Hz;10 Hz;信号最高频率信号最高频率4kHz4kHz。试。试确定以下参量：确定以下参量：(1)(1)最小记录长度最小记录长度t tp p；(2)(2)最大采样间隔最大采样间隔T T（即最小采样频率）；（即最小采样频率）；(3)(3)在一个记录中的最少点数在一个记录中的最少点数N N。5.5.1 5.5.1 5.5.1 5.5.1 用用用用 DFT DFT 对连续时间信号进行频谱分析对连续时间信号进行频谱分析对连续时间信号进行频谱分析对连续时间信号进行频谱分析解：解：解：解：(1)(1)由分辨率的要求确定最小长度由分辨率的要求确定最小长度由分辨率的要求确定最小长度由分辨率的要求确定最小长度t tp p (2)(2)从信号的最高频率确定最大可能的采样间隔从信号的最高频率确定最大可能的采样间隔从信号的最高频率确定最大可能的采样间隔从信号的最高频率确定最大可能的采样间隔T T（即最小采样频率（即最小采样频率（即最小采样频率（即最小采样频率fsfs=1/T=1/T）。）。）。）。(3)(3)最小记录点数最小记录点数最小记录点数最小记录点数N N应满足应满足应满足应满足 第第4 4章章 离散傅里叶变换离散傅里叶变换5.5.1 5.5.1 5.5.1 5.5.1 用用用用 DFT DFT 对连续时间信号进行频谱分析对连续时间信号进行频谱分析对连续时间信号进行频谱分析对连续时间信号进行频谱分析 3.3.用用用用DFTDFT近似分析连续时间信号频谱时出现的问题近似分析连续时间信号频谱时出现的问题近似分析连续时间信号频谱时出现的问题近似分析连续时间信号频谱时出现的问题 返回到本章向导返回到本章向导返回到本章向导返回到本章向导 混叠失真混叠失真 对连续时间信号进行频谱分析时，为了避免混对连续时间信号进行频谱分析时，为了避免混叠失真，必须满足抽样定理；叠失真，必须满足抽样定理；一般应取抽样频率一般应取抽样频率 对频谱很宽或无限宽的连续时间信号，一般采用对频谱很宽或无限宽的连续时间信号，一般采用预滤波法；预滤波法；在抽样前滤除不必要的的高频分量！在抽样前滤除不必要的的高频分量！以避免抽样频率过高实现困难或频谱混叠！以避免抽样频率过高实现困难或频谱混叠！在用在用DFT对信号频谱进行近似分析时，它所能够对信号频谱进行近似分析时，它所能够分析的信号频谱的最高频率和频率分辨力之间存分析的信号频谱的最高频率和频率分辨力之间存在着矛盾；在着矛盾；第第4 4章章 离散傅里叶变换离散傅里叶变换5.5.1 5.5.1 5.5.1 5.5.1 用用用用 DFT DFT 对连续时间信号进行频谱分析对连续时间信号进行频谱分析对连续时间信号进行频谱分析对连续时间信号进行频谱分析 3.3.用用用用DFTDFT近似分析连续时间信号频谱时出现的问题近似分析连续时间信号频谱时出现的问题近似分析连续时间信号频谱时出现的问题近似分析连续时间信号频谱时出现的问题 返回到本章向导返回到本章向导返回到本章向导返回到本章向导 混叠失真混叠失真 因此，必须兼顾最高频率和频率分辨力；因此，必须兼顾最高频率和频率分辨力；因此，必须兼顾最高频率和频率分辨力；因此，必须兼顾最高频率和频率分辨力；其唯一办法就是增加记录长度的抽样点数；其唯一办法就是增加记录长度的抽样点数；其唯一办法就是增加记录长度的抽样点数；其唯一办法就是增加记录长度的抽样点数；频谱泄漏频谱泄漏频谱泄漏频谱泄漏 用用DFT分析连续时间信号持续时间很长或无限长分析连续时间信号持续时间很长或无限长的频谱时，必须进行信号的截取的频谱时，必须进行信号的截取 ！即要满足：即要满足：以得到有限长得到以得到有限长得到N点有限长序列点有限长序列 第第4 4章章 离散傅里叶变换离散傅里叶变换5.5.1 5.5.1 5.5.1 5.5.1 用用用用 DFT DFT 对连续时间信号进行频谱分析对连续时间信号进行频谱分析对连续时间信号进行频谱分析对连续时间信号进行频谱分析 返回到本章向导返回到本章向导返回到本章向导返回到本章向导 由序列傅里叶变换的卷积和定理可知，时域由序列傅里叶变换的卷积和定理可知，时域由序列傅里叶变换的卷积和定理可知，时域由序列傅里叶变换的卷积和定理可知，时域的乘积对应于频域的卷积和，的乘积对应于频域的卷积和，的乘积对应于频域的卷积和，的乘积对应于频域的卷积和，频谱泄漏频谱泄漏频谱泄漏频谱泄漏 频谱的泄漏有可能使得最高频率超过奈奎斯特频谱的泄漏有可能使得最高频率超过奈奎斯特频谱的泄漏有可能使得最高频率超过奈奎斯特频谱的泄漏有可能使得最高频率超过奈奎斯特频率，从而造成混叠失真；频率，从而造成混叠失真；频率，从而造成混叠失真；频率，从而造成混叠失真；在时域相当：在时域相当：在时域相当：在时域相当：又由于又由于 的频谱为的频谱为Sa()函数而且无限长函数而且无限长；的频谱相对于原信号频谱出现拖尾，造成的频谱相对于原信号频谱出现拖尾，造成频谱扩散；频谱扩散；频谱泄漏频谱泄漏频谱泄漏频谱泄漏一般采用变化缓慢的窗函数（如升余弦函数等）一般采用变化缓慢的窗函数（如升余弦函数等）一般采用变化缓慢的窗函数（如升余弦函数等）一般采用变化缓慢的窗函数（如升余弦函数等）取代矩形窗函数来进行截取！取代矩形窗函数来进行截取！取代矩形窗函数来进行截取！取代矩形窗函数来进行截取！第第4 4章章 离散傅里叶变换离散傅里叶变换5.5.1 5.5.1 5.5.1 5.5.1 用用用用 DFT DFT 对连续时间信号进行频谱分析对连续时间信号进行频谱分析对连续时间信号进行频谱分析对连续时间信号进行频谱分析 返回到本章向导返回到本章向导返回到本章向导返回到本章向导 DFT DFT 计算的频谱是离散的计算的频谱是离散的计算的频谱是离散的计算的频谱是离散的 ；栅栏效应栅栏效应栅栏效应栅栏效应 就好象通过一个就好象通过一个就好象通过一个就好象通过一个“栅栏栅栏栅栏栅栏”看景象一样看景象一样看景象一样看景象一样 ；而相邻谱线之间的频谱无从知晓！而相邻谱线之间的频谱无从知晓！而相邻谱线之间的频谱无从知晓！而相邻谱线之间的频谱无从知晓！减小栅栏效应的方法：减小栅栏效应的方法：减小栅栏效应的方法：减小栅栏效应的方法：谱线只限制在基频谱线只限制在基频 （频域抽样间隔）的整数（频域抽样间隔）的整数倍处；倍处；这就不能反映原信号的全部频谱特性！这就不能反映原信号的全部频谱特性！这就不能反映原信号的全部频谱特性！这就不能反映原信号的全部频谱特性！这种现象称为栅栏效应这种现象称为栅栏效应 增加频域的抽样点数，减小抽样间隔，增加频域的抽样点数，减小抽样间隔，使谱线变密使谱线变密 第第4 4章章 离散傅里叶变换离散傅里叶变换5.5.1 5.5.1 5.5.1 5.5.1 用用用用 DFT 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)|;for m=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);返回到本章向导返回到本章向导返回到本章向导返回到本章向导第第4 4章章 离散傅里叶变换离散傅里叶变换5.5.1 5.5.1 5.5.1 5.5.1 用用用用 DFT DFT 对连续时间信号进行频谱分析对连续时间信号进行频谱分析对连续时间信号进行频谱分析对连续时间信号进行频谱分析ylabel(st(m,:);if m=1 title(矩形窗截取);endend plot(fk,abs(Xk)/max(abs(Xk);程序的执行结果如图程序的执行结果如图 第第4 4章章 离散傅里叶变换离散傅里叶变换5.5.2 5.5.2 线性卷积和的分段计算法线性卷积和的分段计算法返回到本节向导返回到本节向导返回到本节向导返回到本节向导 问题的提出：问题的提出：问题的提出：问题的提出：为了能用为了能用DFT计算线性卷积和，需要将两序列计算线性卷积和，需要将两序列 和和 后补零值点加长为后补零值点加长为 ；当当 和和 的值相差很大时，这不仅加大了计的值相差很大时，这不仅加大了计算量，而且时延也可能不满足处理要求算量，而且时延也可能不满足处理要求 ；解决的方法：采用分段卷积和的计算方法解决的方法：采用分段卷积和的计算方法 基本思路为：基本思路为：基本思路为：基本思路为：先将长序列分段，使各分段的长度与短序列相近；先将长序列分段，使各分段的长度与短序列相近；然后分别计算各分段与短序列的线性卷积和然后分别计算各分段与短序列的线性卷积和；最后按照一定的方式将各分段的线性最后按照一定的方式将各分段的线性卷积和组合起来；卷积和组合起来；第第4 4章章 离散傅里叶变换离散傅里叶变换5.5.2 5.5.2 线性卷积和的分段计算法线性卷积和的分段计算法返回到本节向导返回到本节向导返回到本节向导返回到本节向导 就可以得到原长序列与短序列的线性卷积和；就可以得到原长序列与短序列的线性卷积和；就可以得到原长序列与短序列的线性卷积和；就可以得到原长序列与短序列的线性卷积和；每段长度为每段长度为 M 点，点，M 与与N的数量级相同；的数量级相同；1.1.重叠相加法重叠相加法重叠相加法重叠相加法 假设共分假设共分 r 段（最后一段若不足段（最后一段若不足M点，可以后点，可以后补零值点来补齐），即：补零值点来补齐），即：设：设：为为N点有限长序列点有限长序列 ；为为L0点有限长序列点有限长序列 ；且有：且有：现将现将 均匀分段；均匀分段；第第4 4章章 离散傅里叶变换离散傅里叶变换5.5.2 5.5.2 线性卷积和的分段计算法线性卷积和的分段计算法返回到本节向导返回到本节向导返回到本节向导返回到本节向导 表明：表明：表明：表明：首先要计算分段卷积和首先要计算分段卷积和首先要计算分段卷积和首先要计算分段卷积和 ，然后把各分段，然后把各分段，然后把各分段，然后把各分段卷积和的结果相加卷积和的结果相加卷积和的结果相加卷积和的结果相加 ；这种分段卷积法也因此称为重叠相加法这种分段卷积法也因此称为重叠相加法这种分段卷积法也因此称为重叠相加法这种分段卷积法也因此称为重叠相加法 则则 与与 的线性卷积和为：的线性卷积和为：分段卷积和分段卷积和 是是 点有限长序列，可点有限长序列，可以用以用 点点 DFT 来计算；来计算；而且每个而且每个 都与它下一分段的卷积和都与它下一分段的卷积和 有有 N-1个个 点重叠；点重叠；第第4 4章章 离散傅里叶变换离散傅里叶变换5.5.2 5.5.2 线性卷积和的分段计算法线性卷积和的分段计算法返回到本节向导返回到本节向导返回到本节向导返回到本节向导 在利用公式求和在利用公式求和在利用公式求和在利用公式求和时必须把重叠部时必须把重叠部时必须把重叠部时必须把重叠部分相加才能得到分相加才能得到分相加才能得到分相加才能得到完整的卷积和序完整的卷积和序完整的卷积和序完整的卷积和序列列列列 ；第第4 4章章 离散傅里叶变换离散傅里叶变换5.5.2 5.5.2 线性卷积和的分段计算法线性卷积和的分段计算法返回到本节向导返回到本节向导返回到本节向导返回到本节向导 例例例例 设两个有限长序列设两个有限长序列设两个有限长序列设两个有限长序列 和和和和；按分段长度按分段长度 M=7 计算线性卷积和；计算线性卷积和；用重叠相加法，用重叠相加法，解：解：按分段长度按分段长度 对对 进行分段，得：进行分段，得：分别计算各分段线性卷积和分别计算各分段线性卷积和：第第4 4章章 离散傅里叶变换离散傅里叶变换5.5.2 5.5.2 线性卷积和的分段计算法线性卷积和的分段计算法返回到本节向导返回到本节向导返回到本节向导返回到本节向导 相加（相邻段有相加（相邻段有3点重叠，需对应相加）得：点重叠，需对应相加）得：解：解：相应的相应的Matlab程序为：程序为：L0=17;nx=0:L0-1;x=2*nx+3;N=4;nh=0:N-1;h=nh+1;L=L0+N-1;x0=x,zeros(1,N-1);y=fftfilt(h,x0);ny=1:L;stem(ny-1,y,.);其中，其中，fftfilt()是采用重叠相加法是采用重叠相加法FFT计算线性卷积和计算线性卷积和Matlab函数函数 第第4 4章章 离散傅里叶变换离散傅里叶变换5.5.2 5.5.2 线性卷积和的分段计算法线性卷积和的分段计算法返回到本节向导返回到本节向导返回到本节向导返回到本节向导 重叠保留法重叠保留法重叠保留法重叠保留法 ：在对在对 分段时：分段时：各分段各分段 长度为长度为 点；点；并使每段和其前一段并使每段和其前一段 有个重叠点；有个重叠点；对于第一段对于第一段 ；由于没有前一段的重叠点，由于没有前一段的重叠点，则需在序列前补充则需在序列前补充 个零值点；个零值点；然后计算各分段然后计算各分段 与与 的的 L 点圆周卷积和点圆周卷积和 ；将前将前N-1个点删除个点删除 再将相邻段剩余部再将相邻段剩余部分依次衔接起来；分依次衔接起来；得到最终的线性卷积和得到最终的线性卷积和 第第4 4章章 离散傅里叶变换离散傅里叶变换5.5.2 5.5.2 线性卷积和的分段计算法线性卷积和的分段计算法返回到本节向导返回到本节向导返回到本节向导返回到本节向导 例例例例 设两个有限长序列设两个有限长序列设两个有限长序列设两个有限长序列 和和和和；按分段长度按分段长度 L=10 计算线性卷积和；计算线性卷积和；用重叠保留法，用重叠保留法，解：解：按分段长度按分段长度 对对 进行分段，得：进行分段，得：第第4 4章章 离散傅里叶变换离散傅里叶变换5.5.2 5.5.2 线性卷积和的分段计算法线性卷积和的分段计算法分别计算各分段分别计算各分段10点圆周卷积和点圆周卷积和：前三个前三个3点删除后依次衔接，得：点删除后依次衔接，得：第第4 4章章 离散傅里叶变换离散傅里叶变换5.2 按时间抽取的按时间抽取的基基-2 FFT算算法法 5 5、快速傅立叶变换、快速傅立叶变换第第4 4章章 离散傅里叶变换离散傅里叶变换X2(k)也可进行同样的分解：也可进行同样的分解：式中：5.2 按时间抽取的按时间抽取的基基-2 FFT算算法法 5 5、快速傅立叶变换、快速傅立叶变换第第4 4章章 离散傅里叶变换离散傅里叶变换5 5、快速傅立叶变换、快速傅立叶变换一个N=8点DFT分解为四个N/4点DFT