第 30 章 线性代数在信号处理与编码中的应用¶
前置：酉矩阵 (Ch55A) · 循环矩阵 (Ch37A) · 有限域 (Ch52) · 正交性 (Ch07)
本章脉络：信号即向量 \(\to\) 线性时不变 (LTI) 系统的代数描述 \(\to\) 卷积的矩阵形式：循环矩阵与 Toeplitz 矩阵 \(\to\) 核心变换：离散傅里叶变换 (DFT) 的范德蒙德矩阵表示 \(\to\) 谱分析：频率作为特征值 \(\to\) 小波变换与正交基 \(\to\) 抽样定理的线性代数解释 \(\to\) 编码理论：生成矩阵与校验矩阵 \(\to\) 纠错码的子空间视角 \(\to\) 应用：音频压缩 (MP3)、数字水印、5G 通信中的信道编码
延伸：信号处理是线性代数的“动态实现”；它将频率分析转化为算子的对角化过程，将信息冗余转化为向量空间的子空间编码，是连接物理波动与数字逻辑的桥梁
在现代数字世界中，无论是听音乐还是发送短信，背后都在进行着高频的线性代数运算。信号处理（Signal Processing）将时间序列视为向量，将滤波器视为矩阵。而编码理论（Coding Theory）则通过在有限域上构建特殊的子空间来保护信息。本章将介绍离散傅里叶变换的矩阵本质，以及线性代数如何让通信变得既快又准。
30.1 DFT 的矩阵本质¶
定义 30.1 (DFT 矩阵 \(F_n\))
\(n\) 阶离散傅里叶变换是一个线性变换，其矩阵元素为单位根的幂： $\((F_n)_{jk} = \frac{1}{\sqrt{n}} \omega^{jk}, \quad \omega = e^{-2\pi i/n}\)$ 性质：\(F_n\) 是一个酉矩阵。这意味着频域表示完整保留了时域信号的能量（Parseval 定理）。
30.2 卷积与循环矩阵¶
定理 30.1 (卷积定理的矩阵版)
离散卷积运算等价于向量与一个循环矩阵（Circulant Matrix）相乘。 由于循环矩阵总能被 DFT 矩阵对角化，这解释了为什么“时域卷积等于频域点乘”。
30.3 纠错码的代数结构¶
子空间编码
一个 \((n, k)\) 线性纠错码是 \(GF(q)^n\) 空间中的一个 \(k\) 维子空间。 - 纠错能力：由子空间中向量之间的最小 Hamming 距离决定。 - 伴随式 (Syndrome)：利用校验矩阵 \(H\) 的零空间性质，通过 \(H\mathbf{r}^T\) 快速定位错误位置。
练习题¶
1. [基础] 计算 \(2 \times 2\) 的 DFT 矩阵 \(F_2\)。
参考答案
构造： 1. \(n=2, \omega = e^{-i\pi} = -1\)。 2. 指标 \(j, k \in \{0, 1\}\)。 3. 矩阵元素：\(F_{00}=1, F_{01}=1, F_{10}=1, F_{11}=-1\)。 4. 归一化因子 \(1/\sqrt{2}\)。 结论：\(F_2 = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}\)。注意：这正好是 Hadamard 矩阵。
2. [谱分析] 证明：循环矩阵的特征值可以通过对其第一行向量做 DFT 得到。
参考答案
证明思路： 1. 设循环矩阵为 \(C\)。已知 \(C = F^* \Lambda F\)。 2. \(\Lambda\) 的对角元即为特征值。 3. 考虑第一行 \(c = (c_0, \ldots, c_{n-1})\)。 4. \(C\) 的第一行等于 \(\mathbf{e}_1^T C\)。 5. 代入对角化形式并利用 \(F\) 的结构，发现特征值恰好是 \(c\) 的基变换结果。
3. [计算] 若信号向量 \(x = (1, 0, 1, 0)^T\)，求其经过 \(F_4\) 变换后的直流分量（第 0 个频率）。
参考答案
计算： 1. 第 0 个频率对应 DFT 矩阵的第一行，全为 \(1/2\)（归一化后）。 2. \(X_0 = \frac{1}{2}(1\cdot 1 + 0\cdot 1 + 1\cdot 1 + 0\cdot 1) = \frac{1}{2}(2) = 1\)。 结论：直流分量为 1。
4. [采样] 抽样定理在向量空间中意味着什么？
参考答案
代数解释： 意味着如果我们知道连续函数在某个低维子空间（带宽受限）内，那么通过对其在特定点采样得到的有限维向量，可以唯一重构出原函数。这本质上是保证采样算子在带限子空间上是单射的。
5. [小波] 简述 Haar 小波变换相对于傅里叶变换的矩阵特点。
参考答案
Haar 小波矩阵是稀疏的且具有递归的分块结构。 对比：傅里叶基是全局支撑的（每个基向量影响所有时间点），而小波基是局部支撑的。这使得小波变换在矩阵表示上更适合处理突变信号和图像压缩（JPEG 2000）。
6. [纠错] 若校验矩阵 \(H = \begin{pmatrix} 1 & 1 & 1 \end{pmatrix}\)，接收到向量 \(\mathbf{r} = (1, 0, 1)\)，是否有错？
参考答案
计算伴随式： \(H \mathbf{r}^T = 1\cdot 1 + 1\cdot 0 + 1\cdot 1 = 1+0+1 = 0 \pmod 2\)。 结论：由于伴随式为 0，说明接收向量落在编码子空间内，判定为无错。
7. [性质] 证明 DFT 矩阵的逆矩阵满足 \(F^{-1} = F^*\)。
参考答案
证明： 1. 计算 \(F F^*\) 的 \((j, k)\) 元素：\(\frac{1}{n} \sum_m \omega^{jm} \overline{\omega^{km}} = \frac{1}{n} \sum_m \omega^{m(j-k)}\)。 2. 利用单位根求和性质：若 \(j=k\)，和为 \(n\)；若 \(j \neq k\)，和为 0。 3. 故 \(F F^* = I\)。 结论：DFT 矩阵是典型的酉矩阵。
8. [应用] 什么是信道均衡中的“迫零”（Zero Forcing）算法？
参考答案
代数本质： 信道干扰可以建模为 \(y = Hx + n\)。 迫零算法通过左乘信道矩阵的逆或伪逆 \(H^+\) 来抵消干扰：\(\hat{x} = H^+ y\)。 这直接应用了线性方程组求解理论。
9. [滤波器] 判定：理想低通滤波器在频域对应的矩阵是什么形状？
参考答案
结论：对角矩阵。 在频域基下，滤波操作（频率加权）表现为 \(y_f = \Lambda X_f\)。 对于理想低通， \(\Lambda\) 的前 \(k\) 个对角元为 1，其余为 0。这本质上是一个正交投影算子。
10. [极限] 为什么快速傅里叶变换 (FFT) 如此重要？
参考答案
效率飞跃： 普通的矩阵-向量乘法需要 \(O(n^2)\) FLOPs。 FFT 利用 DFT 矩阵的递归对称性（Danielson-Lanczos 引理），将其分解为一系列稀疏矩阵之积，将复杂度降为 \(O(n \log n)\)。 这一代数上的加速是支撑现代所有实时通信（WiFi, 4G/5G）的基石。
本章小结¶
信号处理与编码是线性代数的“工程化呈现”：
- 频率的代数定义：通过 DFT 矩阵，我们证明了频率分析本质上是循环算子的特征值分解，为理解波动现象提供了纯数理工具。
- 信息的空间保护：纠错码理论展示了如何通过在有限域向量空间中精确设计子空间的“间距”，实现对物理噪声的代数免疫。
- 结构的效率：从循环矩阵的卷积对角化到 FFT 的分治分解，线性代数不仅提供了描述系统的语言，更通过利用矩阵的对称性结构，创造了支撑信息时代的极速算法。