3. 线性分组码基础

比特翻转纠错码并不是凭空设计出来的，它建立在线性分组码这套代数框架之上。理解生成矩阵、校验矩阵和伴随式，就等于拿到了读懂后续纠错码构造与译码的钥匙。本节从“信息如何被编码”出发，逐步过渡到“错误如何被检测”，为后续的比特翻转纠错码奠定代数基础。

一、分组码的基本约定

分组码把信息序列切成固定长度的信息组，每组 k 个比特，编码后得到 n 个比特的码字，记作 (n, k) 码。多出来的 n−k 个比特是校验位，它们由信息位通过线性运算产生。所谓“线性”，指任意两个合法码字按位模 2 相加，结果仍是合法码字；全零向量也一定是合法码字。这两条性质决定了整个码字集合是一个 k 维线性子空间，也决定了后面所有矩阵运算都在 GF(2) 上进行——加法即异或，减法与加法相同。

需要先明确参照约定：本节所有向量均按行向量书写，矩阵乘法为“行向量 × 矩阵”，所有运算在 GF(2) 上取模 2。这一约定在全文和图示中保持一致。

二、生成矩阵 G：从信息到码字

既然合法码字构成 k 维子空间，就一定能找到 k 个线性无关的码字作为基。把这 k 个基码字按行排成一个 k×n 的矩阵，就得到生成矩阵 G。对任意信息向量 m（长度 k），码字 c 由下式给出：

c = m · G   （GF(2) 上运算）

最常用的是系统形式的生成矩阵：G = [ I_k | P ]，其中 I_k 是 k 阶单位阵，P 是 k×(n−k) 的校验位生成子矩阵。系统形式的优点是编码后前 k 位原样保留信息，后 n−k 位是校验位，便于观察和提取。

举一个具体示例（示例参数，用于说明构造方法）：取 k=4、n=7，构造 (7,4) 码，令

        [1 0 0 0 | 1 1 0]
        [0 1 0 0 | 0 1 1]
G  =    [0 0 1 0 | 1 1 1]
        [0 0 0 1 | 1 0 1]

若信息 m = (1 0 1 1)，则码字 c = m·G。逐位计算：第 5 位（第一个校验位）= 1·1 ⊕ 0·0 ⊕ 1·1 ⊕ 1·1 = 1；第 6 位 = 1·1 ⊕ 0·1 ⊕ 1·1 ⊕ 1·0 = 0；第 7 位 = 1·0 ⊕ 0·1 ⊕ 1·1 ⊕ 1·1 = 0。于是 c = (1 0 1 1 1 0 0)。可以看到，信息位原样出现在前四位，校验位由 P 的各列与信息位做内积得到。这就是编码的实际操作过程：把信息向量与 G 的每一列做模 2 内积，得到对应码位。

三、校验矩阵 H：合法码字的“筛子”

生成矩阵回答“哪些是码字”，校验矩阵回答“怎样判断一个向量是不是码字”。对系统码 G = [ I_k | P ]，校验矩阵定义为：

H = [ P^T | I_(n−k) ]   （尺寸 (n−k)×n）

它满足核心关系 G · H^T = 0，等价地，任意合法码字 c 都满足：

c · H^T = 0

这条式子就是错误检测的全部依据。对上例，P^T 为 3×4 矩阵，接上 3 阶单位阵，得到 3×7 的 H。可以验证，前面算出的码字 (1 0 1 1 1 0 0) 与 H 的每一行做内积（即与 H^T 相乘）结果均为 0，说明它确实落在码空间内。

从几何上看，H 的每一行定义了一个校验方程，n−k 个方程共同“筛出”了 k 维的码空间。H 的列向量尤其重要：每一列是一个 n−k 维向量，称为该码位的校验列。当只有第 i 位发生翻转时，接收向量 r = c ⊕ e_i，其中 e_i 是第 i 位为 1 的单位向量，此时 r·H^T 恰好等于 H 的第 i 列。这一事实是后续伴随式定位错误的直接来源。

四、伴随式：错误检测的核心量

接收端拿到 r 后，计算伴随式（syndrome）：

s = r · H^T

由于 r = c ⊕ e，且 c·H^T = 0，立刻得到：

s = (c ⊕ e) · H^T = c·H^T ⊕ e·H^T = e·H^T

这个推导非常关键：伴随式只与错误图样 e 有关，与发送的是哪个码字无关。也就是说，无论信息内容是什么，只要错误模式相同，伴随式就相同。这正是线性分组码能够用统一逻辑检测和纠正错误的根本原因。

伴随式的长度是 n−k 位，最多有 2^(n−k) 种取值。对 (7,4) 码，伴随式是 3 位，共 8 种取值。其中 s = 0 对应无错（或错误恰好构成另一个合法码字，即不可检测错误）；s ≠ 0 的 7 种非零取值，恰好可以一一对应 7 个单比特错误位置。这就是为什么 (7,4) 码能够纠正任意单比特翻转：7 个单错图样映射到 7 个互不相同的非零伴随式，译码器只需查表即可定位错误位。

继续用上例演示。假设码字 (1 0 1 1 1 0 0) 在传输中第 3 位翻转，接收为 r = (1 0 0 1 1 0 0)。计算 s = r·H^T，结果应等于 H 的第 3 列。查 H 的第 3 列（对应 P^T 的第 3 行转置后与单位阵部分组合），得到非零向量，据此判定第 3 位出错，将其翻转回 1，恢复原码字。整个检测—定位—纠正的闭环，完全由矩阵乘法和查表完成，无需任何启发式判断。

五、构造时的两个实用要点

第一，H 的列必须互不相同且非零。若两列相同，则这两个位置同时出错会产生相同伴随式，无法区分；若某列为零，则该位出错不改变伴随式，直接漏检。对纠单错的码，这一条件既是必要的也是充分的。构造时可以先列出所有非零的 n−k 维向量作为候选列，再从中挑选 n 列。

第二，最小距离决定纠错能力。码的最小汉明距离 d_min 等于 H 中任意线性相关列的最小数目。d_min = 3 时可纠 1 位错、检 2 位错；d_min 越大，纠错能力越强，但校验位也越多。设计比特翻转纠错码时，本质上就是在“校验位开销”和“纠错能力”之间做权衡，而 H 的列结构就是这一权衡的直接体现。

掌握以上内容后，再看比特翻转纠错码的具体构造，就会发现它不过是在这套线性代数框架下，针对特定错误模型（比特翻转）选择了一组满足列条件的 H，并配套设计了查表译码逻辑。生成矩阵与校验矩阵的对偶关系、伴随式与错误图样的一一映射，构成了后续所有纠错方案的共同底座。