快速傅里叶变换：算法与应用

本书语言流畅、图文并茂，具有系统性、先进性和实用性的特点。通过使用大量图、表、框图等，本书为读者理解FFT算法提供了直观和生动的资料，并给出了的MATLAB方程和源代码。 本书深入浅出地阐述了快速傅里叶变换（FFT）的原理，系统总结了各类FFT算法，并广泛精辟地介绍了FFT在视频和音频信号处理中的各种应用。本书对FFT的理论及技术提供了全面详尽的诠释，并且采用图示和MATLAB实例的方式，易于读者加深对概念的理解。在阐述了离散傅里叶变换（DFT）的原理和性质之后，详细讨论了时域抽取（DIT）和频域抽取（DIF）的各类快速算法。论述了近似计算DFT的整数FFT、二维及多维信号FFT、非均匀DFT等原理和技术。并详细讨论了FFT的应用，给出了大量实例。每章之后附有小结、习题和课程实践。 

本书深入浅出地阐述了快速傅里叶变换（FFT）的原理，系统地总结了各类FFT算法，并广泛精辟地介绍了FFT在视频和音频信号处理中的各种应用。本书在阐述了离散傅里叶变换（DFT）的原理和性质之后，详细讨论了时域抽取（DIT）和频域抽取（DIF）的各类快速算法。论述了近似计算DFT的整数FFT、二维及多维信号FFT、非均匀DFT等原理和技术。本书还详细讨论了FFT的应用，给出了大量案例，并且附有小结、习题，还附有课程实践和参考文献。

目 录译者序 原书前言 本书结构 缩略语 第1章 简介 ………………………………………………………………………………………1 1.1 离散傅里叶变换的应用 …………………………………………………………………1 第2章 离散傅里叶变换 …………………………………………………………………………4 2.1 定义 …………………………………………………………………………………………4 2.1.1 DFT ………………………………………………………………………………………4 2.1.2 IDFT ………………………………………………………………………………………4 2.1.3 归一化DFT ………………………………………………………………………………4 2.2 Z变换 ………………………………………………………………………………………6 2.3 DFT的性质 ………………………………………………………………………………11 2.4 卷积定理 …………………………………………………………………………………16 2.4.1 乘积定理 ………………………………………………………………………………21 2.5 相关性定理 ………………………………………………………………………………21 2.6 重叠相加和重叠保留法 ………………………………………………………………24 2.6.1 重叠相加法 ……………………………………………………………………………24 2.7 数据域的补零 ……………………………………………………………………………27 2.8 使用一次复数FFT计算两个实序列的DFT ………………………………………30 2.9 利用DFT矩阵将循环矩阵对角化 …………………………………………………30 2.9.1 托普利茨（Toeplitz）矩阵 ……………………………………………………………30 2.9.2 循环矩阵 ………………………………………………………………………………31 2.9.3 利用DFT矩阵将循环矩阵对角化 ……………………………………………………31 2.10 小结 ………………………………………………………………………………………33 2.11 习题 ………………………………………………………………………………………33 2.12 课程实践 …………………………………………………………………………………36 第3章 快速算法 …………………………………………………………………………………37 3.1 基-2 DIT-FFT算法 …………………………………………………………………37 3.1.1 N =8时IFFT的稀疏矩阵因子 …………………………………………………………42 3.2 基于稀疏矩阵因式分解的快速算法 ………………………………………………44 3.3 基-2 DIF-FFT ………………………………………………………………………51 3.3.1 N =8时的DIF-FFT …………………………………………………………………52 3.3.2 原位计算 ………………………………………………………………………………56 3.4 基-3 DIT-FFT ………………………………………………………………………56 3.5 基-3 DIF-FFT ………………………………………………………………………57 3.6 N为合数时的FFT ……………………………………………………………………59 3.7 基-4 DIT-FFT ………………………………………………………………………60 3.8 基-4 DIF-FFT ………………………………………………………………………66 3.9 分裂基FFT算法 …………………………………………………………………………69 3.10 用矩阵分割技术实现快速傅里叶变换（FFT）和快速二进制傅里叶表示（BIFORE）变换 ……………………70 3.10.1 矩阵分割技术 …………………………………………………………………………71 3.10.2 DFT算法 ………………………………………………………………………………72 3.10.3 BIFORE变换（BT） …………………………………………………………………74 3.10.4 复BIFORE变换（CBT） ……………………………………………………………75 3.10.5 稀疏矩阵因式分解（SMF） …………………………………………………………75 3.11 威诺格拉德傅里叶变换算法 ………………………………………………………75 3.11.1 5点DFT ………………………………………………………………………………75 3.11.2 7点DFT ………………………………………………………………………………76 3.11.3 9点DFT ………………………………………………………………………………77 3.11.4 输入为实序列时的DFT算法 …………………………………………………………78 3.11.5 威诺格拉德短 NDFT模块 ……………………………………………………………79 3.11.6 素因子映射索引 ………………………………………………………………………81 3.11.7 威诺格拉德傅里叶变换算法（WFTA） ……………………………………………83 3.12 DFT矩阵的稀疏分解 …………………………………………………………………84 3.12.1 使用复数旋转进行DFT矩阵的稀疏分解 ……………………………………………84 3.12.2 利用酉矩阵进行DFT矩阵的稀疏分解 ………………………………………………85 3.13 统一离散傅里叶-哈特雷变换 ……………………………………………………87 3.13.1 UDFHT的快速结构 ……………………………………………………………………91 3.14 Bluestein FFT算法 ……………………………………………………………………93 3.15 Rader质数算法 …………………………………………………………………………95 3.16 小结 ………………………………………………………………………………………96 3.17 习题 ………………………………………………………………………………………97 3.18 课程实践 …………………………………………………………………………………99 第4章 整数快速傅里叶变换 ………………………………………………………………100 4.1 介绍 ………………………………………………………………………………………100 4.2 提升技术 …………………………………………………………………………………100 4.3 算法 ………………………………………………………………………………………101 4.3.1 定点运算的实现 ………………………………………………………………………105 4.4 整数离散傅里叶变换 …………………………………………………………………107 4.4.1 近完全整数DFT ………………………………………………………………………107 4.4.2 完全整数DFT …………………………………………………………………………108 4.4.3 能量守恒 ………………………………………………………………………………110 4.4.4 循环移位 ………………………………………………………………………………110 4.5 小结 ………………………………………………………………………………………112 4.6 习题 ………………………………………………………………………………………112 4.7 课程实践 …………………………………………………………………………………112 第5章 二维离散傅里叶变换 ………………………………………………………………113 5.1 定义 ………………………………………………………………………………………113 5.2 性质 ………………………………………………………………………………………116 5.2.1 周期性 …………………………………………………………………………………116 5.2.2 共轭对称 ………………………………………………………………………………116 5.2.3 时域/空域的循环移位（周期性移位） ……………………………………………117 5.2.4 频域的循环移位（周期性移位） ……………………………………………………117 5.2.5 斜特性 …………………………………………………………………………………119 5.2.6 旋转性 …………………………………………………………………………………120 5.2.7 帕斯瓦尔定理 …………………………………………………………………………120 5.2.8 卷积定理 ………………………………………………………………………………120 5.2.9 相关定理 ………………………………………………………………………………122 5.2.10 空域微分 ……………………………………………………………………………122 5.2.11 频域微分 ……………………………………………………………………………123 5.2.12 拉普拉斯算子 ………………………………………………………………………123 5.2.13 矩形方程 ……………………………………………………………………………123 5.3 二维滤波 …………………………………………………………………………………124 5.3.1 逆高斯滤波器（IGF） ………………………………………………………………126 5.3.2 根滤波器 ………………………………………………………………………………127 5.3.3 同态滤波 ………………………………………………………………………………129 5.3.4 范围压缩 ………………………………………………………………………………130 5.3.5 高斯低通滤波器 ………………………………………………………………………131 5.4 逆滤波和维纳滤波 ……………………………………………………………………131 5.4.1 维纳滤波器 ……………………………………………………………………………133 5.4.2 几何平均滤波器（GMF） ……………………………………………………………135 5.5 三维DFT ………………………………………………………………………………136 5.5.1 三维DFT ………………………………………………………………………………136 5.5.2 三维IDFT ……………………………………………………………………………136 5.5.3 三维坐标 ………………………………………………………………………………136 5.5.4 三维DFT ………………………………………………………………………………136 5.5.5 三维IDFT ……………………………………………………………………………136 5.6 一维DFT域的方差分布 ……………………………………………………………137 5.7 酉变换下的方差和不变 ………………………………………………………………138 5.8 二维DFT域的方差分布 ……………………………………………………………138 5.9 基于变换系数方差的量化 ……………………………………………………………140 5.10 方差区域采样（MVZS） ……………………………………………………144 5.11 几何区域采样（GZS） ……………………………………………………………145 5.12 小结 ……………………………………………………………………………………151 5.13 习题 ……………………………………………………………………………………151 5.14 课程实践 ………………………………………………………………………………151 第6章 矢量基二维FFT算法 ………………………………………………………………161 6.1 矢量基DIT-FFT ……………………………………………………………………161 6.2 矢量基DIF-FFT ……………………………………………………………………164 6.3 小结 ………………………………………………………………………………………168 第7章 非均匀离散傅里叶变换 ……………………………………………………………169 7.1 简介 ………………………………………………………………………………………169 7.2 一维非均匀离散傅里叶变换（NDFT） …………………………………………169 7.2.1 均匀采样序列的离散傅里叶变换 ……………………………………………………169 7.2.2 非均匀离散傅里叶变换的定义 ………………………………………………………171 7.2.3 NDFT的性质 …………………………………………………………………………173 7.2.4 NDFT-2示例 …………………………………………………………………………175 7.3 NDFT的快速算法 ……………………………………………………………………180 7.3.1 前向NDFT ……………………………………………………………………………180 7.3.2 NDFT的逆变换（INDFT） …………………………………………………………184 7.4 二维NDFT ………………………………………………………………………………188 7.4.1 二维采样结构 …………………………………………………………………………188 7.4.2 二维非均匀矩形采样的例子 …………………………………………………………191 7.5 使用NDFT设计滤波器 ………………………………………………………………192 7.5.1 低通滤波器的设计 ……………………………………………………………………192 7.5.2 非均匀低通滤波器的例子 ……………………………………………………………198 7.6 小结 ………………………………………………………………………………………201 7.7 习题 ………………………………………………………………………………………201 第8章 应用 ……………………………………………………………………………………203 8.1 频域下采样 ………………………………………………………………………………203 8.1.1 频域上采样（零插入） ………………………………………………………………206 8.2 分形图像压缩 …………………………………………………………………………207 8.3 纯相位相关 ………………………………………………………………………………211 8.4 利用DFT/FFT实现图像的旋转和平移 …………………………………………213 8.5 帧内错误隐藏 …………………………………………………………………………216 8.6 表面纹理分析 …………………………………………………………………………216 8.7 基于FFT的听觉模型 …………………………………………………………………216 8.8 图像水印 ………………………………………………………………………………… 218 8.9 音频水印 …………………………………………………………………………………219 8.9.1 使用知觉掩蔽的音频水印 ……………………………………………………………220 8.10 正交频分复用（OFDM） …………………………………………………………221 8.10.1 使用IFFT/FFT表示OFDM信号 ……………………………………………………222 8.11 OFDM的FFT处理器 ………………………………………………………………223 8.12 基于DF DFT的信道估计方法 ……………………………………………………224 8.12.1 基于DF DFT的信道估计方法 ……………………………………………………… 225 8.13 共轭梯度快速傅里叶变换（CG-FFT） ………………………………………226 8.14 改进型离散余弦变换（MDCT） …………………………………………………226 8.15 奇叠加TDAC …………………………………………………………………………235 8.16 感知变换音频编码器 ………………………………………………………………237 8.17 OCF编码器 ……………………………………………………………………………238 8.18 NMR评估系统 ………………………………………………………………………239 8.19 移动接收音频编码器 ………………………………………………………………240 8.20 高质量音乐信号的自适应功率谱感知熵编码（ASPEC） …………………241 8.21 残差激励线性预测（RELP）声码器 ……………………………………………242 8.22 同态声码器 ……………………………………………………………………………243 8.23 掩蔽模式通用子带集成编码与复用（MUSICAM） …………………………243 8.24 AC-2音频编码器 …………………………………………………………………245 8.25 利用IFFT实现IMDCT/IMDST ……………………………………………………246 8.26 利用IFFT实现MDCT/MDST ……………………………………………………249 8.27 自相关函数和功率谱密度 …………………………………………………………250 8.27.1 滤波白噪声 …………………………………………………………………………251 8.28 三维人脸识别 …………………………………………………………………………252 8.29 二维多采样率处理 …………………………………………………………………254 8.29.1 上采样与内插 ………………………………………………………………………254 8.29.2 下采样和抽取 ………………………………………………………………………257 8.30 快速均匀离散曲波（curvelet）变换（FUDCuT） …………………………261 8.30.1 Radon变换 ……………………………………………………………………………262 8.30.2 脊波（ridgelet）变换 ………………………………………………………………262 8.30.3 曲波（curvelet）变换 ………………………………………………………………263 8.31 习题 ……………………………………………………………………………………271 8.32 课程实践 ………………………………………………………………………………274 8.32.1 方向带通滤波器 ……………………………………………………………………275 附录 …………………………………………………………………………………………………277 附录A 各种离散变换的性能对比 ………………………………………………………277 A.1 变换编码增益 ……………………………………………………………………………277 A.2 变换域中的方差分布 ……………………………………………………………………278 A.3 规范化的MSE …………………………………………………………………………279 A.4 码率与失真（率失真） …………………………………………………………………279 A.5 剩余相关 …………………………………………………………………………………280 A.6 标量维纳滤波 ……………………………………………………………………………281 A.7 几何区域采样（GZS） …………………………………………………………………282 A.8 方差区域采样（MVZS） …………………………………………………………282 附录B 图像质量的谱距离评价法 ………………………………………………………283 B.1 课程实践 …………………………………………………………………………………285 附录C 整数离散余弦变换（Int DCT） ………………………………………………288 C.1 提升结构的整数DCT …………………………………………………………………288 C.1.1 利用沃尔什-哈达玛变换分解DCT ………………………………………………289 C.1.2 整数DCT的实现 ……………………………………………………………………292 C.2 利用二元对称性原理实现整数DCT …………………………………………………293 C.2.1 产生8点整数DCT …………………………………………………………………293 C.2.2 视频编码标准中的整数DCT ………………………………………………………294 C.2.3 8点整数DCT性能 …………………………………………………………………298 C.3 习题 ………………………………………………………………………………………300 C.4 课程实践 …………………………………………………………………………………301 附录D DCT和DST …………………………………………………………………………302 D.1 DCT和DST的核 …………………………………………………………………………302 D.2 酉DCT和DST的推导 …………………………………………………………………304 D.3 用DCT和DST代替FFT的循环卷积 …………………………………………………311 D.4 DCT的循环移位特性 ……………………………………………………………………312 D.5 习题 ………………………………………………………………………………………313 D.6 课程实践 …………………………………………………………………………………313 附录E 克罗内克乘积与可分离性 ………………………………………………………314 E.1 克罗内克乘积 ……………………………………………………………………………314 E.2 广义克罗内克乘积 ………………………………………………………………………315 E.3 可分离变换 3………………………………………………………………………………315 附录F 数学关系 ……………………………………………………………………………317 F.1 习题 ………………………………………………………………………………………318 附录G MATLAB基础 ………………………………………………………………………319 G.1 MATLAB相关网站列表 …………………………………………………………………325 G.1.1 MATLAB教程 ………………………………………………………………………325 G.1.2 MATLAB命令和函数 ………………………………………………………………325 G.1.3 MATLAB概要和教程 ………………………………………………………………325 G.1.4 MATLAB初级读本 …………………………………………………………………325 G.1.5 MATLAB常见问题解答（FAQ） …………………………………………………325 G.2 MATLAB相关参考文献 …………………………………………………………………326 附录H MATLAB程序示例 ………………………………………………………………328 H.1 15点的WFTA的MATLAB程序代码 …………………………………………………328 H.2 纯相位相关的MATLAB程序代码 ……………………………………………………330 参考文献 ……………………………………………………………………………………………332

原书前言 本书介绍了快速傅里叶变换（FFT）的原理，包括各类FFT算法、频域滤波及 其在视频和音频信号处理中的应用。 伴随着通信领域的高速发展，语音和图像处理及其相关领域也正在经历飞速发展。作为数字信号处理的核心技术，FFT获得了广泛的应用。因此，无论对于教师还是学生而言，都迫切需要一本介绍FFT技术的专著。 本书对FFT的重要性及其技术提供了全面、详尽的说明，并且采用了MATLAB案例和课程实践这样的新颖方式，为理解各类FFT技术提供帮助。 FFT是离散傅里叶变换（DFT）的有效实现。DFT是在数字信号处理领域中应用广泛的离散变换。DFT将时间域或空间域的数字序列映射到频率域。从初Cooley和Tukey提出的DFT方法到后来其他研究人员提出的各种增强和改进方法，DFT理论的发展激发和促进了其在各类学科中的广泛应用和飞速发展。目前已经涌现出了许多独立于Cooley-Tukey方法的算法，如素因子（prime factor）算法、分裂基（split radix）算法、向量基（vector radix）算法、分裂向量基（split vector radix）算法、Winograd傅里叶变换及整数FFT。本书将重点关注多种FFT算法，如时域抽取（decimation-in-time）FFT、频域抽取（decimation-in-frequency）FFT、整数FFT、素因子DFT等。 在众多应用中，如双音多频检测和某些特定的模式识别，相应的频谱经过扭曲后，非均匀地分布在某一区域内。在这个基本概念的基础上，简要介绍了非均匀离散傅里叶变换（Nonuniform DFT，NDFT），处理在z平面上任意间隔采样的样本。相应地，DFT对应于z平面上以原点为中心的单位圆上的等间隔采样。 许多公司都提供了实现FFT的程序，以及类似卷积/相关、滤波、频谱分析等基本应用的各类平台。并且许多通用数字信号处理（DSP）芯片可以编程实现FFT和其他离散变换。 本书适用于相关研究领域内的本科高年级学生和研究生，以及教师、工程师、科技工作者和其他自学者，有助于读者理解各类FFT算法，并将其直接有效地应用于各自的领域中。本书可以作为教材和参考书，书中的例题、习题和课程实践均与MATLAB紧密联系，有助于掌握具体概念。本书的参考文献包括了相关的书籍、综述性论文、应用列表、软硬件及有用的网址。本书通过使用大量图、表、框图和图像为读者理解快速算法的概念提供了直观和生动的资料。此外，本书还提供了的MATLAB的命令函数和程序源代码。 对本书内容的理解不需要任何关于FFT的先验知识。本书适用任何想要了解FFT发展和应用的专业技术人员。对于计划在本领域开展工作的工程技术人员来说，无论其目的是基本实现还是深入研究，本书都是一本极好的参考书。 这里，本书的作者之一D.N.Kim还要向韩国知识经济部（The Minstry of Knowledge Economy）国家信息通信产业振兴院（National Information Technology （IT）Industry Promotion Agency，NIPA）提供的IT奖学金项目致谢。