资源预览内容
第1页 / 共157页
第2页 / 共157页
第3页 / 共157页
第4页 / 共157页
第5页 / 共157页
第6页 / 共157页
第7页 / 共157页
第8页 / 共157页
第9页 / 共157页
第10页 / 共157页
亲,该文档总共157页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
离散傅里叶变换(DFT)及其快速算法 (FFT)第章第3章 离散傅里叶变换(DFT)及其快速算法(FFT)3.1 学习要点与重要公式3.2 频率域采样3.3 循环卷积和线性卷积的快速计算以及信号的频谱分析3.4 例题3.5 教材第3章习题与上机题解答3.6 教材第4章习题与上机题解答离散傅里叶变换(DFT)及其快速算法 (FFT)第章3.1 学习要点与重要公式3.1.1 学习要点(1) DFT的定义和物理意义, DFT和FT、 ZT之间的关系;(2) DFT的重要性质和定理: 隐含周期性、 循环移位性质、 共轭对称性、 实序列DFT的特点、 循环卷积定理、 离散巴塞伐尔定理;(3) 频率域采样定理;(4) FFT的基本原理及其应用。离散傅里叶变换(DFT)及其快速算法 (FFT)第章3.1.2 重要公式1) 定义k=0, 1, , N1k=0, 1, , N12) 隐含周期性离散傅里叶变换(DFT)及其快速算法 (FFT)第章3) 线性性质若,则4) 时域循环移位性质5) 频域循环移位性质离散傅里叶变换(DFT)及其快速算法 (FFT)第章6) 循环卷积定理循环卷积: L x(n)循环卷积的矩阵表示: 离散傅里叶变换(DFT)及其快速算法 (FFT)第章循环卷积定理: 若yc(n)=h(n) L x(n)则 Yc(k)=DFTyc(n)L=H(k)X(k) k=0, 1, 2, , L1其中 H(k)=DFTh(n)L, X(k)=DFTx(n)L6) 离散巴塞伐尔定理离散傅里叶变换(DFT)及其快速算法 (FFT)第章7) 共轭对称性质(1) 长度为N的共轭对称序列xep(n)与轭对称序列 xop(n):序列x(n)的共轭对称分量与共轭反对称分量:离散傅里叶变换(DFT)及其快速算法 (FFT)第章(2) 如果 x(n)=xr(n)+jxi(n)且 X(k)=Xep(k)+Xop(k)则 Xep(k)=DFTxr(n), Xop(k)=DFTjxi(n)(3) 如果x(n)=xep(n)+xop(n)且 X(k)=Xr(k)+jXi(k)则 Xr(k)=DFTxep(n), jXi(k)=DFTxop(n)(4) 实序列DFT及FT的特点: 假设x(n)是实序列, X(k)=DFTx(n), 则X(k)=X*(Nk)|X(k)|=|X(Nk)|, (k)=(Nk)离散傅里叶变换(DFT)及其快速算法 (FFT)第章3.2 频 率 域 采 样我们知道, 时域采样和频域采样各有相应的采样定理。 频域采样定理包含以下内容:(1) 设 x(n)是任意序列, X(ej)=FTx(n),对X(ej)等间隔采样得到k=0,1,2,3,N1 则离散傅里叶变换(DFT)及其快速算法 (FFT)第章(2) 如果x(n)的长度为M, 只有当频域采样点数NM时, xN(n)=x(n), 否则会发生时域混叠, xN(n)x(n)。通过频率域采样得到频域离散序列xN(k), 再对xN(k)进行IDFT得到的序列xN(n)应是原序列x(n)以采样点数N为周期进行周期化后的主值区序列, 这一概念非常重要。 离散傅里叶变换(DFT)及其快速算法 (FFT)第章(3) 如果在频率域采样的点数满足频率域采样定理, 即采样点数N大于等于序列的长度M, 则可以用频率采样得到的离散函数X(k)恢复原序列的Z变换X(z), 公式为式中 上面第一式称为z域内插公式, 第二式称为内插函数。 离散傅里叶变换(DFT)及其快速算法 (FFT)第章3.3 循环卷积和线性卷积的快速计算以及信号的频谱分析3.3.1 循环卷积的快速计算如果两个序列的长度均不很长, 可以直接采用循环卷积的矩阵乘法计算其循环卷积; 如果序列较长, 可以采用快速算法。 快速算法的理论基础是循环卷积定理。 设h(n)的长度为N, x(n)的长度为M, 计算yc(n)=h(n) L x(n)的快速算法如下:离散傅里叶变换(DFT)及其快速算法 (FFT)第章(1) 计算 k=0,1,2,3,,L1,L=maxN, M(2) 计算 Yc(k)=H(k)X(k) k=0, 1, 2, , L1(3) 计算 yc(n)=IDFTYc(k)L n=0, 1, 2, , L1说明: 如上计算过程中的DFT和IDFT均采用FFT算法时, 才称为快速算法, 否则比直接在时域计算循环卷积的运 算量大3倍以上。离散傅里叶变换(DFT)及其快速算法 (FFT)第章3.3.2 线性卷积的快速计算快速卷积法序列h(n)和x(n)的长度分别为N和M, L=N+M1, 求y(n)=h(n)*x(n)的方法如下: (1)在h(n)的尾部加LN个零点, 在x(n)的尾部加LM个零点;(2)计算L点的H(k)=FFTh(n)和L点的X(k)=FFTx(n);(3) 计算Y(k)=H(k)X(k);(4) 计算Y(n)=IFFTY(k), n=0,1,2,3,L-1。但当h(n)和x(n)中任一个的长度很长或者无限长时, 需用书上介绍的重叠相加法和重叠保留法。 离散傅里叶变换(DFT)及其快速算法 (FFT)第章3.3.3 用DFT/FFT进行频谱分析对序列进行N点的DFT/FFT就是对序列频域的N点离散采样, 采样点的频率为k=2k/N, k=0, 1, 2, , N1。 对信号进行频谱分析要关心三个问题: 频谱分辨率、 频谱分析范围和分析误差。 DFT的分辨率指的是频域采样间隔2/N, 用DFT/FFT进行频谱分析时, 在相邻采点之间的频谱是不知道的, 因此频率分辨率是一个重要指标, 希望分辨率高, 即2/N要小, DFT的变换区间N要大。离散傅里叶变换(DFT)及其快速算法 (FFT)第章当然, 截取信号的长度要足够长。 但如果截取的长度 不够长, 而依靠在所截取的序列尾部加零点, 增加变换区 间长度, 也不会提高分辨率。 例如, 分析周期序列的频谱 , 只观察了一个周期的1/4长度, 用这些数据进行DFT, 再通过尾部增加零点, 加大DFT的变换区间N, 也不能分辨 出是周期序列, 更不能得到周期序列的精确频率。 用DFT/FFT对序列进行频谱分析, 频谱分析范围为; 用DFT/FFT对模拟信号进行频谱分析, 频谱分析范围为采 样频率的一半, 即0.5Fs。 用DFT/FFT对信号进行谱分析的误差表现在三个方面, 即混叠现象、 栅栏效应和截断效应。 截断效应包括泄漏和 谱间干扰。 离散傅里叶变换(DFT)及其快速算法 (FFT)第章3.4 例 题例3.4.1 设x(n)为存在傅里叶变换的任意序列, 其Z变换为X(z),X(k)是对X(z)在单位圆上的N点等间隔采样, 即求X(k)的N点离散傅里叶逆变换(记为xN(n))与x(n)的 关系式。 解: 由题意知离散傅里叶变换(DFT)及其快速算法 (FFT)第章即X(k)是对X(ej)在0, 2上的N点等间隔采样。 由于X(ej)是以2为周期的, 所以采样序列即 以N为周期。 所以它必然与一周期序列 相对应, 为 的DFS系数。 离散傅里叶变换(DFT)及其快速算法 (FFT)第章为了导出 与x(n)之间的关系, 应将上式中的用x(n)表示: 所以离散傅里叶变换(DFT)及其快速算法 (FFT)第章因为所以即 是x(n)的周期延拓序列, 由DFT与DFS的关系可得出离散傅里叶变换(DFT)及其快速算法 (FFT)第章xN(n)=IDFTX(k)为x(n)的周期延拓序列(以N为延拓周期)的主值序列。 以后这一结论可以直接引用。 例3.4.2 已知x(n)=R8(n), X(ej)=FTx(n)对X(ej)采样得到X(k), 求离散傅里叶变换(DFT)及其快速算法 (FFT)第章解:直接根据频域采样概念得到例3.4.3 令X(k)表示x(n)的N点DFT, 分别证明: (1) 如果x(n)满足关系式x(n)=x(N1n) 则X(0)=0(2) 当N为偶数时, 如果x(n)=x(N1n) 则离散傅里叶变换(DFT)及其快速算法 (FFT)第章证 (1) 直接按DFT定义即可得证。 因为所以令n=N1m, 则式+式得离散傅里叶变换(DFT)及其快速算法 (FFT)第章所以X(0)=0(2) 因为x(n)=x(N1n), 所以令m=N1n, 则上式可写成离散傅里叶变换(DFT)及其快速算法 (FFT)第章当 时(N为偶数), 因为所以因此证得离散傅里叶变换(DFT)及其快速算法 (FFT)第章例3.4.4 有限时宽序列的N点离散傅里叶变换相当于其Z变换在单位圆上的N点等间隔采样。 我们希望求出X(z)在半径为r的圆上的N点等间隔采样, 即试给出一种用DFT计算得到 的算法。 解: 因为 离散傅里叶变换(DFT)及其快速算法 (FFT)第章所以由此可见, 先对x(n)乘以指数序列rn, 然后再进行N点DFT, 即可得到题中所要求的复频域采样 。 离散傅里叶变换(DFT)及其快速算法 (FFT)第章例3.4.5 长度为N的一个有限长序列x(n)的N点DFT为X(k)。 另一个长度为2N的序列y(n)定义为试用X(k)表示y(n)的2N点离散傅里叶变换Y(k)。解: 该题可以直接按DFT定义求解。 离散傅里叶变换(DFT)及其快速算法 (FFT)第章上面最后一步采用的是X(k)以N为周期的概念。离散傅里叶变换(DFT)及其快速算法 (FFT)第章例3.4.6 用DFT对模拟信号进行谱分析, 设模拟信号xa(t)的最高频率为200 Hz, 以奈奎斯特频率采样得到时域离散序列x(n)=xa(nT), 要求频率分辨率为10 Hz。 假设模拟信号频谱Xa(j)如图3.4.1所示, 试画出X(ej)=FTx(n)和X(k)=DFTx(n)的谱线图, 并标出每个k值对应的数字频率k和模拟频率fk的取值。 离散傅里叶变换(DFT)及其快速算法 (FFT)第章图3.4.1离散傅里叶变换(DFT)及其快速算法 (FFT)第章解: 因为最高频率fmax=200 Hz, 频率分辨率F=10 Hz, 所以采样频率fs为观察时间采样点数N=Tfs=0.1400=40个所以, 对xa(t)进行采样得x(n)=xa(nT) n=0, 1, , 39离散傅里叶变换(DFT)及其快速算法 (FFT)第章Xa(jf)、 X(ej)及X(k)N分别如图3.4.2(a)、 (b)、 (c)所示。离散傅里叶变换(DFT)及其快速算法 (FFT)第章图3.4.2离散傅里叶变换(DFT)及其快速算法 (FFT)第章当fs=2fmax时, f=fmax 对应 , 由 可求得 ; 当fs2fmax时,fmax对应的数字频率=2fmaxT。 Xa(if)与X(k)的对应关系(由图3.4.2(a)、 (c)可看出)为离散傅里叶变换(DFT)及其快速算法 (FFT)第章该例题主要说明了模拟信号xa(t)的时
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号