第三章离散傅立叶变换和快速傅立叶变换1

1、第三章 离散傅立叶变换 和快速傅立叶变换3.1 傅立叶变换概述3.2 离散傅立叶变换3.3 离散傅立叶变换的性质3.4 快速傅立叶变换傅立叶变换信号信号以时间为自变量以频率为自变量傅立叶变换逆傅立叶变换3.1 傅立叶变换概述不不 同同 形形 式式 的的 傅傅 里里 叶叶 变变 换换 对对傅 里 叶 级 数(FS)：连 续 时 间 , 离 散 频 率 的 傅 里 叶 变 换 。连 续 傅 里 叶 变 换(FT)：连 续 时 间 , 连 续 频 率 的 傅 里 叶 变 换 。序 列 的 傅 里 叶 变 换(DTFT):离 散 时 间 , 连 续 频 率 的 傅 里 叶 变 换.离 散 傅 里 叶

2、变 换(DFT):离 散 时 间 , 离 散 频 率 的 傅 里 叶 变 换3.1.1 连续时间信号的傅立叶变换1周期信号与离散频谱 周期函数：)()(nTtxtx, 3 , 2 , 1n22nnnbaAnnnab1tan其中：1000sincos)(nnntnbtnaatx100)sin(nnntnAa)(20T )()( 00ktjkejkXtx2200)(1)(T/ -T/ tjkdtetxTjkX)(tx)(0jkX周期连续时间信号 非周期离散频谱密度函数傅立叶级数FS通过 变 换 对 可 以 看 出 时 域 的 连 续 函 数 造 成 频 域 是 非 周 期 的 频 谱 函 数 ,

3、而 频 域 的 离 散 频 谱 就 与 时 域 的 周 期 时 间 函 数 对 应 。(频域采样，时域周期延 拓)二、 非周期信号与连续频谱非周期连续时间信号通过连续付里叶变换(FT)得到非周期连续频谱密度函数。条件：dttx )( )()(dtetxjXtj )(21)(dejXtxtj以下变换对可以看出时域 连 续 函 数 造成频域是非周期的谱 , 而是时域的非周期造成频域是连续的谱 . 周期信号 非周期信号1 周期信号2 非周期信号 )()( 00ktjkejkXtxnTTtjktjkdtetxTe2/2/00)(1nTTtjktjkdtetxe2/2/000)(21)2(0T0,0T,

4、00kd dedtetxtxtjtj)(21)()( jX例：窗函数解：2/02/1)(TtTttxt1-T/2T/222)()(TTdtedtetxjXtjtjdttjtTT22)sin(cossin22TTTTT2T4三 频谱分析中一些定理1 线性 )()(),()(2211fXtxfXtx)()()()(2121fXfXtxtx2 时间展缩定理)()(fXtx)(1)(kfXkktx)0( k证明：dtektxtj)(dtektxftj2)(tkt )()(2ktdetxktfj)(1kfXktX(t)A-TTtX(t/2)A-2T2TX(f)f2AT1/2T4AT1/4T3. 时移和频

5、移定理)()(fXtx)()(020fXettxftj)()(020ffXetxtfj4.卷积定理)()()()(2121fXfXtxtx)()()()(2121fXfXtxtxxjxexjxejxjxsincossincos3.1.2 离散时间信号的傅立叶变换一、离散时间傅立叶变换(DTFT)1. 定义 )()( nnj-jenxeX正变换： )(21)( deeXnxnjj反变换：Tw序列的傅立叶变换就是单位圆上的Z变换jezjzXeX)()()(nxn00)(jeX222 时域的离散造成频域的周期延拓 ,而时域的非周 期对应于频域的连续 . 2、性 质1）线性 2）时移3）卷积 )()(

6、),()(2211jjeXnxeXnx)()()()()()(2121jjjeXeXeXnxnxnx)()(00jnjeXennx);()()()(jjeHeXnhnx)()()()(jjeHeXnhnx4) 巴塞伐定理njdeXnx22)(21)( 2)(21)()(21)()(21)(21)()()()(deXdeXeXdenxeXdeeXnxnxnxnxjjjnjnjnjjnnn证明：3、应用解：)2/sin()2/sin()()(11)()(2/ ) 1(2/2/2/2/2/2/10NeeeeeeeeeeenheHNjjjjNjNjNjnjNjNnnjnjj)(exp)()()()(I

7、RjjjjeHeHeHeH)2/sin(/ )2/sin()(NeHj)2/sin()2/sin(arg2/ ) 1()()(arctan)(RINNeHeHjj)()(ndnh设矩形窗若，求系统的频率响应 , 01-0 , 1)(为其他值nNnnd上面讨论的三种傅里叶变换对 ,都不适用在计算机上运算 , 因为至少在一个域 ( 时 域 或 频 域 ) 中 , 函 数 是 连 续 的 。 因 为 从 数 字 计 算 角 度 , 我 们 感 兴 趣 的 是 时 域 及 频 域 都 是 离 散 的 情 况 。我 们 先 从 周 期 性 序 列 的 离 散 傅 里 叶 级 数(DFS) 开 始 讨 论

8、 , 然 后 在 讨 论 可 作 为 周 期 函 数 一 个 周 期 的 有 限 长 序 列 的 离 散 傅 里 叶 变 换(DFT)。二、周期序列离散傅立叶级数（DFS)1.周期序列DFS定义设 为周 期 为 N 的 周 期 序 列 , 则 其 离 散 傅 里 叶 级 数 (DFS) 变 换 对 为 : 正变换 反变换 其中：)(nx10102)()()()(NnnkNNnnkNjWnxenxnxDFSkX10102)()(1)()(NknkNNknkNjWkxekXNkXIDFSnxNjNeW22. DFS离散傅里叶级数的推导意义用数字计算机对信号进行频谱分析时，要求信号必须以离散值作为输

9、入，而且上面讨论可知：只有第四种形式(DFS)对数字信号处理有实用价值。但如果将前三种形式要么在时域上采样，要么在频域上采样，变成离散函数，就可以在计算机上应用。3. 推导正变换非周期信号x(n),其 DTFT(单位圆上Z变换)为周期连续频谱密度函数，对其进行采样，使其成为周期性离散频谱函数。设在一周期内采样N个点，则两采样点间距为：得到频间距为：代入DTFT式子中得：njnwjwenxeX)()(N2kNw212, 1 ,0Nk1022)()()(NnkNjnkNwjwenxeXkX12, 1 ,0Nk4、DFS反变换证明：已知两边同乘以 ,并对一个周期求和用n置换r得)()(nxkXIDF

10、T 102)()(NnkNjnenxkX12, 1 , 0NkkrNje2)()1)()()(10)(210210210210rxNeNnxNeenxekXNknrkNjNnrkNjNknkNjNnkrNjNk根据正交定理nrnr01102)(1)(NnknNjekXNnx12, 1 , 0NnDFS设 x(n)为周 期 为 N 的 周 期 序 列 , 则 其 离 散 傅 里 叶 级 数 (DFS) 变 换 对 为 :正 变 换 反变换其中: 10102)()()()(NnnkNNnnkNjWnxenxnxDFSkX10102)()(1)()(NknkNNknkNjWkxekXNkXIDFSn

11、xNjNeW25、性质可以由抽样Z变换来解析DFS，它的许多性质与Z变换性质类似。它们与Z变换主要区别为：(1) 与 两者具有周期性，与Z变换不同。(2)DFS在时域和频域之间具有严格的对偶关系。 它们主要性质分为：线性、序列移位(循环移位)、调制性、周期卷积和。)(nx)(kX1）线性)()()()(2121kXbkXanxbnxaDFS2）序列移位(循环、移位)时域频域)()(kXWmnxDFSmkN)()(nxWlkXIDFSnlN3）调制性)()(lkXnxWDFSnlN4）时域卷积周期卷积和与以前卷积不同，它的卷积过程限在一个周期内称为周期卷积。时域卷积等于频域相乘。频域)()()(

12、21kXkXkY10121021)()()()()()(NmNmmnxmxmnxmxkYIDFSny5）频域卷积时域：)()()(21nxnxny10121021)()(1)()(1)()(NmNlmnXmXNlkXlXNnyDFSkY四种形式的傅立叶变换为什么从DFS过渡到DFT ?在计算机上实现信号的频谱分析要求：时域和频域都是离散的；时域和频域都是有限长的。 FT, FS, DTFT, DFS都不符合要求，但是， 利用DFS时域和频域的周期性，各取一个周期就形成新的变换对。主 值(主值区间、主值序列)主 值 区 间：设 有 限 长 序 列 x(n) ,0nN-1 , 将 其 延 拓 为

13、周 期 序 列 , 周 期 序 列 长度为N, 则 的 第 一 个 周 期 n=0 到 n=N-1 的 区 间 称 为 主 值 区 间. 主 值 序 列: 设 有 限 长 序 列 x(n) , 0nN-1 , 将 其 延 拓 为 周 期 序 列 , 周 期 为 N , 则 主 值 区 间 内 的 序 列 x(n)= ,0nN-1 , 即 为 主 值 序列。)(nx)(nx)(nx)(nx3.2 离散傅立叶变换(DFT)一、离散傅立叶变换的定义1. 有限长序列 和周期序列)(nx)(nx , 01-0 , )()(为其它值nNnnxnxrrNnxnx)()()mod()(Nnxnx记作：Nnxn

14、x)()()()()(ndnxnx其中：为其他值nNnnd , 01-0 , 1)(频域周期序列 与有限长序列)k(X)(kXNkXkX)()()()()(kdkXkX周期序列实际上只有有限个序列值才有意义 ,因 而它的离散傅里叶级数表示式也适用于有限长 序列 , 这就得到有限长序列的傅里叶变换(DFT)。2. DFT的定义(1) 时 域 周 期 序 列 看 作 是 有 限 长 序 列 x(n) 的 周 期 延 拓; (2) 把频域周期序列看作是有限长序列X(k)的周期 延 拓.(3) 这 样 我 们 只 要 把 DFS 的 定 义 式 两 边 取 主 值 区 间, 就 得 到 关 于 有 限

15、 长 序 列 的 时 频 域 的 对 应 变 换 对. 这 就 是 数 字 信 号 处 理 课 程 里 最 重 要 的 变 换 - 离 散 傅 里 叶 变 换 (DFT)。正变换反变换X(k)、x(n)为有限长序列的离散付里叶变换对，已知其中一个序列就能确定另一个序列。10102)()()()(NnnkNNnnkNjWnxenxnxDFTkX10102)(1)(1)()(NknkNNknkNjWkXNekXNkXIDFTnx注意：在 离 散 傅 里 叶 变 换 关 系 中 , 有 限 长 序 列 都 作 为 周 期 序 列 的 一 个 来 表 示 , 都 隐 含 有 周 期 性 意 义。DFT

16、的图形解释截短时域采样频域采样DFSDFT, DTFT, Z变换10)()(NnnznxzXjezNnnjjzXenxeX)()()(10kNNnjnkNjeXenxkX2102)()()(Z平面K=1N/2三、频域采样定理与内插公式z变换与DFT的关系（抽样z变换）， 在此基础上引出抽样z变换的概念，并进一步深入讨论频域抽样不失真条件。频域抽样理论（频域抽样不失真条件）频域内插公式1、 z变换与DFT关系连续傅里叶变换引出离散傅里叶变换定义式。离散傅里叶变换看作是序列的傅里叶变换在 频 域 再 抽 样 后 的 变 换 对.在Z变换中,又可了解到序列的傅里叶变换就是单位圆上的Z 变 换.所以对

17、序列的傅里叶变换进行频域抽样时, 自 然可以看作是对单位圆上的 Z变换进行抽样. （1）引言（2）推导Z 变 换 的 定 义 式 (正 变 换) 重 写 如 下:取z=ejw 代 入 定 义 式, 得 到 单 位 圆 上 Z 变 换 为w是 单 位 圆 上 各 点 的 数 字 角 频 率.再 进 行 抽 样- N 等 分.这 样w=2k/N, 即w值为0,2/N,4/N,6/N, 考虑到x(n)是N点有限长序列, 因而n只需0N-1即可。将w=2k/N代入并改变上下限, 得 这正是离散傅里叶变换 (DFT)正变换定义式.nnznxzX)()(0njwnjwenxeX)()(010220)()(

18、NnnNkjNkjenxeX(3) 结论从 以 上 推 导 中 可 看 出, 有 限 长 序 列 x(n) 的 离 散 傅 里 叶 变 换 X(k) 序 列 的 各 点 值 等 于 对 x(n) 进 行 Z 变 换 后 在 单 位 圆 上 N 等 分 抽 样 的 各 点 处 所 得 的 Z 变 换 值, 即 这 就 是 Z 变 换 与 DFT 的 关 系.kNjezzXkX2)()(0有限长序列补零加长 N增加, 求其DFT。 发现频 谱包络不变,只是抽样点更密.原因:即N补零加长并不改变有限长序列本身, 因而其 Z变换不变,而只是增加了N值。 根 据 每个 X(k) 仍 等 于X0(ejw)

19、 这 一 包 络.由于0kN-1,X(k)值的个数增加了,谱线变密.kNjezzXkX2)()(02 频率抽样定理（1）问题由 Z 变 换 与 DFT 的 关 系： x(n) 的 离 散 傅 里 叶 变 换 X(k) 序 列 值 和 x(n) 的 Z 变 换 在 单 位 圆 N 个 等 分 点 上 的 抽 样 值 相 等, 这 就 是 实 现 了 频 域 的 抽 样。是否任何一序列(或说任何一个频率特性) 都能用频域抽样的办法去逼近呢? 其 限 制 条 件 是 什 么?（2）分析将x(n)的频域函数X(ejw)，按每周期 N点抽样，得到一周期序列 ,再反变换回时域，得到变换结果 ，是一周期延拓

20、的序列，且与原序列x(n) 有如下关系频 域 按 每 周 期 N 点 抽 样, 时 域 便 按 N 点 周 期 延 拓。 频域抽样 时域周期延拓)(kX)(nxNrNrNnxnx)()(（3）结论长度为M的有限长序列，频域抽样不失真的条件： 频域抽样点数N要大于或等于序列长度M，即满足NM.此时可得到长度为N(或小于N)的有限长序列可用它的z变换在单位圆上的N个均分点上的抽样值精确地表示。 )()()()()()(nxnRrNnxnRnxnxNrNNN3. 内插公式从 频 域 抽 样 不 失 真 条 件 可 以 知 道： N 个 频 域 抽 样 X(k) 能 不 失 真 的 还 原 出 长 度

21、 为 N 的 有 限 长 序 列 x(n)。 那 么 用 N 个 X(k) 也 一 定 能 完 整 地 表 示 出 X(z) 以 及 频 率 响 应 即 单 位 圆 上 的 X(z). 过 程 很 简 单, 先 把 N 个 X(k) 作 IDFT 得 到 x(n), 再 把 x(n) 作 Z 变 换 便 得 到 X(z)（1）内插公式称为内插函数其中)()()()(10zzkXzXkkNk（2）内插函数1111)(zwzNzkNNk（3）频域响应的内插公式)2()()10kNwkXeXezzNkjwjw（代替便得到用把(4) 频域响应的内插函数wNjkewwNNw)21()2sin()2sin

22、(1)(（5）说明从 公 式 中看 出: 在 每 个 抽 样 点 上X(ejw) 就 精 确 地 等 于 X(k) (因 为 其 它 的 内 插 函 数 在 这 一 点 上 的 值 为 零, 无 影 响)， 即各 抽 样 点 之 间 的X(ejw) 值, 则 由 各 抽 样 点 的 加 权 内 插 函 数 在 所 求 点 上 的 值 的 叠 加 而 得到. 频 率 响 应 的 内 插 函 数 具 有 线 性 相 位.1,.1 ,0),()2NkkXeXkNwjw（)(w3.3 离散傅立叶变换的性质在由DFS引出DFT的过程中我们知道，DFT本质上是和周期序列的DFS概念紧密相关的，因而它们在性

23、质上有着极大的相似，并由DFT隐含周期性（对应于DFS的显式周期性）所保证。DFT的性质线性对称性循环移位循环卷积设x1(n)，x2(n)都是两个有限列长为N的有限序列,它们的离散付里时变换分别为)(1)(1nxDFTkX)(2)(2nxDFTkX一、 线性x1(n) ，x2(n)的线性组合有： 其中a,b为任一常数，本性质可由定义直接证明。证：)(2)(1)(2)(1kbXkaXnbxnaxDFT)(2)( 1)(2)( 1)(2)( 1)(2)( 1101022102kbXkaXenxbenxaenbxnaxnbxnaxDFTNnNnnkNjnkNjNnnkNj说明：如果x1(n)和x2(

24、n)长度皆为N，即0nN-1范围有值，则aX1(k)+bX2(k)的长 度也是N；若x1(n)和x2(n)长度不等，设x1(n)长度为N1，x2(n)长度为N2，则ax1(n)+bx2(n)的长度应为N=maxN1，N2，故DFT必须按长度N计算。若N1频域相乘频域卷积-时域相乘)()()()(2121kXkXnxnxDFT)()()()(12121nxnxDFTkXkXN4 、采 用 DFT 办 法 求 解 线 性 卷 积引言时域循环卷积，频域是两序列的 DFT相乘。时频两域的转换 (即 DFT 及 IDFT)有快速 傅里叶变换(FFT)算法。所以利用循环卷积定理计算循环卷积比计算线性卷积的

25、计算速度快得多。实际问题中x(n) 即信号通过线性时不变系统h(n)后的响应y(n)是线 性卷积运算。线性时不变系统h(n)y(n)=x(n)*h(n)（1）循环卷积实现圆周卷积方法1设L为循环卷积点数: 设 x(n) 是 激 励，是0nN1-1 的 有 限 长 序 列；h(n)是线性时不变系统的系统函数(冲激响应)，是0nN2-1的有限长序列；y(n)是激励通过系统后的响应： 即 y(n)=x(n)* h(n)。 选好卷积点数L（L N1+N2-1）循环卷积L点圆周延拓，再取主值线性卷积（2）循环卷积实现圆周卷积方法2取L N1+N2-1情况下，循环卷积代替线性 卷积的实 际 实 现 的 框

26、 图 如 下上图依据的是循环卷积定理，做的是循环卷积。然而由于L选取符合条件，因而结果是与 线性卷积结果一致的。L点DFTh(n)L点DFTL点IDFTy(n)x(n)离散傅立叶变换在实际应用中的问题混 叠 现 象频 谱 泄 漏栅 栏 效 应一、混叠现象利 用 DFT 逼 近 连 续 时 间 信 号 的 傅 里 叶 变 换，为 避 免 混 叠 失 真，要求满足采样定理，即奈奎斯特准则： fs2fh 其中fs为采 样 频 率 , fh 为信号最高频率.但此条件只规定出fs的下限为fh , 其上限要受采样间隔 的约束。 采 样 间 隔 即 频 率 分 辨 力，它是 记 录 长 度（原模拟信号的长度

27、）的 倒 数, 即 T = 1 / 若 采 样 点 数 为 N，则 采 样 间 隔 与 fs 的 关 系 为 = fs / N 2fh /Nffff结论由 = fs / N 2fh /N 看出： 在 N 给 定 时, 为 避 免混 叠 失 真 而 一 味 提 高 抽 样 频 率 fs , 必 然 导 致 增 加, 即 频 率 分 辨 力 下 降； 反 之, 若 要 提 高 频 率 分 辨 力 即 减 小, 则 导 致 减 小fs， 最 终 必 须 减 小 信 号 的 高 频 容 量。以 上 两 点 结 论 都 是 在记录长度内采样点数 N 给 定 的 条 件 下 得 到 的. 所 以 在 高

28、频 容 量 fh 与 频 率 分 辨 力 参 数 中, 保 持 其 中 一 个 不 变 而 使 另 一 个 性 能 得 以 提 高 的 唯 一 办 法, 就 是 增 加 记 录 长 度 内 的 采样点 数 N, 即 fh 和 都 给 定 时，N 必 须 满 足 N 2fh /F这是未采用任何特殊数据处理（例如加窗）情况下，为实现基本DFT算法所必须满足条件。fffff例 1有一频谱分析仪用的FFT处理器，其抽样点数必须是2的整数幂。假定没有采用任何特殊的数据处理措施，已给条件为：（1）频率分辨力10Hz (2) 信号的最高频率4kHz试确定以下参量：（1）最小记录长度Tp；（2）采样点的最大时

29、间间隔T；（3）在一个记录中的最少点数N。解：（1）由分辨力的要求确定最小记录长度Tp。 Tp=1/ =1/10=0.1(s) 故最小记录长度为0.1秒。 （2）从信号的最高频率确定最大的抽样时间间 隔T。 fs2fh, T=1/fs 1/2fh=0.125*10-3 (s) (3)最小记录点数N，它应满足 N2fh / =800 该处理器所需最少采样点数为N=210=1024点。 （因为N=29=512点不够）ff二、频 谱 泄 漏在实际中，要把观测的信号x(n)限制在一定的时间间隔之内，即采取截断数据的过程。 时域的截断在数学上的意义为原连续时间信号乘上一个窗函数，使原连续时间函数成为两端

30、突然截断，中间为原信号与窗函数相乘的结果。时域两函数相乘，在频域是其频谱的卷积。由于窗函数不可能取无限宽，即其频谱不可能为一冲激函数，信号的频谱与窗函数的卷积必然产生拖尾现象，造成 频谱泄漏。所 以 在 截 取 (即 在 窗 函 数 的 选 取) 时，应 尽 量 选 择 适 当 形 状 的 窗 函 数 对时域信号进行截断，使频谱泄漏最小。频 谱 泄 漏注 意 点由于我们无法取无数个点，所以在DFT时，时域的截断是必然的，因而泄漏也是必然存在的。为了减少频率泄漏可采用：（1）适当加大窗口宽度，增加M值；（2）采用适当形状的窗函数截断泄漏是不能与混叠完全分开的。因为泄漏造成频谱扩展。例 2设信号为x(n)=1/2,经过矩形窗函数截断，求信号经过矩形窗函数前后的频谱函数。解：设信号经过矩形窗函数后的信号为x1(n),矩 形窗函数为W(n),其频谱函数为X1(ejw) x1(n)=x(n)W(n) X1(ejw)=X(ejw)*W (ejw)说明： X1(ejw) X(ejw) 相当