第五章 纠错编码 (Error-Correction Coding)

纠错编码的基本思想是在信息序列中引入冗余位（监督位），利用这些冗余位与信息位之间的代数关系来检测或纠正传输过程中的差错。

1. $(n, k)$ 分组码基础

1.1 基本定义

• $k$：信息位的位数。
• $n$：码字的总长度（信息位 + 监督位）。
• $r = n - k$：监督位（校验位）的位数。
• 码率 $R$：$R = \frac{k}{n}$，衡量编码效率。

1.2 线性分组码 (Linear Block Codes)

线性分组码的特点是：码字中的监督位是信息位的模-2 和（即异或 $\oplus$ 运算）。

例：$(7, 3)$ 分组码 设信息位为 $m = \{m_1, m_2, m_3\}$，码字为 $C = \{c_1, c_2, c_3, c_4, c_5, c_6, c_7\}$。 如果规定前 3 位为信息位（$c_1=m_1, c_2=m_2, c_3=m_3$），后 4 位为监督位，且满足：

$\begin{cases} c_4 = c_1 \oplus c_3 \\ c_5 = c_1 \oplus c_2 \\ c_6 = c_1 \oplus c_2 \oplus c_3 \\ c_7 = c_2 \oplus c_3 \end{cases}$

一部分是信息位一部分是校验位

1.3 系统码 (Systematic Codes)

系统码是指码字可以明确划分为信息位和校验位两个部分。

• 形式 1：$[ \text{信息位} \mid \text{校验位} ]$
• 形式 2：$[ \text{校验位} \mid \text{信息位} ]$ (笔记中提到“一刀切”，前面校验，后面信息，这也是一种常见形式)

2. 生成矩阵 $G$ (Generator Matrix)

生成矩阵的作用是：已知信息位 $m$，通过 $G$ 生成码字 $C$。

$C = m \cdot G$

其中，$m$ 是 $1 \times k$ 向量，$G$ 是 $k \times n$ 矩阵。

如果我们需要编码，那么我们就需要求出生成多项式

2.1 典型形式（系统码）

若 $G = [I_k \mid P]$，其中 $I_k$ 是 $k \times k$ 单位阵，$P$ 是 $k \times r$ 校验矩阵，则生成的码字是系统码。

• 注：非系统码可以通过初等行变换转化为系统码。

例题 给定 $G = [I \mid P] = \begin{bmatrix} 1 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 0 & 1 \end{bmatrix}$ 每一行都是一个合法的码字。

3. 校验矩阵 $H$ (Parity-Check Matrix)

校验矩阵用于验证接收到的码字是否正确。 若 $G = [I_k \mid P]$，则对应的校验矩阵为 $H = [P^T \mid I_r]$。 满足关系：$G \cdot H^T = 0$。

3.1 伴随式 (Syndrome) $S$

设接收到的码字为 $Y$，则伴随式为：

$S = Y \cdot H^T$

• 若 $S = 0$：接收无误（或发生了不可检测的差错）。
• 若 $S \neq 0$：接收有误。
• 检错规律：若 $S$ 等于 $H$ 矩阵的第 $i$ 列，通常预示着第 $i$ 位发生了错误。

4. 纠错与检错能力

4.1 最小汉明距离 $d_{min}$

最小汉明距离是码组中任意两个码字之间对应位不同的最小个数。

• 对于线性分组码，$d_{min} = \text{最小非零码字的汉明重量 } w_{min}$。
• 在校验矩阵 $H$ 中，$d_{min}$ 等于 $H$ 中线性相关的列向量的最少个数。

4.2 纠检错公式

1. 检测 $e$ 个错：$d_{min} \ge e + 1$
2. 纠正 $t$ 个错：$d_{min} \ge 2t + 1$
3. 纠正 $t$ 个错且检测 $e$ 个错 ($e > t$)：$d_{min} \ge t + e + 1$

5. 汉明码 (Hamming Codes)

汉明码是一种能纠正单个随机错误的线性分组码。

• 参数：$n = 2^m - 1, r = m, k = 2^m - 1 - m$。
• 构造：$H$ 矩阵的每一列由除全 0 外的所有 $m$ 位二进制向量组成。

6. 循环码 (Cyclic Codes)

6.1 特点

码字具有循环移位特性：若 $C$ 是一个码字，则其循环移位后的序列也是码字。

6.2 多项式表示

• 码字多项式：$C(x) = c_{n-1}x^{n-1} + c_{n-2}x^{n-2} + \dots + c_1x + c_0$
• 生成多项式 $g(x)$：阶数为 $r = n - k$。所有码字多项式都能被 $g(x)$ 整除。

6.3 系统循环码的编码 (SOP)

1. 将信息多项式 $m(x)$ 左移 $r$ 位：$m(x) \cdot x^r$。
2. 求余数：$r(x) = [m(x) \cdot x^r] \mod g(x)$。
3. 合成码多项式：$C(x) = m(x) \cdot x^r \oplus r(x)$。

7. 综合例题

例 1：汉明距离与纠错能力

已知一组码字，通过比较每两个码字之间的差异，找出最小距离 $d_{min}$。 若 $d_{min}=3$，则：

• 检测错误数 $e$: $3 \ge e+1 \to e=2$。
• 纠正错误数 $t$: $3 \ge 2t+1 \to t=1$。

例 2：已知 $H$ 求参数

已知 $H$ 为 $4 \times 9$ 矩阵。

• $n = 9$（列数），$r = 4$（行数）。
• $k = n - r = 5$。
• 编码率 $R = k/n = 5/9$。
• 通过行变换观察 $H$ 的线性相关性，求得 $d_{min} = 4$。

例 3：汉明码编码过程

已知校验矩阵 $H = \begin{bmatrix} 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 \end{bmatrix}$ 这是一个系统码形式 $H = [P^T \mid I]$。

1. 写出 $G = [I \mid P]$。
2. 输入序列分段编码：$1101, 0110, 010 \dots$
3. 利用 $C = m \cdot G$ 分段求出对应的码序列并拼接。

例4 循环码

**例题 **: 已知 $g(x) = x^3 + x^2 + 1$，输入信息 $0110$。

1. $k=4, r=3 \to n=7$。信息位 $0110 \to m(x) = x^2 + x$。
2. $m(x) \cdot x^3 = x^5 + x^4$。
3. $(x^5 + x^4) \div (x^3 + x^2 + 1)$，余数为 $x^2$。
4. 码字多项式为 $x^5 + x^4 + x^2$，对应序列为 $0110100$。