离散傅立叶变换及其快速算法.ppt

离散傅立叶变换及其快速算法,版权所有 2005年,版权所有2005 ，吉林大学通信工程学院信息科学实验室,离散傅立叶级数及其性质, 连续时间函数、连续频率的傅立叶变换 连续时间周期函数、离散频率的傅立叶变换（傅立叶级数） 离散时间函数、连续频率的傅立叶变换（序列的傅立叶变换） 离散时间函数、离散频率的傅立叶变换？,版权所有2005 ，吉林大学通信工程学院信息科学实验室,离散傅立叶级数及其性质, 离散傅立叶级数（DFS） 一个周期为 的周期序列 可以表示为 由 的周期性可知它是不能用z变换来表示的。要寻求其它的频域表示 方式。可用离散傅立叶级数来表示周期序列。 - 基频序列,版权所有2005 ，吉林大学通信工程学院信息科学实验室,（1）,离散傅立叶级数及其性质,为 次谐波系数 于是有,版权所有2005 ，吉林大学通信工程学院信息科学实验室,（2）,离散傅立叶级数及其性质,- 周期性 是周期为 的周期信号。记,版权所有2005 ，吉林大学通信工程学院信息科学实验室,周期序列及其DFS,离散傅立叶级数及其性质, 离散傅立叶级数的性质 - 线性 设周期序列 和 的周期都为 ，且 若 ，则有 - 周期序列的移位 设 ，则 类似有,版权所有2005 ，吉林大学通信工程学院信息科学实验室,离散傅立叶级数及其性质,证明：,版权所有2005 ，吉林大学通信工程学院信息科学实验室,离散傅立叶级数及其性质,- 周期卷积 和 是周期都为 的周期序列，且 令 ，则 证明：,版权所有2005 ，吉林大学通信工程学院信息科学实验室,交换律,离散傅立叶变换及其性质, 离散傅立叶变换（DFT） 将有限长序列 延拓成周期序列 。,版权所有2005 ，吉林大学通信工程学院信息科学实验室,离散傅立叶变换及其性质,有限长序列周期延拓的数学表示 其中 符号 表示 对模 的余数，即 同理有,版权所有2005 ，吉林大学通信工程学院信息科学实验室,离散傅立叶变换及其性质,- 离散傅立叶变换 离散傅立叶变换隐含着周期性。离散傅立叶级数和有限长序列的离散 傅立叶变换在本质上没有区别。前者是后者的周期延拓。后者是前者取 主值的结果。 一般情况下,版权所有2005 ，吉林大学通信工程学院信息科学实验室,离散傅立叶变换及其性质,- 离散傅立叶变换与z变换和傅立叶变换间的关系,版权所有2005 ，吉林大学通信工程学院信息科学实验室,离散傅立叶变换及其性质,- 线 性 设 ， 和 都为常数，则 - 对称性 设 是一长度为 的实序列，且 ，则有 这意味着 或,版权所有2005 ，吉林大学通信工程学院信息科学实验室,离散傅立叶变换及其性质,- 序列的循环移位 一个长度为 的序列 的 循环移位定义为 它的离散傅立叶变换为,同理,版权所有2005 ，吉林大学通信工程学院信息科学实验室,离散傅立叶变换及其性质,- 循环卷积 设 ，则 或 循环卷积计算的圆形示意,版权所有2005 ，吉林大学通信工程学院信息科学实验室,利用循环卷积计算线性卷积, 利用循环卷积计算线性卷积 许多实际问题中常要计算线性卷积。如果能将线性卷积化为循环卷 积，则可采用离散傅立叶变换来进行。可利用其快速算法。 有必要讨论在何条件下，循环卷积和线性卷积相等。 设 和 都是长度为 的有限长因果序列，它们的线性卷积为 线性卷积存在要求 的长度为 。,版权所有2005 ，吉林大学通信工程学院信息科学实验室,利用循环卷积计算线性卷积,考虑循环卷积 先将 和 延长至 ，延长部分 补零。然后将 其进行以 为周期的周期延拓，得 因此有周期卷积 可见它是 和 补零后线性卷积的周期延拓。,版权所有2005 ，吉林大学通信工程学院信息科学实验室,利用循环卷积计算线性卷积,- 用填充零值的方法将序列延长,版权所有2005 ，吉林大学通信工程学院信息科学实验室,利用循环卷积计算线性卷积,对该周期卷积取主值，得 和 补零后的循环卷积 讨论在何条件下 和 等价。 - 混叠失真 如果 ，则 的周期延拓必有非零值点相重 叠。因此， 点的循环卷积不等于 点的线性卷积； - 无混叠失真（等价） 如果 ，则 的周期延拓无重叠。 因此，可用 点的循环卷积代替 点的线性卷积。 - 一般情况 如果序列 和 的长度分别为 和 ，则条件改 为,版权所有2005 ，吉林大学通信工程学院信息科学实验室,利用循环卷积计算线性卷积,- “补零问题” 已知 为长度为 的序列，现将其补零延长至 ，得一新序列 。 求这两个序列傅立叶变换的关系。 解：由题知 的离散傅立叶变换为,版权所有2005 ，吉林大学通信工程学院信息科学实验室,频率取样, 频率取样 讨论频率特性的取样在何条件下可无失真的恢复原信号。 已知 的傅立叶反变换 取主值，有,版权所有2005 ，吉林大学通信工程学院信息科学实验室,r为任意整数,取样点数为M,频率取样,- 无混叠失真 是长度为 的序列，如果取样点数 ，那么 的周期延拓不会有混叠。这时 完全复现了原序列 。 - 混叠失真 如果取样点数 ，那么 的周期延拓有混叠。这时 不能复现原序列 。 如果 是无限长序列，则必然出现混叠失真。 当 时，z变换的取样就是离散傅立叶变换 。所以由此可 恢复原序列 还可以恢复z变换和序列的傅立叶变换，即,版权所有2005 ，吉林大学通信工程学院信息科学实验室,频率取样,整理后可得z变换的内插公式 及傅立叶变换的内插公式,版权所有2005 ，吉林大学通信工程学院信息科学实验室,内插函数,用欧拉公式,频率取样,或表示成 则内插公式 内插函数的幅度函数为 当 时，即在取样点上其值为1。而在其它取样点上其值为0。,版权所有2005 ，吉林大学通信工程学院信息科学实验室,内插函数,频率取样,- 内插函数的特性及频谱取样恢复,版权所有2005 ，吉林大学通信工程学院信息科学实验室,快速傅立叶变换（FFT）, 离散傅立叶变换的计算量 它是 级的计算复杂度。,版权所有2005 ，吉林大学通信工程学院信息科学实验室,快速傅立叶变换（FFT）,例1 讨论4点离散傅立叶变换的计算量。16次复数乘法+12次复数加法！ 将其展开有,版权所有2005 ，吉林大学通信工程学院信息科学实验室,写成矩阵形式,12次复数加法+ 2次复数乘法！,对称性,快速傅立叶变换（FFT）, 时间抽选基2FFT算法（库里-图基算法） 设 ， 为正整数，把离散时间序列按时间进行奇偶分解 只求出了N/2个点的离散傅立叶变换。,版权所有2005 ，吉林大学通信工程学院信息科学实验室,快速傅立叶变换（FFT）,后N/2个点的离散傅立叶变换为 整理有,版权所有2005 ，吉林大学通信工程学院信息科学实验室,快速傅立叶变换（FFT）,信号流图,版权所有2005 ，吉林大学通信工程学院信息科学实验室,快速傅立叶变换（FFT）,对 和 采用上述同样的奇偶分解方式，可分别得 对 、 、 和 均采用上述同样的奇偶分解方式，可分别 得N/8、N/16个点等等的离散傅立叶变换，依次类推，最后到2个点的离 散傅立叶变换结束。,版权所有2005 ，吉林大学通信工程学院信息科学实验室,快速傅立叶变换（FFT）,版权所有2005 ，吉林大学通信工程学院信息科学实验室,最后两点的离散傅立叶变换,快速傅立叶变换（FFT）,版权所有2005 ，吉林大学通信工程学院信息科学实验室,快速傅立叶变换（FFT）,版权所有2005 ，吉林大学通信工程学院信息科学实验室,FFT具有M级、N/2个碟形运算、Nlog2N计算复杂度,快速傅立叶变换（FFT）, 频率抽选基2FFT算法 设 ， 为正整数，把离散时间序列分成前后各一半。 把 按奇偶分项,版权所有2005 ，吉林大学通信工程学院信息科学实验室,快速傅立叶变换（FFT）,其中,版权所有2005 ，吉林大学通信工程学院信息科学实验室,由上两式计算N/2点DFT。在计算时仍继续遵循上述原则进行。,快速傅立叶变换（FFT）,版权所有2005 ，吉林大学通信工程学院信息科学实验室,快速傅立叶变换（FFT）,版权所有2005 ，吉林大学通信工程学院信息科学实验室,FFT具有M级、N/2个碟形运算、Nlog2N计算复杂度,快速傅立叶变换（FFT）, IFFT的计算方法,版权所有2005 ，吉林大学通信工程学院信息科学实验室,快速傅立叶变换的应用, 利用FFT计算线性卷积 已知 和 分别是长度为 和 的序列，其线性卷积可用 循环卷积来取代。计算步骤如下： - 将 和 都延长到 点， ； - 计算 和 的 点FFT 和 ； - 计算 ； - 计算 的反变换。 问题 - “补零问题”、长数据占用存储空间； - 两个序列的长度相差太大使快速计算效率下降。 可以通过分段卷积的方法来解决上述问题。,版权所有2005 ，吉林大学通信工程学院信息科学实验室,快速傅立叶变换的应用, 分段卷积 常用的方法：重叠相加法和重叠保留法,版权所有2005 ，吉林大学通信工程学院信息科学实验室,快速傅立叶变换的应用,- 重叠相加法 (Overlap Add) 将 分成长为 的 段，每段表示为 因此有限长序列 的长度是 。 计算步骤同前面。相邻两段 序列有 个点发生重叠。,版权所有2005 ，吉林大学通信工程学院信息科学实验室,用循环卷积来计算,快速傅立叶变换的应用,重叠相加法计算过程： - 计算 ； - 计算 ； - 计算 ； - 计算 ； - 计算最后输出 序列的长度为,版权所有2005 ，吉林大学通信工程学院信息科学实验室,快速傅立叶变换的应用,- 重叠保留法 (Overlap Save) 将 分解成 循环卷积 令 所以,版权所有2005 ，吉林大学通信工程学院信息科学实验室,快速傅立叶变换的应用,补零部分保留原输入信号后的局部差错 已知分段后的循环卷积为 把原来补零的地方保留原序列的值。 但是补零部分保留原输入信号后会出现 的局部差错。 因此，应该把这部分差错部分去掉。,版权所有2005 ，吉林大学通信工程学院信息科学实验室,快速傅立叶变换的应用,重叠保留法计算过程,版权所有2005 ，吉林大学通信工程学院信息科学实验室,线性调频z变换,问题的提出：只对信号的某一频段感兴趣，且要提高频率分辨率；对z 变换单位圆内极点附近的频率感兴趣。 沿螺旋线取样计算z变换，称其为线性调频z变换或Chirp z变换(CZT) 沿螺旋线取样 其中 代入z变换定义式，有,版权所有2005 ，吉林大学通信工程学院信息科学实验室,线性调频z变换,z变换的取样 计算复杂度与离散傅立叶变换相近。如果做如下变换，取 其中,版权所有2005 ，吉林大学通信工程学院信息科学实验室,二次相位复指数序列或Chirp信号,线性调频z变换,线性调频z变换的计算流程图 可以看出，CZT算法输入序列长度 和输出序列长度 可以不等，且可 以为任意数；各取样点的角度间隔可以是任意的，因而频率分辨率可以 调整；计算z变换取样点的轨迹可以不是圆而是螺旋线；取样起始点可以 任意选定，也就是可以从任意频率开始对数据进行分析。,版权所有2005 ，吉林大学通信工程学院信息科学实验室,习题课,例1 已知 是长度为 的有限长序列，且 ，设 求 与 间的关系。 例2 令 表示长度为 的序列 的离散傅立叶变换，试证明（1） 如果 满足关系式 ，则 ；（2）当 为偶 数时，如果 ，则 例3 是周期为 的周期序列， 是周期为 的周期序列。定义序 列 ，证明（1） 是周期为 的周期序列；（2） 利用 和 求出 。,版权所有2005 ，吉林大学通信工程学院信息科学实验室,习题课,例4 已知线性差分方程 （1）试求利用 点离散傅立叶变换来确定系统频率响应 在单位圆 上的 个取样点； （2）对下面的差分方程用同样方法重做 例5 如果 既是一个周期为 ，也是一个周期为 的周期序列。它 们对应的傅立叶级数的系数分别为 和 。试求出 用 表示的表达式。,版权所