4. Tanner图与因子图表示

在最小权重完美匹配译码中，图模型不是辅助说明，而是算法运行的“数据结构本体”。同一个线性分组码，既可以用校验矩阵 H 描述，也可以用 Tanner 图描述；而译码器真正操作的，是 Tanner 图经过“边展开”后形成的因子图——变量节点代表比特或边，校验节点代表局部约束，边权重代表该比特取某值的代价。理解这三层对象之间的对应关系，是写出正确译码程序的前提。

一、从校验矩阵到 Tanner 图

设码长为 n、校验方程数为 m，校验矩阵 H 为 m×n。Tanner 图是二分图：左侧 n 个变量节点 vj 对应码字比特，右侧 m 个校验节点 ci 对应校验方程。当且仅当 Hij=1 时，vj 与 ci 之间存在一条边。因此 Tanner 图的邻接关系与 H 的非零元位置一一对应，图中不存在变量节点之间或校验节点之间的直接连边。

以 (7,4) 汉明码为例，取校验矩阵

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

第 1 行说明校验节点 c1 连接 v1、v2、v4、v5，约束为 v1⊕v2⊕v4⊕v5=0；其余两行同理。每个变量节点的度等于其所在列的列重，每个校验节点的度等于对应行的行重。这个“度分布”直接决定后续因子图的规模与复杂度。

二、因子图：把“比特”变成“边”

最小权重完美匹配译码的关键一步，是把 Tanner 图中的变量节点转换为因子图中的边。做法是：对每个变量节点 vj，把它所连接的所有校验节点两两配对，形成一条候选边；每条候选边对应“比特 vj 取某个值”的一种局部假设。这样，因子图的顶点是校验节点（以及为处理奇偶性引入的辅助节点），因子图的边才是原始码字比特。

更具体地说，若 vj 的度为 dj，则在因子图中它为每个相邻校验节点提供一个“端点”，这些端点按比特取值 0 或 1 分成两组，组内配对形成边。每条边携带一个权重，表示该比特取对应值的代价。译码目标于是转化为：在因子图中选出一组边，使每个校验节点的度约束（奇偶校验）被满足，且所选边的总权重最小——这正是“最小权重完美匹配”名称的由来。

三、边权重的来源与含义

因子图中的每条边必须带权重，否则“最小权重”无从谈起。权重通常来自信道软信息：对 BPSK 调制、AWGN 信道，若第 j 个比特的接收似然比为 Lj，则取 0 的代价可设为 wj(0)=max(0,−Lj)，取 1 的代价为 wj(1)=max(0,Lj)。直观上，接收值越偏向某个比特值，取该值的代价越小。这样，最小化总权重就等价于最大化整码字的似然，与最大似然译码在软判决意义上一致。

需要注意权重与“边”的绑定方式：在因子图中，一条边代表“比特 vj 在某个校验节点处取某值”的局部事件，因此同一位比特在不同校验节点处会形成不同的边，各自携带与该取值对应的代价。译码器最终选出的匹配边集合，必须保证每个比特在所有相邻校验节点处的取值一致——这一致性约束由因子图的结构（辅助节点的配对方式）来保证，而不是靠事后检查。

四、译码目标在图上的精确表述

把上述对应关系串起来，最小权重完美匹配译码的目标可以写成：在因子图中寻找一个边集 M，使得每个校验节点（因子）恰好关联 M 中一条边（完美匹配条件），并且 Σe∈M w(e) 最小。这里的“完美”指每个校验节点的局部奇偶约束都被满足，“匹配”指每个比特的取值假设不冲突。求解该问题通常采用 Blossom 算法（如 Kolmogorov 的 Blossom V 实现），其输入正是因子图的顶点、边与权重三元组。

五、一个可核对的小例子

仍以 (7,4) 汉明码为例，假设接收软信息给出各比特取 1 的代价为 [0.2, 0.9, 0.4, 0.7, 0.1, 0.6, 0.3]，取 0 的代价为 [0.8, 0.1, 0.6, 0.3, 0.9, 0.4, 0.7]（示例数据，仅用于说明流程）。按前述规则展开因子图后，每个校验节点周围形成若干候选边。运行匹配算法，若选出的边集对应的比特取值为 1011010，则需验证 H·xT=0 是否成立；成立则说明匹配结果满足全部校验约束，且其总权重应与穷举所有合法码字得到的最小代价一致。这个“匹配结果—码字—校验—权重”的闭环核对，是调试因子图构建是否正确的最直接手段。

综上，Tanner 图回答“哪些比特参与哪个校验”，因子图回答“每个比特的取值假设如何与校验约束配对”，边权重回答“这种假设要付多少代价”，而译码目标则是三者在图上的统一：找一组满足全部校验约束、总代价最小的比特取值。把这三层对象在代码中分别建模、再通过边标识关联起来，后续的匹配求解与结果反查就会清晰可控。