DFT以及FFT概念详解.ppt

第二章离散傅里叶变换及其快速算法 1753年 Bernoulli就推断一振动的弦可以表示成正弦加权和的形式 但是他未能给出所需的加权系数 Jean Baptiste JosephFourier于1768年3月出生在法国的Auxerre 当他8岁时不幸成了一名孤儿 Fourier对数学产生了浓厚的兴趣 21岁那年 Fourier在巴黎学术界论述了有关数值方程解的著名论作 这一工作使他在巴黎的数学界出名 1798年 拿破仑侵略埃及 在侵略队伍中一些有名的数学家和科学家 Fourier就是其中的一位 回国后 Fourier被任命为格勒诺布尔伊泽尔省的长官 就是在此期间 Fourier完成了其经典之作Theorieanalytiquedelachaleur 热能数学原理 在该著作中 他证明了任一周期函数都可以表示成正弦函数和的形式 其中正弦函数的频率为周期频率的整数倍 Fourier 离散傅里叶变换不仅具有明确的物理意义 相对于DTFT他更便于用计算机处理 但是 直至上个世纪六十年代 由于数字计算机的处理速度较低以及离散傅里叶变换的计算量较大 离散傅里叶变换长期得不到真正的应用 快速离散傅里叶变换算法的提出 才得以显现出离散傅里叶变换的强大功能 并被广泛地应用于各种数字信号处理系统中 近年来 计算机的处理速率有了惊人的发展 同时在数字信号处理领域出现了许多新的方法 但在许多应用中始终无法替代离散傅里叶变换及其快速算法 2 1离散傅里叶变换 DFT 为了便于更好地理解DFT的概念 先讨论周期序列及其离散傅里叶级数 DFS 表示 2 1 1离散傅里叶级数 DFS 一个周期为N的周期序列 即 k为任意整数 N为周期 周期序列不能进行Z变换 因为其在n 到 都周而复始永不衰减 即z平面上没有收敛域 但是 正象连续时间周期信号可用傅氏级数表达 周期序列也可用离散的傅氏级数来表示 也即用周期为N的正弦序列来表示 将周期序列展成离散傅里叶级数时 只需取k 0到 N 1 这N个独立的谐波分量 所以一个周期序列的离散傅里叶级数只需包含这N个复指数 利用正弦序列的周期性可求解系数将上式两边乘以 并对一个周期求和 k r N 8 k r N 8 上式中 部分显然只有当k r时才有值为1 其他任意k值时均为零 所以有或写为 1 可求N次谐波的系数2 也是一个由N个独立谐波分量组成的傅里叶级数3 为周期序列 周期为N 时域上周期序列的离散傅里叶级数在频域上仍是一个周期序列 是一个周期序列的离散傅里叶级数 DFS 变换对 这种对称关系可表为 习惯上 记 假设都是周期为N的两个周期序列 各自的离散傅里叶级数为 1 线性 a b为任意常数 DFS的几个主要特性 证 因为及都是以N为周期的函数 所以有 2 序列移位 由于与对称的特点 同样可证明 证 同理 对于复序列其共轭序列满足 3 共轭对称性 进一步可得 共轭偶对称分量 共轭奇对称分量 4 周期卷积若则或 周期卷积 周期为5 x n h n n n 周期卷积 x k h 0 k k y 0 n 周期卷积 x k h 1 k k y 1 n 周期卷积 x k h 2 k k y 2 n 周期卷积 x k h 3 k k y 3 n 周期卷积 x k h 4 k k y 4 n 周期卷积 y n n 先计算主值区间 再周期延拓 求得最终的周期卷积的结果 如下图所示 证 这是一个卷积公式 但与前面讨论的线性卷积的差别在于 这里的卷积过程只限于一个周期内 即m 0 N 1 称为周期卷积 例 周期为N 7 宽度分别为4和3 求周期卷积 结果仍为周期序列 周期为N 7 由于DFS与IDFS的对称性 对周期序列乘积 存在着频域的周期卷积公式 若 则 2 1 2离散傅里叶变换 DFT 我们知道周期序列实际上只有有限个序列值有意义 因此它的许多特性可推广到有限长序列上 一个有限长序列x n 长为N 为了引用周期序列的概念 假定一个周期序列 它由长度为N的有限长序列x n 延拓而成 它们的关系 周期序列的主值区间与主值序列 对于周期序列 定义其第一个周期n 0 N 1 为的 主值区间 主值区间上的序列为主值序列x n x n 与的关系可描述为 数学表示 RN n 为矩形序列 符号 n N是余数运算表达式 表示n对N求余数 例 是周期为N 8的序列 求n 11和n 2对N的余数 因此 频域上的主值区间与主值序列 周期序列的离散傅氏级数也是一个周期序列 也可给它定义一个主值区间 以及主值序列X k 数学表示 长度为N的有限长序列x n 其离散傅里叶变换X k 仍是一个长度为N的有限长序列 它们的关系为 x n 与X k 是一个有限长序列离散傅里叶变换对 已知x n 就能唯一地确定X k 同样已知X k 也就唯一地确定x n 实际上x n 与X k 都是长度为N的序列 复序列 都有N个独立值 因而具有等量的信息 有限长序列隐含着周期性 DFT的矩阵方程表示 DFT特性 以下讨论DFT的一些主要特性 这些特性都与周期序列的DFS有关 假定x n 与y n 是长度为N的有限长序列 其各自的离散傅里叶变换分别为 X k DFT x n Y k DFT y n 1 线性DFT ax n by n aX k bY k a b为任意常数 2 循环移位有限长序列x n 的循环移位定义为 f n x n m NRN n 含义 1 x n m N表示x n 的周期延拓序列的移位 2 x n m NRN n 表示对移位的周期序列x n m N取主值序列 所以f n 仍然是一个长度为N的有限长序列 f n 实际上可看作序列x n 排列在一个N等分圆周上 并顺时针旋转m位 循环移位 f n x n 2 NRN n 循环移位 移位前 左移两位后 证 利用周期序列的移位特性 实际上 利用WN mk的周期性 将f n x n m NRN n 代入DFT定义式 同样很容易证明 序列循环移位后的DFT为F k DFT f n x k 同样 对于频域有限长序列X k 的循环移位 有如下反变换特性 IDFT X k l NRN k x n 3 循环卷积若F k X k Y k 则或 证 这个卷积可看作是周期序列卷积后再取其主值序列 将F k 周期延拓 得 则根据DFS的周期卷积公式 因0 m N 1时 x m N x m 因此经过简单的换元可证明 这一卷积过程与周期卷积比较 过程是一样的 只是这里只取结果的主值序列 由于卷积过程只在主值区间0 m N 1内进行 所以实际上就是y m 的循环移位 称为 循环卷积 习惯上常用符号 表示循环卷积 以区别于线性卷积 循环卷积 x n h n n n 循环卷积 x k k y n x n h n n h 0 k 循环卷积 x k k y n x n h n n h 1 k 循环卷积 x k k y n x n h n n h 2 k 循环卷积 x k k y n x n h n n h 3 k 循环卷积 x k h 4 k k y n x n h n n 循环卷积 y n x n h n n 由有限长序列x n h n 构造周期序列 计算周期卷积 卷积结果取主值 如下图所示 同样 若f n x n y n 则 4 有限长序列的线性卷积与循环卷积 循环卷积的应用 实际问题的大多数是求解线性卷积 如信号x n 通过系统h n 其输出就是线性卷积y n x n h n 而循环卷积比起线性卷积 在运算速度上有很大的优越性 它可以采用快速傅里叶变换 FFT 技术 若能利用循环卷积求线性卷积 会带来很大的方便 现在我们来讨论上述x n 与h n 的线性卷积 如果x n h n 为有限长序列 则在什么条件下能用循环卷积代替而不产生失真 有限长序列的线性卷积 假定x n 为有限长序列 长度为N y n 为有限长序列 长度为M 它们的线性卷积f n x n y n 也应是有限长序列 因x m 的非零区间 0 m N 1 y n m 的非零区间 0 n m M 1 这两个不等式相加 得 0 n N M 2 在这区间以外不是x m 0 就是y n m 0 因而f n 0 因此 f n 是一个长度为N M 1的有限长序列 循环卷积 重新构造两个有限长序列x n y n 长度均为L max N M 序列x n 只有前N个是非零值 后L N个为补充的零值 序列y n 只有前M个是非零值 后L M个为补充的零值 为了分析x n 与y n 的循环卷积 先看x n y n 的周期延拓 根据前面的分析 f n 具有N M 1个非零序列值 因此 如果周期卷积的周期L N M 1 那么f n 周期延拓后 必然有一部分非零序列值要重叠 出现混淆现象 只有L N M 1时 才不会产生交叠 这时f n 的周期延拓中每一个周期L内 前N M 1个序列值是f n 的全部非零序列值 而剩下的L N M 1 点的序列则是补充的零值 循环卷积正是周期卷积取主值序列 所以使圆周卷积等于线性卷积而不产生混淆的必要条件是 L N M 1 比较线性卷积与循环卷积 例 设有两个序列 x n 为N 4矩形序列 y n 为M 6矩形序列 观察其线性卷积和圆周卷积 由线性卷积定义可直接验证 两者的线性卷积f n x n y n 具有N M 1 9个非零值 其结果见下图左半部分 c 不同L下的圆周卷积结果在图的右半部分 图线性卷积和循环卷积图中 d e f 反映了不同L下循环卷积与线性卷积之间的关系 图 d 中L 6 产生严重的混淆 致使fl n 与f n 已完全不同 图 e 中L 8 这时有两点 n 0 n 8 发生混淆失真 只有图 f 中 满足条件L N M 1 9 循环卷积与线性卷积相同 与图 c 比较 5 共轭对称性设x n 为x n 的共轭复数序列 则DFT x n X N k 证 DFT x n 0 k N 1由于因此 DFT x n 说明 当k 0时 应为X N 0 X 0 因为按定义X k 只有N个值 即0 k N 1 而X N 已超出主值区间 但一般已习惯于把X k 认为是分布在N等分的圆周上 它的末点就是它的起始点 即X N X 0 因此仍采用习惯表示式DFT x n X N k 以下在所有对称特性讨论中 X N 均应理解为X N X 0 同样 x N x 0 2 复序列的实部与虚部的DFT变换以xr n 和xi n 表示序列x n 的实部与虚部即x n xr n jxi n 则 Xe k 和X0 k 表示实部与虚部序列的DFT 则 显然 Xe k 与Xo k 对称性 故因此 Xe k 具有共轭对称性 称为X k 的共轭偶对称分量 用同样的方法可得到X0 k X 0 N k 即Xo k 具有共轭反对称特性 称其为X k 的共轭奇对称分量 对于纯实数序列x n 即x n xr n X k 只有共轭偶对称部分 即X k Xe k 表明实数序列的DFT满足共轭对称性 利用这一特性 只要知道一半数目的X k 就可得到另一半的X k 这一特点在DFT运算中可以加以利用 以提高运算效率 根据x n 与X k 的对称性 同样可找到X k 的实部 虚部与x n 的共轭偶部与共轭奇部的关系 分别以xe n 及x0 n 表示序列x n 的圆周共轭偶部与圆周共轭奇部 同样应从圆周意义上理解x N 0 x 0 可证明 DFT xe n Re X k DFT x0 n jIm X k 6 选频性 对 0有限制 对复指数函数进行采样得复序列x n 0 n N 1其中q为整数 当 0 2 N时 x n ej2 nq N 其离散傅里叶变换为写成闭解形式可见 当输入频率为q 0时 变换X K 的N个值中只有X q N 其余皆为零 如果输入信号为若干个不同频率的信号的组合 经离散傅里叶变换后 不同的k上 X k 将有一一对应的输出 因此 离散傅里叶变换算法实质上对频率具有选择性 例 求余弦序列 的DFT 7 DFT与Z变换有限长序列可以进行z变换比较z变换与DFT变换 可见 当z w kN时 即 图DFT与z变换 o o o o o o o o o o o X ej X k o Re z jIm z o 变量 周期 分辨率 是z平面单位圆上幅角为的点 即将z平面上的单位圆N等分后的第k点 1 X k 也就是z变换在单位圆上等间隔的采样值 2 X k 也可看作是对序列傅氏变换X ej 的采样 采样间隔为 N 2 N 即 结论 采样定律告诉我们 一个频带有限的信号 可以对它进行时域采样而不丢失任何信息 DFT变换进一步告诉我们 对于时间有限的信号 有限长序列 也可以对其进行频域采样 而不丢失任何信息 这正反应了傅立叶变换中时域 频域的对称关系 它有十分重要的意义 由于时域上的采样 使我们能够采用数字技术来处理这些时域上的信号 序列 而DFT的理论不仅在时域 而且在频域也离散化 因此使得在频域采用数字技术处理成为可能 FFT就是频域数字处理中最有成效的一例 8 DFT形式下的Parseval定理 令k 0 得到 2 2利用DFT做连续信号的频谱分析 利用DFT计算连续信号的频谱 1 混迭对连续信号xa t 进行数字处理前 要进行采样采样序列的频谱是连续信号频谱的周期延拓 周期为fs 如采样率过低 不满足采样定理 fs 2fh 则导致频谱混迭 使一个周期内的谱对原信号谱产生失真 无法恢复原信号 进一步的数字处理失去依据 2 泄漏处理实际信号序列x n 时 一般总要将它截断为一有限长序列 长为N点 相当于乘以一个矩形窗w n RN n 矩形窗函数 其频谱有主瓣 也有许多副瓣 窗口越大 主瓣越窄 当窗口趋于无穷大时 就是一个冲击函数 我们知道 时域的乘积对应频域的卷积 所以 加窗后的频谱实际是原信号频谱与矩形窗函数频谱的卷积 卷积的结果使频谱延伸到了主瓣以外 且一直延伸到无穷 当窗口无穷大时 与冲激函数的卷积才是其本身 这时无畸变 否则就有畸变 例如 信号为 是一单线谱 但当加窗后 线谱与抽样函数进行卷积 原来在 0处的一根谱线变成了以 0为中心的 形状为抽样函数的谱线序列 原来在一个周期 s 内只有一个频率上有非零值 而现在一个周期内几乎所有频率上都有非零值 即的频率成份从 0处 泄漏 到其它频率处去了 考虑各采样频率周期间频谱 泄漏 后的互相串漏 卷积后还有频谱混迭现象产生 3 栅栏效应N点DFT是在频率区间 0 2 上对信号频谱进行N点等间隔采样 得到的是若干个离散的频谱点X k 且它们限制在基频的整数倍上 这就好像在栅栏的一边通过缝隙看另一边的景象一样 只能在离散点处看到真实的景象 其余部分频谱成分被遮挡 所以称之为栅栏效应 减小栅栏效应方法 尾部补零 使谱线变密 增加频域采样点数 原来漏掉的某些频谱分量就可能被检测出来 4 DFT的分辨率 填补零值可以改变对DTFT的采样密度 人们常常有一种误解 认为补零可以提高DFT的频率分辨率 事实上我们通常规定DFT的频率分辨率为 这里的N是指信号x n 的有效长度 而不是补零的长度 不同长度的x n 其DTFT的结果是不同的 而相同长度的x n 尽管补零的长度不同其DTFT的结果应是相同的 他们的DFT只是反映了对相同的DTFT采用了不同的采样密度 参数选择的一般原则 若已知信号的最高频率 为防止混叠 选定采样频率 根据频率分辩率 确定所需DFT的长度 3 和N确定以后 即可确定相应模拟信号的时间长度这里T是采样周期 5 周期信号的谱分析 对于连续的单一频率周期信号 为信号的频率 可以得到单一谱线的DFT结果 但这是和作DFT时数据的截取长度选得是否恰当有关 截取长度N选得合理 可完全等于的采样 6 8 10 k X k a b c d 不同截取长度的正弦信号及其DFT结果