《第三章离散傅里叶变换及其快速算法》由会员分享，可在线阅读，更多相关《第三章离散傅里叶变换及其快速算法（97页珍藏版）》请在金锄头文库上搜索。
1、第三章 离散傅立叶变换 数字信号处理第3章 2004 讨论 实际当中 我们在计算机上实现信号的频谱分析时 要求 时域 频域都是离散的 时域 频域都是有限长的 FT FS DTFT DFS都不符合要求 但我们可以利用DFS的时域 频域周期性 各自取一个周期 就形成新的变换对 DFT 数字信号处理第3章 2004 3 2离散傅立叶变换 DFT 3 2 1有限长序列的离散傅立叶变换一 DFT的定义长度为N的序列x n 其频谱为在上从0开始等间隔的取N个点 相应的 k 0 N 1 则上式变为 数字信号处理第3章 2004 k 0 N 1 令 并采用记号 可得有限长序列 x n n 0 1 2 N 1
2、的离散正反傅立叶变换 数字信号处理第3章 2004 离散傅立叶变换 简称DFT傅立叶反变换 简称IDFT k 0 N 1 k 0 N 1 数字信号处理第3章 2004 二 周期性以及与DFS的关系 1 余数运算表达式如果 m为整数 则有 数字信号处理第3章 2004 此运算符表示n被N除 商为m 余数为 是的解 或称作取余数 简称为对n取模值N 例如 N 8N 16 数字信号处理第3章 2004 2 有限长序列x n 和周期序列的关系有限长序列x n 是周期序列的主值序列 而是x n 的周期延拓 数字信号处理第3章 2004 3 周期序列与有限长序列的关系同样 周期序列是有限长序列的周期延拓而
3、有限长序列是周期序列的主值序列 数字信号处理第3章 2004 DFT与Z变换的关系长度为N的序列x n 其Z变换 与傅立叶变换相比较有 数字信号处理第3章 2004 可见序列的N点DFT是x n 的Z变换在单位圆上N点的等间隔采样 显然 对于同一序列当频率采样点数不同时 其DFT的值也不同 数字信号处理第3章 2004 3 2 2DFT的一些性质 一 线性性 若x n 与y n 是同样长的序列 则对任何实数或复数有 数字信号处理第3章 2004 二 循环移位性质如果那么 数字信号处理第3章 2004 图3 2 1循环移位示意图 数字信号处理第3章 2004 证明 令n m nl 则有 数字信号
4、处理第3章 2004 同理可证明频域移位定理 若则 数字信号处理第3章 2004 三 共轭复序列的DFT设为的共轭复序列 则证明 数字信号处理第3章 2004 四 共轭对称性 用和分别表示实部与虚部序列的DFT 数字信号处理第3章 2004 共轭对称性 共轭反对称性 数字信号处理第3章 2004 由于x n 和均是有限长序列 其定义区间为 0 N 1 注意 与在第二章中的对称性不同 这里所谓的对称性是指关于N 2点的对称性 而不是关于原点的对称 见右图 图3 2 2关于N 2点的共轭对称性 数字信号处理第3章 2004 若x n 为实序列 则其DFT满足共轭对称特性若x n 为纯虚序列 则其D
5、FT满足共轭反对称性 数字信号处理第3章 2004 五 循环卷积定理设和是两个具有相同长度N的有限长序列 定义循环卷积 n 0 N 1记为同时满足交换率 数字信号处理第3章 2004 循环卷积定理 若 则 数字信号处理第3章 2004 同理可以证明频域卷积定理 若则 数字信号处理第3章 2004 六 循环相关定理n 0 N 1 设两个有限长实序列 具有相同的长度N 称为序列的循环互相关 数字信号处理第3章 2004 循环相关定理 若 则有 数字信号处理第3章 2004 当x n y n 时 称为序列的循环自相关 是有限长序列的离散功率谱 注意 中没有相位的信息 数字信号处理第3章 2004 七
6、 帕思瓦定理 Parseval 帕思瓦定理的离散傅立叶变换形式 数字信号处理第3章 2004 证明 数字信号处理第3章 2004 当x n y n 时 则有 说明时域中的能量与频域中的能量相等 数字信号处理第3章 2004 3 3频域采样定理 频域采样是指对一有限序列 时间有限序列 进行DFT所得x k 也就是序列傅氏变换的采样 频域采样定理讨论两个基本问题 a 频域采样 DFT 不失真恢复的条件 即由X k 不失真地恢复x n 的条件b 用X k 表示X z 和的插值公式 数字信号处理第3章 2004 1 频域采样不失真恢复x n 的条件 采样点数N必须大于序列的长度L假定x n 的长度为L
7、 没有限制 频率采样 0 k N 1令 IDFT X k 0 n N 1 由于 DFS IDFS 数字信号处理第3章 2004 因而有取主值区 故有由上式可知 是原序列的周期延拓周期为N 然后取主值 如图3 3 1所示 数字信号处理第3章 2004 图3 3 1时域恢复示意图 结论 若序列长度为L 频域采样点数 或DFT的长度 为N 且LN 则频域采样后不能不失真地恢复原序列 数字信号处理第3章 2004 2 用表示和的内插公式 1 用表示设序列长度为N 由傅里叶变换对得 数字信号处理第3章 2004 其中 数字信号处理第3章 2004 2 用表示的内插公式将分别代入式 3 3 6 和 3 3
8、 7 即可得到用表示的内插公式如下 其中 数字信号处理第3章 2004 例 已知 0 1 对的z变换在单位圆上等间隔采样N点 k 0 N 1 求IDFT 解 数字信号处理第3章 2004 3 4DFT的快速算法 FFT 3 4 1时域抽曲基 2FFT算法 DIT FFT 所谓基 2是指要求长度N满足 M为整数 若不满足可将序列补零延长 使其满足 FFT运算分为 数字信号处理第3章 2004 1 算法的推导按n的奇偶把时间序列x n 分解为两个长为N 2点的序列 即因此 数字信号处理第3章 2004 由于所以即其中分别为的N 2点DFT这是前N 2点DFT 数字信号处理第3章 2004 图3 4
9、 1蝶式运算图 那么后N 2的DFT 由于 周期性 因此我们用蝶式运算图来表示上述前N 2和后N 2两式 如图3 4 1所示 数字信号处理第3章 2004 3 FFT算法的特点 1 倒码码位倒置是指将原二进制数的码位倒过来按从低位到高位排列如 序号4用3位二进制表示正常码为100倒码为001 变成了1顺序与倒序对照表如下 数字信号处理第3章 2004 数字信号处理第3章 2004 2 原位运算利用同一存储单元存放蝶式运算输入和输出数据的方法 3 DIF FFT算法其他形式的流图输入的数据为正序 输出是倒码排列 如下图所示 数字信号处理第3章 2004 数字信号处理第3章 2004 3 4 2频
10、域抽取基 2FFT算法 DIF FFT 1 算法 数字信号处理第3章 2004 由于N点DFT按k的奇偶分组可分为两个N 2的DFTk取偶数时 k 2r r 0 1 N 2 1 数字信号处理第3章 2004 k取奇数时 k 2r 1 r 0 1 N 2 1 2 蝶形运算和进行如下蝶形运算 数字信号处理第3章 2004 如下图 x n x n x n N 2 x n N 2 x n x n N 2 3 N 8时 按k的奇偶分解过程先蝶形运算 后DFT 数字信号处理第3章 2004 如下图 数字信号处理第3章 2004 4 DIF FFT的二次分解将N 2点DFT按k的奇偶分解为两个N 4点的DF
11、T 如此进行直到分解为2点DFT 如下图 数字信号处理第3章 2004 例如 N 8时的DFT 可以分解为两个N 2 4点DFT如图所示 数字信号处理第3章 2004 由于 因而N 2仍是偶数 可以进一步把每个N 2点的序列再按其奇偶部分分解为两个N 4的子序列从而可表示为 数字信号处理第3章 2004 因而有其中对也可进行同样的分解 k 0 1 N 4 1 数字信号处理第3章 2004 其中这样又一次的分解得到4个N 4点DFT 数字信号处理第3章 2004 如下图所示 那么依次类推 经过M 1次分解后 将N点DFT分解成N 2个两点DFT 数字信号处理第3章 2004 下图为N 8时的一个
12、完整基 2DIT FFT运算流图 数字信号处理第3章 2004 2 运算量当N 时 总共有M级分解 每级有N 4个蝶式运算 每个蝶式运算需一次复乘两次复加 这样M级总共需要的运算量为复乘次数复加次数 数字信号处理第3章 2004 3 4 3逆DFT的快速算法 IFFT 1 比较DFT与IDFT的计算公式比较两式可知只要将FFT中的旋转因子为 再乘以1 N即可得到IDFT的快速算法IFFT 数字信号处理第3章 2004 另外 可将常数1 N分配到每级运算中 因为 也就是每级蝶形运算均乘以1 22 直接利用FFT程序因为所以 数字信号处理第3章 2004 两边取共轭有 此方法只需要一个FFT程序即
13、可进行正逆变换的快速计算 数字信号处理第3章 2004 FFT IFFT 算法的实现 1 纯软件实现2 硬件实现3 DSP 软硬件结合 数字信号处理第3章 2004 3 4 4N为合数的FFT算法1 算法的实现长度N是复合数 共V个因子 令其中将x n 每隔点抽取一点 数字信号处理第3章 2004 序列x n 的N点DFT为将代入 则 数字信号处理第3章 2004 令则由于继续令如此进行下去直到最后变为点的DFT 数字信号处理第3章 2004 2 算法的运算量第一次抽取后 代替N 代替第二次抽取后 最后总运算量 数字信号处理第3章 2004 3 5DFT与FFT的应用DFT和FFT在信号和信息
14、处理的各个领域都具有广泛的应用 本节主要介绍它们在频域分析 卷积与相关计算中的应用 并讨论chirp z变换及其快速算法 数字信号处理第3章 2004 3 5 1利用FFT计算序列的频谱一 利用FFT进行频谱分析的基本方法极坐标表示 幅度谱 相位谱 数字信号处理第3章 2004 FFT对模拟信号进行频谱分析的框图如下 数字信号处理第3章 2004 1 频率分辨率 2 模拟频率分辨率 3 用于FFT的点数 4 频率刻度值 5 模拟信号长度 6 分辨率 数字信号处理第3章 2004 例3 5 1 用FFT来计算信号的频谱 已知信号的最高频率为 要求频率分辨率为 试确定 1 采样间隔T 2 采用基
15、2FFT的最小样点数N 以及与此相对应的最小记录长度 3 按你确定的参数所获得的实际分辨率 数字信号处理第3章 2004 解 1 按采样定理 采样间隔T 2 基 2FFT的最小样点数N 数字信号处理第3章 2004 当采用基 2FFT算法时 要求 与此相对应的最小记录长度为 3 按确定的参数所获得的实际分辨率 数字信号处理第3章 2004 二 用FFT进行频谱分析存在的问题1 频谱泄漏解决办法 采用其它形式的窗函数 在实际应用中 通常将所观测的信号限制在一定的时间间隔内 也就是说在时域对信号进行截断操作 或称作加时间窗 亦即用时间窗函数乘以信号 由卷积定理可知 时域相乘 频域为卷积 这就造成拖
16、尾现象 称之为频谱泄漏 数字信号处理第3章 2004 2 栅栏效应用DFT计算频谱时 只是知道为频率的整数倍处的频谱 在两个谱线之间的情况就不知道 这相当通过一个栅栏观察景象一样 故称作栅栏效应 解决办法 补零点加大周期 可使F变小来提高辨力 以减少栅栏效应 数字信号处理第3章 2004 3 5 2用FFT计算线性卷积1 利用循环卷积计算线性卷积的条件设是x n 和y n 长为L的循环卷积 其中所以 数字信号处理第3章 2004 利用循环卷积计算线性卷积如下图 数字信号处理第3章 2004 利用FFT进行线性卷积的步骤如下 1 将序列x n 和h n 补零延长 使其长度若采用基 2FFT 还应使L大于或等于的2的最小整数次幂 2 做x n 和h n 的长为L点的FFT得到X k 和Y k 求它们的积Y k X k H k 3 求Y k 的IFFT并取前N1点获得线性卷积的结果为 L N1 N M 1 N1 IFFT 0 n N 数字信号处理第3章 2004 二 长序列FFT卷积的计算方法1 重叠相加法h n 长度为N x n 长度为无限长 取M与N尽量接近x n 与y n 的卷积为 数
