离散傅里叶变换(DFT).ppt

引言3 1离散傅里叶变换 DFT 的定义3 2离散傅里叶变换的基本性质3 3频域采样3 4DFT快速算法FFT3 5DFT的应用举例 第3章离散傅里叶变换 DFT 及其快速算法 FFT 引言 DFT与FT区别FT 序列的付里叶变换 时频对应关系DFT 序列的FT的有限点采样 也可以直接定义即DFT是FT的N点等间隔采样 频域采样定理频域采样时域周期重复 N越大 DFT包络线越逼近FTDFT变换的意义 FT是连续谱 采样离散化后便于计算机处理DFT的定义 性质及频域采样定理 FFT及其应用 3 1离散傅里叶变换的定义 DFT定义DFT与Z变换及FT的关系 DFT的物理意义DFT的周期性 DFT与DFS的关系DFT是DFS的主值区间DFT的矩阵表示 3 1离散傅里叶变换的定义 3 1 1DFT的定义设x n 是一个长度为M的有限长序列 则定义x n 的N点离散傅里叶正变换为 离散傅里叶逆变换为 离散傅里叶变换对 式中 N称为DFT变换区间长度N M 可见 DFT使有限长时域离散序列与有限长频域离散序列建立起对应关系 例1 已知 分别求和时的 解 由该例可知 频率采样点数不同 DFT的长度不同 DFT的结果也不同 图3 1 1X k 与X ej 的关系 例2 分别计算x n 的8点 16点DFT 解 x n 的8点DFT为x n 的16点DFT为 返回 是在频率区间上的等间隔采样 返回 可见 对于同一序列x n DFT变换区间长度N不同 DFT变换结果X k 不同 当N确定后 X k 与x n 一一对应的 N越大 DFT的包络线越接近FT 当N足够大 可用DFT进行谱分析 DFT的物理意义 DFT与FT的关系 X k 是x n 的频谱X ej 在 0 2 上的N点等间隔采样 采样间隔2 N 即对序列频谱的离散化 DFT与ZT的关系 X k 是x n 的Z变换X Z 在单位圆上N点等间隔采样 对序列的傅里叶变换进行频域抽样时 自然可以看作是对单位圆上的Z变换进行抽样 表达式如下 设序列x n 的长度为N 其Z变换和DFT分别为 比较上面二式可得关系式 离散频率 数字频率和模拟频率间的关系 模拟频率 离散频率 或 分别表示模拟频率与模拟角频率 单位分别为赫兹 Hz 和弧度 秒 rad s 两者关系为 离散频率 数字频率和模拟频率间的关系 数字频率 它是将离散 信号数字 频率离散化后的结果 用表示 因此可得出离散频率 数字频率和模拟频率之间的对应关系为 以上所讨论的三种频率变量之间的关系 在对模拟信号进行数字处理以及利用模拟滤波器设计数字滤波器乃至整个数字信号处理中十分重要 望同学们高度重视 3 1 2DFT的隐含周期性 DFT与DFS的关系DFT变换对中 x n 与X k 均为有限长序列 但由于WknN的周期性 都隐含周期性 且周期均为N 有限长序列是取周期序列的一个周期来表示 周期序列与有限长序列x n 的转化 x n 周期延拓 为了以后叙述方便 将 3 1 5 式用如下形式表示 N n x n N N k X k N 文字说明 图3 1 2有限长序列及其周期延拓 对任意整数m 总有均为整数因此 X k x n 隐含周期性X k 满足同理可证明x n mN x n DFT是DFS的主值区间 x n X k DFS DFT 公式说明 如果x n 的长度为N 且 n x n N 则可写出 n 的离散傅里叶级数表示为 取主值区间 DFS对 DFT对 公式说明 式 3 1 5 3 1 8 说明了DFT和DFS之间的关系 这些关系式成立的条件是N M 即DFT的变换区间N不能小于x n 的长度M 如果该条件不满足 按照式 3 1 5 将x n 进行延拓时 中将发生时域混叠 由式 3 1 8 得到的X k 不再是x n 的DFT 这时以上讲的DFS和DFT之间的关系不再成立 M为整数 M为整数 重要公式 n x n N 式中x n N表示x n 以N为周期的周期延拓序列 n N表示n对N求余 即如果n MN n1 0 n1 N 1 M为整数 则 n N n1例如 则有 3 1 3DFT的矩阵表示 周期序列的DFS以及有限长序列x n 的DFT如下可以发现它们右边的函数形式一样 当然k的定义域不同 X k 只是的主值区序列 或者说X k 以N为周期进行周期延拓即是 返回 也可以表示成矩阵形式式中 X是N点DFT频域序列向量 x是时域序列向量 DN称为N点DFT矩阵 定义为 3 1 12 返回 回到本节 也可以表示为矩阵形式 称为N点IDFT矩阵 定义为从式 3 1 12 和式 3 1 14 我们可以发现 3 1 14 返回 回到本节 3 2离散傅里叶变换的基本性质 1线性性质如果x1 n 和x2 n 是两个有限长序列 长度分别为N1和N2 y n ax1 n bx2 n 式中a b为常数 即N max N1 N2 则y n 的N点DFT为Y k DFT y n aX1 k bX2 k 0 k N 1 3 2 1 其中X1 k 和X2 k 分别为x1 n 和x2 n 的N点DFT 若N1 N2 则N N2 那么需将x1 n 补上N2 N1个零值点后变成长度为N序列 然后都作N点的DFT 2 X k x n 隐含周期性 取整数 由于 3循环移位性质 1 移位线性移位 序列沿坐标轴的平移序列的循环移位 圆周移位 设x n 为有限长序列 长度为N 则x n 的m点循环移位定义为表示将序列x N 以N为周期进行周其延拓 再左移m个单位 并取主值区间序列 图3 2 1循环移位过程示意图 有限长序列循环移位的实现步骤 序列点数不够时补零 补到所需的N点 延拓为周期序列 移位 取主值区间 2 时域循环移位定理设N点有限长序列x n 的DFT x n X k 0 k N 1则DFT x n m NRN n WN kmX k 证明 令n m n 则有 因为式中x n NWkn N 以N为周期 所以对其在任一个周期上求和的结果不变 3 频域循环移位定理设频域N点有限长序列X k 0 k N 1 则 4循环卷积定理 卷积线性卷积循环卷积 圆周卷积 圆周卷积与线性卷积的对比线卷积 反折 平移 相乘 积分 或相加 圆卷积 循环反折 循环平移 相乘 相加 线性卷积 线性卷积定义 有限长序列x1 n 0 n N1 1 x2 n 0 n N1 1则线性卷积为注意 线性卷积结果长度变为N1 N2 1 反转移位 循环卷积 圆周卷积 有限长序列x n 和h n 长度分别为N和M 循环卷积定义为 且圆周卷积结果长度不变 为L 即循环卷积亦满足交换律 循环反转循环移位 式中 L称为循环卷积的长度 L max N M 为了区别线性卷积 用表示循环卷积 用表示L点循环卷积 即h n 循环卷积 圆周卷积 的实现步骤 循环反转 循环移位 比较x n h n 线性卷积和循环卷积 圆周卷积 的不同 线性卷积与圆周卷积步骤比较1 线性卷积 圆周卷积 L 7 补零加长 2 3 1 x m 5 4 m 0 N 5 2 3 1 x m 5 4 0 L 7 m 1 线性卷积与圆周卷积步骤比较2 2 3 1 h m 0 m 2 线卷积无需周期延拓 而圆周卷积需进行周期延拓 线卷积的反折 圆卷积的反折 并取主值区间 2 3 1 2 3 1 2 3 1 h m m 0 7 线性卷积与圆周卷积步骤比较3 3 平移 2 3 1 h 1 m m 0 2 3 1 h 1 m m 0 4 相乘x m h m 5 1 5x m h 1 m 5 2 4 1 14x m h 2 m 5 3 4 2 3 1 26 2 3 1 x m 5 4 m 0 2 3 1 x m 5 4 0 N 7 m x m h 3 m 4 3 3 2 2 1 20 x m h 4 m 3 3 2 2 1 1 14x m h 5 m 2 3 1 2 8x m h 6 m 1 3 3 线性卷积与圆周卷积步骤比较4 5 相加得到线性卷积的示意图 相加得到圆周卷积的示意图 14 26 5 n y n 20 14 8 3 0 14 26 5 n y n 20 14 8 3 0 可见 线性卷积与圆周卷积相同 当N N 5 M 3 1 7时 线性卷积与圆周卷积步骤比较5 若圆周卷积取长度为L 5 则求圆周卷积 2 3 1 x m 5 4 0 N 5 m 2 3 1 h m m 0 求得圆周卷积x m h m 5 1 2 3 1 2 13x m h 1 m 5 2 4 1 1 3 17x m h 2 m 5 3 4 2 3 1 26 x m h 3 m 4 3 3 2 2 1 20 x m h 4 m 3 3 2 2 1 1 14看出圆卷积与线卷积不同 17 13 26 y n n 0 20 14 有限长序列循环卷积的矩阵形式上式中右边第一个矩阵称为x n 的L点循环矩阵 它的特点是 a 第一行是x n 的L点循环倒相 x 0 不动 后面其它反转180 放在他的后面 b 第二行是第一行向右循环移一位 c 第三行是第二行向右循环移一位 依次类推 返回 例3 2 计算下面给出的两个长度为4的序列h n 与x n 的4点和8点循环卷积 解 按照式 3 2 21 写出h n 与x n 的4点循环卷积矩阵形式为 返回 周期延拓反折移动 h n 与x n 的8点循环卷积矩阵形式为 返回 时域卷积 频域相乘频域卷积 时域相乘 自已证 2 循环卷积定理 时域卷积 频域相乘证明 直接对上式两边进行DFT 令n m n 则有 因为上式中x2 n NWkn N 以N为周期 所以对其在任一个周期上求和的结果不变 因此 用时域循环卷积定理计算两个序列循环卷积运算的方框图如下图所示 图3 2 3用DFT计算两个有限长序列L点循环卷积运算的方框图 5离散巴塞伐尔定理 设长度为N的序列x n 的N点DFT为X k 则 6复共轭序列的DFT设x n 是x n 的复共轭序列 长度为N且X k DFT x n 则DFT x n X N k 0 m N 1 3 2 6 且X N X 0 类似的 3 2 7 证明 根据DFT的唯一性 只要证明 3 2 6 式右边等于左边即可 将DFT定义式中的K用N K代替 并取共轭 又由X K 的隐含周期性有X N X 0 用同样的方法可以证明 7DFT的共轭对称性 回顾 1 序列的对称性a 奇对称 序列 和偶对称 序列 xe n xe n x0 n x0 n b DFT有限长 圆周奇对称 序列 和圆周偶对称 序列 xep n xep N n xop n xop N n c 共轭对称 序列 和共轭反对称 序列 xe n x e n xo n x o n d DFT有限长 圆周共轭对称 序列 和圆周共轭反对称 序列 xep n xep N n xop n xop N n 复 可见 a c一般序列的对称指对坐标原点的对称 而b d圆周或DFT变换对有限长序列的对称是对变称区间的中心的对称 2 序列的对称分量x n xo n xe n a 奇对称分量和偶对称分量b DFT有限长 圆周奇对称分量和圆周偶对称分量c 共轭对称分量和共轭反对称分量d DFT有限长 圆周共轭对称分量和圆周共轭反对称分量 1 有限长共轭对称序列和共轭反对称序列分别满足下式的称为有限长共轭对称序列和共轭反对称序列xep n x ep N n 0 n N 1 3 2 9 xop n x op N n 0 n N 1 3 2 10 当N为偶数时 将上式中的n换成N 2 n可得到 图3 2 3共轭对称与共轭反对称序列示意图 图中 表示对应点为序列取共轭后的值 任何有限长序列x n 都可以表示成其共轭对称分量和共轭反对称分量之和 即x n xep n xop n 0 n N 1将上式中的n换成N n 并取复共轭 得到x N n x ep N n x op N n xep n xop n xep n 1 2 x n x N n 3 2 13 xop n 1 2 x n x N n 3 2 14 2 DFT的共轭对称性 奇偶虚实 a b 复 c 实信号的DFT共轭对称性 证明 证明 说明 设x n xr n jxi n 其中xr Re x n 1 2 x n x n jxi n jIm x n 1 2 x n x n 可得DFT xr n 1 2DFT x n x n 1 2 X k X N k Xep k DFT jxi n 1 2DFT x n x n 1 2 X k X N k Xop k 由DFT的线性性质即可得X k DFT x n Xep k Xop k 其中Xep k DFT xr n X k 的共轭对称分量Xop k DFT jxi n X k 的共轭反对称分量 设x n xep n xop n 0 n N 1其中xep n 1 2 x n x N n x n 的共轭对称分量xop n 1 2 x n x N n x n 的共轭反对称分量可得DFT xep n 1 2DFT x n x N n 1 2 X k X k Re X k DFT xop n 1 2DFT x n x N n 1 2 X k X k jIm X k 因此X k DFT x n XR k jXI k 其中XR k Re X k DFT xep n jXI k jIm X k DFT xop n 设x n 是长度为N的实序列 且X k DFT x n 则 a X k X N k 0 k N 1 3 2 19 b 如果x n 实偶对称 即x n x N n 则X k 实偶对称 即X k X N k 3 2 20 c 如果x n 实奇对称 即x n x N n 则X k 纯虚奇对称 即X k X N k 3 2 21 利用DFT的共轭对称性 通过计算一个N点DFT 可以得到两个不同实序列的N点DFT 设x1 n 和x2 n 为两个实序列 构成新序列x n 如下 x n x1 n jx2 n 对x n 进行DFT 得到X k DFT x n Xep k Xop k Xep k DFT x1 n 1 2 X k X N k Xop k DFT jx2 n 1 2 X k X N k 所以X1 k DFT x1 n 1 2 X k X N k X2 k DFT x2 n j1 2 X k X N k 应用 例 已知实序列x n y n 的DFT分别为X k Y k 试给出一种计算IDFT就可得到x n y n 的计算方法 解 令w n x n jy n W k DFT w n w n IDFT W k 所以 分别取Re w n Im w n 3 3频域采样定理 将阐明 1 FT变换 z变换与DFT的关系 在此基础上引出频域采样的概念 2 频域采样理论 频域采样不失真条件 3 频域内插公式 X z X ejw x n X k xN n 采样 IDFT 分析频域采样 时域如何变换 n 关系如下 在单位圆上对X z 等间隔采样N点得到 设任意序列x n 在区间 0 2 对X ejw 等间隔N点采样或 xN n IDFT X k 0 n N 1 实质上 是对x n 的频谱函数的等间隔采样 因为以2 为周期 所以是以N为周期的频域序列 即 推导 由DFT与DFS的关系可知 X k 是xN n 以N为周期的周期延拓序列 n 的离散傅里叶级数系数的主值序列 即 而 代入上3 3 1式得 式中 为整数 其它k 所以 结论 将x n 的频域函数X ejw 按每周期N点抽样 得到一周期序列 而时域 得到变换结果 是原序列x n 周期延拓的序列 如下关系即频域按每周期N点抽样 时域便按N点周期延拓 由该式可知 是原序列的周期延拓 周期为N 然后取主值 频域抽样不失真条件结论 如果序列x n 的长度为L 则只有当频域采样点数N L时 才有xN n IDFT X k x n 可由频域采样X k 恢复原序列 否则产生时域混叠现象 这就是所谓的频域采样 定理 返回 用频域采样X k 表示X z 的内插公式和内插函数 频域内插公式 1 内插公式 2 内插函数 所谓频域内插公式 就是用频域采样表示X z 和 频域内插公式是FIR数字滤波器的频率采样结构和频率采样设计法的理论依据 推导 恢复原序列 时域上恢复x n 频域上恢复X z X ejw 从频域抽样不失真条件可以知道 N个频域抽样X k 能不失真的还原出长度为N的有限长序列x n 那么用N个X k 也一定能完整地表示出X z 以及频率响应 即单位圆上的X z 其过程 先由N个X k 作IDFT得到x n 再把x n 作Z变换便得到X z 设序列x n 长度为M 在频域0 2 之间等间隔采样N点 N M 则有 序列 所以 的z变换为 由于 将上式代入X z 的表示式中得 上式中W kNN 1 因此 内插函数 用X k 表示X z 的内插公式 当z ej 时 就成为x n 的傅里叶变换X ej 的内插函数和内插公式 即 进一步化简可得 3 3 7 3 3 8 内插函数零极点与 的幅频特性示意图 内插公式 内插函数零极点与 的幅频特性示意图 解 例 已知序列x n 1 1 4 3 n 0 1 2 3 对其频谱采样 采样频率点 的取样值为X k 求IDFT X k 解 x n 1 4 2 1 4 2 1 1 4 3 1 1 4 3 1 1 4 3 2 1 4 2 1 4 2 3 5DFT的应用举例 DFT的快速算法FFT的出现 使DFT在数字通信 语言信号处理 图像处理 功率谱估计 仿真 系统分析 雷达理论 光学 医学 地震以及数值分析等各个领域都得到广泛应用 以下面两点为基础卷积和相关系数运算作连续傅里叶变换的近似 仅介绍DFT在线性卷积和频谱分析两方面的应用 本节主要论述 3 5 1用DFT FFT 计算两个有限长序列的线性卷积 3 5 2用DFT计算有限长序列与无限长序列的线性卷积 3 5 3用DFT对序列进行谱分析 3 5 1用DFT计算两个有限长序列线性卷积 时域循环卷积 频域是两序列的DFT相乘 时频两域的转换 即DFT及IDFT 有快速傅里叶变换 FFT 算法 所以利用循环卷积定理计算循环卷积比计算卷积的计算速度快得多 实际问题中 即信号通过线性时不变系统h n 后的响应y n 是线性卷积运算 思考 若做卷积的两序列都是有限长序列 能否用它们的圆周卷积结果代替它们的线性卷积结果呢 即圆周卷积与线性卷积的关系是什么 圆周卷积 循环卷积定理 Y k DFT y n X1 k X2 k 0 k L 1 0 k L 1 用DFT计算循环卷积框图 圆周卷积与线性卷积相同的条件 L N M 1 假设h n 和x n 都是有很长序列 长度分别是N和M 其线性卷积和循环卷积分别表示如下 推导 圆周卷积与线性卷积的关系 其中 L max N M 对照线性卷积式可以看出 上式中 3 4 3 周期延拓 线性卷积 x1 n 与x2 n 的L点圆周卷积结果是其线性卷积结果yL n 以L点周期延拓后再取主值序列 如L取适当值L N M 1 则线性卷积结果yL n 被L点周期延拓后无混叠 即其主值序列 线性卷积结果 从而实现圆周卷积代替线性卷积 即当L N1 N2 1时 圆周卷积可以代替线性卷积即 从 看出 图3 4 2线性卷积与循环卷积 图3 4 3用DFT计算线性卷积框图 线性卷积 3 5 2用DFT计算有限长序列与无限长序列的线性卷积 用FFT计算有限长序列与无限长序列的线性卷积问题 h n 为某滤波器的单位脉冲响应 长度有限 输入信号x n 很长 h n 要补许多零再进行计算 计算量有很大的浪费解决方法 重叠相加法重叠保留法重叠相加法 将x n 分段 每段长度为M 然后依次计算各段与h n 的卷积 再由各段的卷积结果得到y n 返回 回到本节 设序列h n 长度为N x n 为无限长序列 将x n 均匀分段 每段长度取M 则 于是 h n 与x n 的线性卷积可表示为 3 4 4 图3 4 4重叠相加法卷积示意图 3 5 3用DFT对序列进行谱分析 本节只讨论序列的频谱分析 连续信号的谱分析下章介绍 理论依据 序列的N点DFT就是序列的频谱函数在频率区间上的N点等间隔采样 具体方法 1 根据频率分辨率要求确定DFT变换区间长度N 在数字频率域 如果要求频率分辨率为D弧度 而N点DFT意味着频谱采样间隔为2 N 即DFT能够实现的频率分辨率为2 N 因此要求2 N D 即 另外为满足基2FFT对点数N的要求 一般取 M为正整数 2 计算x n 的N点DFT 并绘制频谱图 回到本节 例 假设 用DFT分析x n 的频谱 频率分辨率为0 02 要求画出幅频特性曲线和相频特性曲线 解 1 根据频率分辨率求N 因为2 N 0 02 即N 100 取N 100 2 计算x n 的N点DFT 回到本节 的幅频特性和相频特性曲线如下图 a 和 b 所示 由上图可见 x n 的频谱变化很缓慢 所以用DFT对该信号进行谱分析时 频率分辨率可以再低一些 即N小一些 也可以得到正确的频谱 当N 16时 频率分辨率为 8 幅频特性和相频特性曲线如图3 5 4 c 和 d 所示 与N 100的情况相差很小 回到本节 课后习题 例1 求以下有限长序列的N点DFT 闭合表达式 直接用DFT公式求解X k 图3 1 1X k 与X ej 的关系 当为正整数 例2实序列x n 的8点DFT 前5个值0 25 0 125 j0 3 0 0 125 j0 5 0 1 求X k 的其它三个值 解 x n 是实序列 X k 共轭对称X N k X k X 5 X 8 5 X 3 0 125 j0 5X 6 X 2 0X 7 X 1 0 125 j0 3 2 3 因为