CE7453 Numerical Algorithms 期末高分超详细攻略（第七章：Fourier Transform）

本章内容：离散傅里叶变换（DFT）、快速傅里叶变换（FFT）、三角插值、JPEG应用
适用对象：零基础/考前冲刺/快速查漏补缺
内容特色：详细原理、公式推导、算法流程、例题全解、英文关键词

1. 基本概念与背景

• 傅里叶变换（Fourier Transform）：将信号从时域变换到频域，分析信号的频率成分。
• 离散傅里叶变换（DFT）：对有限长离散信号进行傅里叶变换，常用于数字信号处理、图像压缩等。
• 快速傅里叶变换（FFT）：高效计算DFT的算法，大幅降低运算量。
• 实际应用：音频分析、图像处理（如JPEG压缩）、通信、工程仿真等。

2. 离散傅里叶变换（DFT）

2.1 公式与推导

• DFT公式：
  $$X_k=\sum _{n=0}^{N-1}{x}_n{e}^{-2\pi ikn/N},k=0,1,...,N-1$$ 其中，$X_k$ 是频域信号，$x_n$ 是时域信号，$N$ 是信号长度，$i$ 是虚数单位。
• IDFT公式（逆变换）：
  $$x_n=\frac{1}{N}\sum _{k=0}^{N-1}{X}_k{e}^{2\pi ikn/N}$$ IDFT 将频域信号转换回时域信号。
• 性质：
  • 可逆性：DFT 和 IDFT 互为逆运算，可以无损地从时域到频域再回到时域。
  • 能量守恒：根据 Parseval 定理，信号在时域和频域的能量相等。
  • 周期性：DFT 结果具有周期性，$X_{k+N}=X_k$。

2.2 计算复杂度

• 直接计算 DFT 的复杂度为 $O(N^2)$，因为对于每个 $k$，需要对所有 $n$ 进行求和运算。
• 当信号长度 $N$ 很大时，计算效率极低，因此需要更高效的算法（如 FFT）。

3. 快速傅里叶变换（FFT）

3.1 原理

• 分治思想：将长度为 $N$ 的 DFT 分解为两个长度为 $N/2$ 的 DFT，递归进行分解，直到长度为 1。
• 要求：$N$ 必须为 2 的幂，以便递归分解。
• FFT 通过减少重复计算，大幅降低复杂度。

3.2 算法流程（Cooley-Tukey FFT）

1. 输入序列 $x_0,x_1,...,x_{N-1}$。
2. 若 $N=1$，直接返回 $x_0$。
3. 将序列分为偶数项 $x_{2m}$ 和奇数项 $x_{2m+1}$。
4. 分别递归计算偶数和奇数部分的 DFT，得到 $E_k$ 和 $O_k$。
5. 合并结果：
   $$\begin{gathered} X_k=E_k+W_N^k{O}_k \\ {X}_{k+N/2}=E_k-W_N^k{O}_k \end{gathered}$$ 其中 $E_k$、$O_k$ 分别为偶/奇部分的 DFT 结果，$W_N^k=e^{-2\pi ik/N}$ 是旋转因子。
6. 复杂度从 $O(N^2)$ 降为 $O(N\log N)$。

3.3 例题

例题1：计算 $x=[1,0,-1,0]$ 的 DFT。

详细解答：

• 给定 $N=4$，使用 DFT 公式 $X_k={\sum }_{n=0}^3{x}_n{e}^{-2\pi ikn/4}$。
• 计算 $X_0$： $$X_0=x_0{e}^0+x_1{e}^0+x_2{e}^0+x_3{e}^0=1+0+(-1)+0=0$$
• 计算 $X_1$： $$X_1=x_0{e}^0+x_1{e}^{-2\pi i\cdot 1\cdot 1/4}+x_2{e}^{-2\pi i\cdot 2\cdot 1/4}+x_3{e}^{-2\pi i\cdot 3\cdot 1/4}$$ 其中 $e^{-2\pi i/4}=e^{-\pi i/2}=-i$，$e^{-\pi i}=-1$，$e^{-3\pi i/2}=i$，所以： $$X_1=1\cdot 1+0\cdot (-i)+(-1)\cdot (-1)+0\cdot i=1+0+1+0=2$$
• 计算 $X_2$： $$X_2=x_0{e}^0+x_1{e}^{-2\pi i\cdot 1\cdot 2/4}+x_2{e}^{-2\pi i\cdot 2\cdot 2/4}+x_3{e}^{-2\pi i\cdot 3\cdot 2/4}$$ 其中 $e^{-\pi i}=-1$，$e^{-2\pi i}=1$，$e^{-3\pi i}=-1$，所以： $$X_2=1\cdot 1+0\cdot (-1)+(-1)\cdot 1+0\cdot (-1)=1+0+(-1)+0=0$$
• 计算 $X_3$： $$X_3=x_0{e}^0+x_1{e}^{-2\pi i\cdot 1\cdot 3/4}+x_2{e}^{-2\pi i\cdot 2\cdot 3/4}+x_3{e}^{-2\pi i\cdot 3\cdot 3/4}$$ 其中 $e^{-3\pi i/2}=i$，$e^{-3\pi i}=-1$，$e^{-9\pi i/2}=e^{-4\pi i-\pi i/2}=e^{-\pi i/2}=-i$，所以： $$X_3=1\cdot 1+0\cdot i+(-1)\cdot (-1)+0\cdot (-i)=1+0+1+0=2$$
• 最终结果：$X=[0,2,0,2]$。

例题2：使用 FFT 计算 $x=[1,2,3,4,5,6,7,8]$ 的 DFT。

解答步骤：

1. $N=8$，满足 2 的幂要求。
2. 第一步分解：分为偶数项 $[1,3,5,7]$ 和奇数项 $[2,4,6,8]$。
3. 继续递归分解，直到长度为 1。
4. 合并计算（由于篇幅限制，这里省略详细计算步骤，直接给出结果）。
5. 结果：$X=[36,-4+9.656i,-4+4i,-4+1.656i,-4,-4-1.656i,-4-4i,-4-9.656i]$。

4. 三角插值与JPEG应用

4.1 三角插值（Trigonometric Interpolation）

• 定义：用三角函数（正弦、余弦）拟合周期数据，适用于周期性信号的分析和重构。
• 与 DFT 的关系：DFT 本质上就是三角插值系数的计算，$X_k$ 表示信号在不同频率上的分量。
• 应用：信号重构、数据平滑、周期性预测。

例题3：计算信号 $x=[1,1,1,1]$ 的 DFT，并解释其频域意义。

详细解答：

1. 使用 DFT 公式：$X_k={\sum }_{n=0}^3{x}_n{e}^{-2\pi ikn/4}$。
2. 计算 $X_0$： $$X_0=1+1+1+1=4$$
3. 计算 $X_1$： $$X_1=1\cdot 1+1\cdot e^{-\pi i/2}+1\cdot e^{-\pi i}+1\cdot e^{-3\pi i/2}=1+(-i)+(-1)+i=0$$
4. 计算 $X_2$： $$X_2=1\cdot 1+1\cdot e^{-\pi i}+1\cdot e^{-2\pi i}+1\cdot e^{-3\pi i}=1+(-1)+1+(-1)=0$$
5. 计算 $X_3$： $$X_3=1\cdot 1+1\cdot e^{-3\pi i/2}+1\cdot e^{-3\pi i}+1\cdot e^{-9\pi i/2}=1+i+(-1)+(-i)=0$$
6. 结果：$X=[4,0,0,0]$。
7. 频域意义：信号的能量全部集中在直流分量（$X_0$），表示信号没有周期性变化，是一个常数值信号。

4.2 JPEG 压缩中的 DCT

• 离散余弦变换（DCT）：JPEG 采用 DCT，本质与 DFT 类似，但只使用实数部分（余弦函数），避免复数运算。
• DCT 公式（一维）： $$C_k=\sum _{n=0}^{N-1}{x}_n\cos \left[\frac{\pi }{N}\left(n+\frac{1}{2}\right)k\right]$$
• 优势：
  • DCT 能将图像能量集中在低频分量，便于去除高频噪声（人眼对高频细节不敏感）。
  • 实数运算比 DFT 的复数运算更高效。
• JPEG 压缩流程：
  1. 将图像分成 8x8 像素块。
  2. 对每个块应用二维 DCT，得到频域系数。
  3. 量化：对高频系数进行压缩（丢弃小值或近似）。
  4. 编码：使用霍夫曼编码等方法进一步压缩数据。
  5. 解压时逆向操作：逆量化、逆 DCT 重构图像。
• DCT 与 DFT 的区别：
  • DCT 仅用余弦函数，输出为实数；DFT 使用复指数，输出为复数。
  • DCT 边界条件更适合图像处理（镜像对称），减少边界不连续性。

例题4：解释为什么 JPEG 压缩会丢失细节。

解答：

• JPEG 压缩通过量化步骤丢弃高频分量的小值系数，而高频分量对应图像的细节（如边缘、纹理）。
• 人眼对高频细节不敏感，因此丢弃这些分量可以在不明显影响视觉质量的情况下大幅减少数据量。
• 这种有损压缩导致细节丢失，尤其在高压缩比下，图像可能出现块状伪影（blocking artifacts）。

5. 常见考点与易错点

• DFT/IDFT 公式推导与正负号：注意指数中的正负号，DFT 为负号，IDFT 为正号。
• FFT 分治递归与合并步骤：理解如何分解序列和合并结果，旋转因子的作用。
• 频域与时域的物理意义：时域表示信号随时间变化，频域表示信号的频率成分和能量分布。
• DCT 与 DFT 的区别：DCT 仅用实数，适合图像压缩；DFT 处理复数，适合信号分析。
• 易错点：
  • 计算 DFT 时漏掉旋转因子的复数性质。
  • FFT 合并时未正确处理 $N/2$ 偏移。
  • 混淆 DCT 和 DFT 的应用场景。
• 英文术语拼写与公式记忆：熟悉常见术语拼写，考试中可能要求手写公式。

6. 英文关键词与表达

• discrete Fourier transform (DFT), fast Fourier transform (FFT), frequency domain, time domain, trigonometric interpolation, discrete cosine transform (DCT), JPEG compression, signal processing, spectrum, complex exponential, quantization, blocking artifacts

如需更详细例题推导或某一算法的代码实现，可随时补充！