《数字信号处理复习知识点(第一章到第四章)》由会员分享，可在线阅读，更多相关《数字信号处理复习知识点(第一章到第四章)（32页珍藏版）》请在金锄头文库上搜索。
1、第四章第四章 快速傅立叶变换快速傅立叶变换(FFT)一、直接用一、直接用DFTDFT计算的运算量与用计算的运算量与用FFTFFT计算的运计算的运算量比较，减少运算量的途径算量比较，减少运算量的途径二、二、FFT算法中一些概念算法中一些概念 按时间抽取法解过程的规律。按时间抽取法解过程的规律。n n1. 1.原位运算（原位运算（in-place)in-place)n n2. 2.码位倒读规则，乱序输入，顺序输出码位倒读规则，乱序输入，顺序输出（1 1）“ “级级级级” ”概念概念概念概念n n将将N N 点点DFTDFT先分成两个先分成两个N/2N/2点点DFTDFT，再是四个，再是四个N/4N
2、/4点点DFTDFT直至直至N/2N/2个两点个两点DFT.DFT.每分一次称为每分一次称为“ “一一” ”级级运算。运算。n n因为因为N=2N=2MM所以所以NN点点DFTDFT可分成可分成MM级级依次依次m=0,m=1.M-1m=0,m=1.M-1共共MM级级（2）“组”概念 每一级都有N/2个蝶形单元，例如：N=8,则每级都有4个蝶形单元。每一级的N/2个蝶形单元可以分成若干组，每一组具有相同的结构，相同的 因子分布，第m级的组数为：例：N=8=23，分3级。m=0级,分成四组,每组系数为m=1级,分成二组,每组系数为m=2级,分成一组,每组系数为(3) 因子的分布因子的分布结论：每由
3、后向前（结论：每由后向前（m由由M-1-0级）推进一级，级）推进一级，则此系数为后级系数中偶数序号的那一半。则此系数为后级系数中偶数序号的那一半。三、一个完整三、一个完整N=8的按的按DIT时间抽取时间抽取FFT的运的运算流图算流图 x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)m=0m=1m=2一个完整一个完整N=8的按的按DIF频率抽频率抽取取FFT的运算流图的运算流图 x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)m=0m=1
4、m=22.直接利用直接利用FFT流图方法的推流图方法的推导导可知：只须将频域成份一个求共轭变换，即（1）将X(k)的虚部乘以-1，即先取X(k)的共轭，得X*(k)。(2)将X*(k)直接送入FFT程序即可得出Nx*(n)。(3)最后再对运算结果取一次共轭变换，并乘以常数1/N，即可以求出IFFT变换的x(n)的值。此为DFT可用FFT程序3.用用CZT求解求解DFT的流图的流图6、说明、说明1（1）A为起始样点位置6、说明、说明2（2）zk是z平面一段螺线上的等分角上某一采样点。6、说明、说明36、说明、说明410、CZT运算量与直接运算量比较运算量与直接运算量比较当M、N足够小时，直接算法
5、运算量少。但M、N值比较大时（大于50），CZT算法比直接算法的运算量少得多。例M=50，N=50，N*M=2500次而CZT1600次。重叠相加法重叠相加法n n（1）x(n)为分段，每段长为p点，p选择与M数量组相同。用xi(n)表示x(n)的第i段.重叠保留法重叠保留法第三章第三章 离散傅立叶变换（离散傅立叶变换（DFT）一、四种不同的傅立叶变换对n n傅 里 叶 级 数(FS)：连 续 时 间 , 离 散 频 率 的 傅 里 叶 变 换 。n n连 续 傅 里 叶 变 换(FT)：连 续 时 间 , 连 续 频 率 的 傅 里 叶 变 换 。n n序 列 的 傅 里 叶 变 换(DTF
6、T):离 散 时 间 , 连 续 频 率 的 傅 里 叶 变 换.n n离 散 傅 里 叶 变 换(DFT):离 散 时 间 , 离 散 频 率 的 傅 里 叶 变 换四种付里叶变换形式的归纳四种付里叶变换形式的归纳四种付里叶变换形式的归纳四种付里叶变换形式的归纳二、二、DFS定义定义n n设 为周 期 为 N 的 周 期 序 列 , 则 其 离 散 傅 里 叶 级 数 (DFS) 变 换 对 为 :n n正 变 换n n 反变换n n其中: 三、三、三、三、DFTDFT1、定义、定义n n正变换n n反变换n nX(k)X(k)、x(n)x(n)为有限长序列的离散付里叶变换对，已知为有限长序
7、列的离散付里叶变换对，已知其中一个序列就能确定另一个序列。其中一个序列就能确定另一个序列。2、DFT性质性质n n时移特性时移特性时移特性时移特性已知已知已知已知 DFTx(n)=X(k) DFTx(n)=X(k)则则则则 DFTx(n+m) DFTx(n+m)NNR RNN(n)=W(n)=WNN-mk-mkX(k)X(k)n n频移特性频移特性设频域设频域NN点，有限长序列点，有限长序列X(k)X(k)则则3、圆、圆 周周 卷卷 积积 与与 线线 性性 卷卷 积积 的的 性性 质质 对对 比比 4、奇偶虚实关系表、奇偶虚实关系表四、频域抽样理论四、频域抽样理论n n长度为M的有限长序列,频
8、域抽样不失真的条件： 频域抽样点数N要大于或等于序列长度M, 即满足NM.此时可得到 n n 表明长度为N(或小于N)的有限长序列可用它的z变换在单位圆上的N个均分点上的抽样值精确地表示. 五、五、DFT 做做 傅傅 里里 叶叶 变变 换换 (级级 数数) 的逼的逼 近近 时时 所所 产产 生生 的的 问问 题题n n混 叠 现 象:n n频 谱 泄 漏n n栅 栏 效 应1、混、混 叠叠 现现 象象n n利 用 DFT 逼 近 连 续 时 间 信 号 的 傅 里 叶 变 换 ,为 避 免 混 叠 失 真, 要求满足抽样定理，即奈奎斯特准则： fs2fh n n其中fs为抽 样 频 率 , f
9、h 为信号最高频率.但此条件只规定出fs的下限为fh , 其上限要受抽样间隔 F的约束.n n 抽 样 间 隔 F 即 频 率 分 辨 力, 它是 记 录 长 度的 倒 数, 即 Tp = 1 / F n n若 抽 样 点 数 为 N, 则 抽 样 间 隔 与 fs 的 关 系 为 F = fs / N 2fh /N混混混混 叠叠叠叠 现现现现 象的结论象的结论象的结论象的结论n n由由F = fs / N 2fF = fs / N 2fh h /N /N 看出：看出：n n 在在 N N 给给 定定 时时, , 为为 避避 免混免混 叠叠 失失 真真 而而 一一 味味 提提 高高 抽抽 样样
10、 频频 率率 f fs s , , 必必 然然 导导 致致 F F 增增 加加, , 即即 频频 率率 分分 辨辨 力力 下下 降降; ; 反反 之之, , 若若 要要 提提 高高 频频 率率 分分 辨辨 力力 即即 减减 小小 F, F, 则则 导导 致致 减减 小小f fs s, , 最最 终终 必必 须须 减减 小小 信信 号号 的的 高高 频频 容容 量量. .n n以以 上上 两两 点点 结结 论论 都都 是是 在记录长度内抽样点数在记录长度内抽样点数 N N 给给 定定 的的 条条 件件 下下 得得 到到 的的. . 所所 以以 在在 高高 频频 容容 量量 f fh h 与与 频
11、频 率率 分分 辨辨 力力 F F 参参 数数 中中, , 保保 持持 其其 中中 一一 个个 不不 变变 而而 使使 另另 一一 个个 性性 能能 得得 以以 提提 高高 的的 唯唯 一一 办办 法法, , 就就 是是 增增 加加 记记 录录 长长 度度 内内 的的 点点 数数 N, N, 即即 f fh h 和和 F F 都都 给给 定定 时时, , 则则 N N 必必 须须 满满 足足 N 2fh /Fn n这是未采用任何特殊数据处理（例如加窗）情况下，这是未采用任何特殊数据处理（例如加窗）情况下，为实现基本为实现基本DFTDFT算法所必须满足条件。算法所必须满足条件。2、频、频 谱谱
12、泄泄 漏注漏注 意意 点点n n由于我们无法取无数个点，所以在DFT时，时域的截断是必然的，因而泄漏也是必然存在的。n n为了减少频率泄漏可采用：n n（1）适当加大窗口宽度，增加M值；n n（2）采用适当形状的窗函数截断n n指出：泄漏是不能与混叠完全分开的。3、减、减 小小 栅栅 栏栏 效效 应方应方 法法 n n减 小 栅 栏 效 应 的 一 个 方 法 是 在 所 取 数 据 的 末 端 加 一 些 零 值 点, 使 一 个 周 期 内 点 数 增 加, 但 是 不 改 变 原 有 的 记 录 数 据. n n 这种方法 等 效 于 加 长 了 周 期 Tp . 因 公 式 F = 1
13、/ Tp (F是 抽 样 间 隔). Tp 增 加, 抽 样 间 隔 变 小, 从 而 能 保 持 原 来 频 谱 形 式 不 变 的 情 况 下 使 谱 线 变 密, 也 就 使 频 谱 抽 样 点 数 增 加. n n 这 样, 原 来 看 不 到 的 频 谱 分 量 就 有 可 能 看 到 了.n n序列的傅立叶变换和性质（教材序列的傅立叶变换和性质（教材7878页，表页，表2-32-3）x(n)的傅立叶变换定义如下: 可见 还是 w的周期函数，周期为比较后可见：序序列列的的傅傅立立叶叶变变换换是是Z Z变变换换在在 时时的的Z Z变换，即变换，即Z Z变换在的单位圆上变换在的单位圆上 的特殊情况。的特殊情况。第二章第二章Z变换与离散时间傅里叶变换变换与离散时间傅里叶变换第一章离散时间信号与系统第一章离散时间信号与系统n n奈奎斯特抽样定理奈奎斯特抽样定理理想抽样输出：
