(39)--第4章 离散傅里叶变换.ppt
测试信号分析与处理测试信号分析与处理课程课程 第四章第四章 离散傅里叶变换及其离散傅里叶变换及其快速算法快速算法 第一节第一节 序列的傅里叶变换序列的傅里叶变换 第二节第二节 离散傅里叶级数（离散傅里叶级数（DFSDFS）第三节第三节 离散傅里叶变换（离散傅里叶变换（DFTDFT）第四节第四节 离散傅里叶变换的性质离散傅里叶变换的性质 测试信号分析与处理测试信号分析与处理课程课程第五节第五节 快速傅里叶变换快速傅里叶变换第六节第六节 IDFTIDFT的快速算法（的快速算法（IFFTIFFT）第七节第七节 实序列的实序列的FFTFFT高效算法高效算法第八节第八节 频率域采样理论频率域采样理论第一节第一节 序列的傅里叶变换序列的傅里叶变换 v如X(Z)在单位圆上是收敛的，则将在单位圆上的Z变换定义为序列的傅里叶变换，即 v非周期序列的傅里叶变换（频谱）的特点在于它是周期为 的连续周期函数，其周期为 。第二节第二节 离散傅里叶级数（离散傅里叶级数（DFS）一、傅里叶变换在时域和频域中的对称规律一、傅里叶变换在时域和频域中的对称规律v 第二节第二节 离散傅里叶级数（离散傅里叶级数（DFS）v 第二节第二节 离散傅里叶级数（离散傅里叶级数（DFS）v一个域中（时域或频域）是连续的，对应另一个域中（频域或时域）是非周期的。v一个域中（时域或频域）是离散的，对应另一个域中（频域或时域）是周期的。第二节第二节 离散傅里叶级数（离散傅里叶级数（DFS）二、离散傅里叶级数二、离散傅里叶级数v离散周期信号的频谱，即离散傅里叶级数(DFS)。v离散傅里叶级数的变换对表达式 第三节第三节 离散傅里叶变换（离散傅里叶变换（DFT）一、离散傅里叶变换一、离散傅里叶变换DFT定义式定义式v离散傅里叶变换就是对有限长序列进行傅里叶变换的表示式。正变换反变换 第三节第三节 离散傅里叶变换（离散傅里叶变换（DFT）v矩阵形式或 第三节第三节 离散傅里叶变换（离散傅里叶变换（DFT）二、二、DFT的物理意义的物理意义 v有限长序列的DFT就是序列在单位圆上的Z变换（即有限长序列的傅里叶变换或频谱）以 为间隔的抽样值 第四节第四节 离散傅里叶变换的性质离散傅里叶变换的性质v线性特性线性特性 v时移特性时移特性 1）圆周移位序列2）时移定理v频移特性频移特性 第四节第四节 离散傅里叶变换的性质离散傅里叶变换的性质v圆周卷积特性 1）时域圆周卷积 2）频域圆卷积 若v实数序列奇偶性（对称性）v 帕斯瓦尔定理：变换过程中能量是守恒的。第五节第五节 快速傅里叶变换快速傅里叶变换一、一、DFT运算的特点运算的特点1 的周期性2 的对称性 第五节第五节 快速傅里叶变换快速傅里叶变换二、基二、基2时析型时析型FFT算法（时间抽取法）算法（时间抽取法）1.1.算法原理算法原理 对长度为对长度为 （L L为正整数，若原序列的长为正整数，若原序列的长度不满足此条件，则可用零补足）的序列度不满足此条件，则可用零补足）的序列x(nx(n),),按按序列各项序号的奇偶将序列分成两个子序列（大点序列各项序号的奇偶将序列分成两个子序列（大点数化为小点数），有数化为小点数），有偶序号序列偶序号序列 奇序号序列奇序号序列X(nX(n)的的DFTDFT最后结果最后结果 第五节第五节 快速傅里叶变换快速傅里叶变换2.2.算法的具体实现算法的具体实现 第五节第五节 快速傅里叶变换快速傅里叶变换3.3.流程图规律流程图规律1)1)2 2）L L级蝶形运算，每一级都是级蝶形运算，每一级都是“同址运算同址运算”蝶群序号蝶群序号蝶距（序号蝶距（序号差）差）蝶群宽（点蝶群宽（点数）数）蝶群数蝶群数第一级（第一级（2点点DFT）第第i级（级（点点DFT)第五节第五节 快速傅里叶变换快速傅里叶变换3 3）每个蝶形单元的运算，都包括乘）每个蝶形单元的运算，都包括乘 ，并，并与相应的与相应的DFTDFT结果加减各一次结果加减各一次 4 4）同一级中，）同一级中，的分布规律相同的分布规律相同第第i i级级(点点DFT):;.;DFT):;.;第五节第五节 快速傅里叶变换快速傅里叶变换序列输入的自然顺序十进制二进制码码位倒置结果（二进制码）乱序十进制序列乱序的输入顺序5）输入重排）输入重排 第五节第五节 快速傅里叶变换快速傅里叶变换4.4.运算量比较运算量比较N N（）点的）点的FFTFFT总运算量为总运算量为复数乘复数乘复数加复数加 利用基利用基2 2时析型时析型FFTFFT求序列的求序列的DFTDFT同直接计算同直接计算序列的序列的DFTDFT的复数乘运算次数之比为的复数乘运算次数之比为第六节第六节 IDFTIDFT的快速算法（的快速算法（IFFTIFFT）一、一、IFFTIFFT算法算法在在FFTFFT的时间抽取算法中，第一次分解的结果是的时间抽取算法中，第一次分解的结果是 第六节第六节 IDFTIDFT的快速算法（的快速算法（IFFTIFFT）第七节第七节 实序列的实序列的FFT高效算法高效算法v同时计算两组实序列的同时计算两组实序列的DFTDFT v用用N N点序列的点序列的DFTDFT结果获得结果获得2N2N点长实序列的点长实序列的DFTDFT结果结果 第八节第八节 频率域采样理论频率域采样理论v频域采样定理 如果序列x(n)的长度为M,则只有当频域采样点数 时，才有即可由频域采样 X(k)恢复原序列x(n)，否则产生时域混叠现象。
