3. 译码问题到匹配问题的转化

伴随式译码的目标，是在给定接收序列 r 后，从所有满足 H·eᵀ = s 的错误图样 e 中挑出重量最小的一个，再令 ĉ = r ⊕ ê。这一步看似是"在码的陪集里找最轻向量"，但它与图论中的最小权重完美匹配之间存在一条非常直接的构造通道。理解这条通道，是后续用 Blossom 类算法实现译码的前提。

一、为什么"陪集找最轻"能变成"图上配对"

设二元线性分组码 C 的校验矩阵为 H，尺寸为 (n−k)×n，列向量记为 h₁, h₂, …, hₙ，每个 hⱼ ∈ GF(2)^(n−k)。接收序列的伴随式为 s = H·rᵀ。若错误图样 e 的非零位置集合为 E ⊆ {1,…,n}，则伴随式条件等价于

Σ_{j∈E} hⱼ = s   (GF(2) 上的向量和)

也就是说，选哪些列、使它们的异或和恰好等于 s，就是译码要解决的问题；而重量最小，就是要求被选中的列数最少。这个"用最少的列异或出目标向量"的结构，正是匹配问题擅长表达的形式：把每个列向量看作图中的一个顶点，把"两列异或等于某个中间值"看作一条带权边，那么一组配对就对应一组列的异或组合。

二、Tanner 图视角：校验节点与变量节点的连接

更贴近工程实现的看法来自 Tanner 图。Tanner 图是二分图：左侧 n 个变量节点 v₁…vₙ 对应码字比特，右侧 n−k 个校验节点 c₁…c_{n−k} 对应校验方程；当 H 的第 i 行第 j 列为 1 时，vⱼ 与 cᵢ 之间连一条边。每个变量节点 vⱼ 所连的校验节点集合，恰好就是列向量 hⱼ 中 1 的位置，因此 hⱼ 可以理解为"变量节点 vⱼ 在校验空间中的签名"。

译码时，伴随式 s 标记出哪些校验节点"不满足"。一个错误比特 eⱼ = 1 会翻转它所连接的所有校验节点的满足状态。于是问题变成：选择最少的变量节点，使被翻转的校验节点集合恰好等于不满足集合。这正是把"列异或"翻译成了"节点翻转覆盖"。

三、构造匹配图的三条关键规则

把 Tanner 图"折叠"成匹配图，需要明确三件事，否则构造出的图与译码问题不等价。

规则一：顶点代表列签名，而不是比特本身。匹配图的一个顶点对应一个列向量 hⱼ（即变量节点 vⱼ 的校验签名）。若两个列签名相同，它们可以合并为同一顶点，但需要记录该顶点可被使用的次数（即该签名在 H 中出现的列数），这对应匹配中的"多重顶点"处理。

规则二：边代表"两列异或等于某个目标值"。若 hᵢ ⊕ hⱼ = t，则在 hᵢ 与 hⱼ 之间连一条边，边权取 w(hᵢ,hⱼ) = 2（因为用了两列）。若某列 hⱼ 本身等于目标值 t，则它需要与一个"虚拟顶点"配对，边权取 1（只用了一列）。虚拟顶点代表"空"，与它配对意味着该列单独贡献。

规则三：目标值由伴随式决定，且需要逐层消去。直接对 s 一次性配对往往不够，因为 s 可能由三列、四列甚至更多列异或而成。标准做法是引入"中间目标"：把 s 分解为若干子目标 t₁ ⊕ t₂ ⊕ … = s，每个子目标由一对列（或一列加虚拟顶点）实现。子目标的选取不是任意的，需要保证分解后每一对都能在图中找到对应边，且总权重最小。工程上常把 s 的所有可能"半分解"枚举出来，构造一个以 s 为根、以列签名为叶的分解树，再把树上的每个二选一节点转成匹配边。

四、一个可手算的教学示例

取一个 (6,3) 码，校验矩阵设为

H = [1 0 1 1 0 1
     0 1 1 0 1 1
     1 1 0 1 1 0]

列签名依次为 h₁=(1,0,1)、h₂=(0,1,1)、h₃=(1,1,0)、h₄=(1,0,1)、h₅=(0,1,1)、h₆=(1,1,0)。注意 h₁=h₄、h₂=h₅、h₃=h₆，即每个签名出现两次。设接收序列的伴随式为 s=(1,1,0)，恰好等于 h₃。

构造匹配图：顶点为三个签名 A=(1,0,1)、B=(0,1,1)、C=(1,1,0)，各带容量 2；另设虚拟顶点 ∅。边与权重如下：

最小权重完美匹配会优先选 C—∅，权重 1，对应错误图样只翻转一个比特，位置在 h₃ 或 h₆ 处（两者签名相同，任选其一即可，译出的码字相同）。若 s 不等于任何单列签名，例如 s=(1,1,0)⊕(1,0,1)=(0,1,1)，则匹配会退而选 A—B，权重 2，对应翻转两个比特。这个例子说明：匹配权重直接给出错误重量，匹配结果直接给出错误位置，译码不需要再额外搜索。

五、实现时容易踩的三个坑

坑一：忘记虚拟顶点。若只允许列与列配对，奇数重量的错误图样就无法表达，匹配会失败或给出错误结果。虚拟顶点的容量应设为足够大（至少 n），否则单列解会被"挤掉"。

坑二：把边权设成 1 而不是 2。列与列配对消耗两列，权重必须是 2；只有列与虚拟顶点配对才计 1。若统一设 1，最小匹配会倾向于多用配对，导致错误重量被低估。

坑三：忽略签名重复带来的容量约束。同一签名出现 m 次，该顶点最多被匹配 m 次。若容量设错，匹配可能选出 H 中不存在的列组合，译出的错误图样无法对应真实比特位置。