综合译码

让校验方程消掉合法信息 ​

收到一段含噪声的数据时，直接猜原码字可能很困难。线性码提供了一种先问“小问题”的方法：这段数据违反了哪些校验方程？把所有校验结果收集起来，就是综合（syndrome，也称伴随式）。

综合的作用不是完整记录错误，而是消去合法码字留下的成分，只保留错误对校验方程造成的影响。综合译码据此寻找一个与校验结果一致的错误模式，再把它从接收词中减去。

从综合到纠正词 ​

基础综合译码为每个综合 $s$ 选择一个最小重量的错误代表，称为陪集首领：

一种有限的表构造方式是按重量从 $0$ 到 $n$ 枚举全部错误向量，同重量按预定字典序排列；计算每个向量的综合，只在该综合尚无代表时存入它。满行秩使每种综合都出现，最终每个表项都是按上述规则选定的最小重量首领。译码时计算 $s=H{r}^T$，取表项并返回 $r-\hat{e}(s)$。这给出可执行的穷举与查表过程，尚未给出多项式资源保证。

若有多个最小者，可以约定固定的选择规则。因为 $H{\hat{e}}^T=H{r}^T$，输出必然满足 $H{\hat{c}}^T=0$，所以它确实是一个码字。输出为合法码字与输出为原来的码字是两种不同保证。

当 $k\ge 1$ 时，设码的最小距离为 $d_{min}$，实际错误满足 $\mathrm{wt}(e)\le t$，且 $2t<d_{min}$。若存在另一个重量不大于 $t$ 的错误 $e^{\prime }$ 具有相同综合，那么非零码字 $e-e^{\prime }$ 的重量至多为 $2t$，与最小距离矛盾。因此在

的范围内，最小重量首领唯一且就是实际错误。这个保证来自Hamming 距离理路Hamming 距离Hamming distance等长字中不同坐标的数量；由逐位比较、三角不等式和 Hamming 球解释检错与唯一纠错半径。，不是来自查表本身。若 $k=0$，码本只有零向量，每个综合恰对应一个错误向量，译码始终返回零向量，无须用不同码字对定义最小距离。

对于各比特独立、翻转概率相同且 $0<p<1/2$ 的二元对称信道，一个重量为 $w$ 的具体错误向量发生的概率为 $p^w(1-p{)}^{n-w}$，随 $w$ 增加而减小。因此最小重量选择与最大似然译码一致。各位置可靠度不同或采用软判决时，应改用相应的似然代价；单纯“少改几位”不再自动等于最可能。[1]

一次完整的 Hamming 码译码 ​

考虑二元 $[7,4,3]$ Hamming 码，其校验矩阵为

七列恰好是七种不同的非零三比特向量。若仅第 $j$ 位翻转，$e$ 只有第 $j$ 个坐标为 $1$，于是 $H{e}^T$ 就是 $H$ 的第 $j$ 列：综合直接指出出错位置。

码字 $c=1110000$ 满足前三列之和为零，故校验通过。若第 $5$ 位翻转，则

综合 $(1,0,1{)}^T$ 等于第 $5$ 列，译码器翻转接收词的第 $5$ 位，恢复 1110000。这一过程只用一个三比特校验结果，就定位了七个可能位置之一。[1]

现在让第 $1$、$2$ 位同时翻转。两列异或得到第 $3$ 列，译码器会误以为第 $3$ 位出了错，再翻转这一位。最终三个位置都被改变，输出仍是合法码字，却不是原码字。这恰好越过了该码只能保证纠正一位错误的范围。

综合为零也不等于没有错误。任意非零码字形状的错误 $e\in C$ 都满足 $H{e}^T=0$，会把原码字变成另一个码字而不触发校验。

校验容易，寻找首领未必容易 ​

直接做矩阵乘法，计算综合需要 $O(n(n-k))$ 次有限域运算；稀疏或结构化矩阵可以更快。真正昂贵的部分可能是从 $s$ 找到最合适的 $e$。完整查表有 $q^{n-k}$ 个入口，构造每个入口的最小重量首领也可能需要大量搜索。

这就是“综合很短”不等于“译码很容易”的原因。对一般二元矩阵，判定是否存在 $\mathrm{wt}(e)\le t$ 且 $H{e}^T=s$ 的错误，是经典 NP 完全问题；这并不否定 Hamming 码等特定结构拥有高效译码算法。[2]

基础综合译码每次选一个码字。列表译码理路列表译码List decoding允许每个接收词对应一个受控候选列表，从而在组合意义上越过唯一译码半径。则允许返回给定半径内的多个候选，改变的是输出目标与算法任务，而不是简单把一次首领猜测重复执行。理解这些区别，有助于分开校验信息、错误模型和译码算法各自承担的作用。

特殊求值结构可以避免枚举秩错误陪集 ​

若码本是Gabidulin码理路Gabidulin码与Moore求值Gabidulin code · Gabidulin evaluation code在底域独立的求值点上评价低q次数线性化消息，构造达到秩Singleton界的线性码，并证明最小距离与任意k个坐标的擦除恢复。，且错误预算按底域秩给定，插值译码器理路Gabidulin码的插值译码Gabidulin interpolation decoder · Linearized interpolation decoding用首一错误湮灭多项式建立扩域线性插值系统，经左因子形式复合除法与残差秩复核，返回唯一半径内码字或完整的无半径内码字结论。可先解 $N(g_i)=\mathrm{\Lambda }(y_i)$ 的扩域线性系统，再按 $N=\mathrm{\Lambda }\circ f+R$ 求形式商和余式，最后重编码并检查残差秩。半径满足 $2t\le n-k$ 时，它完整判定有没有距离至多 $t$ 的码字。

与本页一样，合法候选与真实发送者必须分开。无错输入也可能有多份辅助 $\mathrm{\Lambda }$，但所有插值解给同一条消息；若真实错误超预算，接收词仍可能落入另一合法纠错球。这个结构化算法没有解决任意线性码的一般译码问题。