每日精学 199｜二元线性码的擦除恢复方程

2026-09-25

← 技术专题 · 每日精学目录

雷达 · 通信 · 电子战　/　基础精学 199

擦除符号不同于错误符号，其未知位置已明确。接收机不必搜索错误位置，只需利用保留下来的可靠位计算右端项并求出未知变量。

01
模型与符号

已知位完全正确，擦除集合 \mathcal E 已知，H_{\mathcal E} 是校验矩阵的擦除列子矩阵；模二运算下求解。

\mathcal E：擦除位置（集合）

\mathcal K：已知位置（集合）

H_{\mathcal E}：擦除列（矩阵）

\boldsymbol z：校验右端项（比特）

r：擦除子矩阵秩（维数）

02
从模型到公式

约束分块

合法码字满足

H_{\mathcal E}\boldsymbol c_{\mathcal E}^T+H_{\mathcal K}\boldsymbol c_{\mathcal K}^T=0.

在二元域负号等于正号，故

H_{\mathcal E}\boldsymbol c_{\mathcal E}^T=H_{\mathcal K}\boldsymbol c_{\mathcal K}^T=\boldsymbol z.

右端只依赖未擦除的已知数据。


唯一性

若两个解都成立，其差位于齐次核中：

H_{\mathcal E}(\boldsymbol x_1+\boldsymbol x_2)=0.

唯一恢复当且仅当

\operatorname{rank}_{\mathrm{GF}(2)}H_{\mathcal E}=|\mathcal E|.

若秩为

r<|\mathcal E|

且方程一致，共有

2^{|\mathcal E|-r}

个解。


固定两位恢复

对七位Hamming码擦除位置三和五，校验关系直接给出

c_3=c_2\oplus c_6\oplus c_7,\qquad c_5=c_1\oplus c_3\oplus c_7.

任意两个互异非零列线性无关，因此

|\mathcal E|\le2\implies\text{唯一恢复}.

三列若异或为零则出现歧义，展示距离与擦除能力的联系。


擦除列相关性决定唯一恢复

已知擦除位置集合为 E 时，未知比特只出现在对应校验矩阵列中。唯一恢复的充要条件是

\operatorname{rank}(H_E)=|E|.

Hamming 校验矩阵的列均非零且互不相同，所以任意一列及任意两列在二元域上线性独立。

三列则可能满足

\boldsymbol h_i+\boldsymbol h_j+\boldsymbol h_k=0,

从而产生多个一致解。已知位置的两个擦除可恢复，与未知位置只保证单错纠正并不冲突；

擦除标志提供了额外的位置信息。固定模式解式不能推广成任意擦除模式的求解器。

03
物理含义

恢复过程利用冗余约束补齐缺失信息，已知位置把问题从组合搜索变为线性方程。错误标记若把错误值当成已知数据，方程右端就会被污染。

04
固定参数算例

穷举十六个码字，对固定位置三和五擦除后通过显式公式恢复；同时枚举所有一、二、三列子集，在二元域消元检查秩和可恢复性。

固定参数数值验证结果
量数值
fixed pattern messages16
fixed recovery bit errors0
unique one erasure sets7
unique two erasure sets21
unique three erasure sets28
ambiguous three erasure sets7
three erasure sets35
图 1：Hamming擦除列秩与固定双擦除恢复图 1：Hamming擦除列秩与固定双擦除恢复

图 1　Hamming擦除列秩与固定双擦除恢复

表中数值和图中曲线由 MATLAB 实际运行得到，随机种子为 20261118；运行版本与完整结果另存为独立文件。

05
数字实现的边界

RTL 固定恢复位置三、五，输入这两位内容被忽略，其余位作为可靠已知量；输出完整七位码字。它不是可配置高斯消元器，只实现声明擦除模式的解式。 模块采用同步高有效复位及 valid 握手；

有效输入在一个时钟沿登记输出，空拍不改变数据寄存器而清除输出有效标志。端口采用有符号 32 位容器，实际有效范围按子核定义约束。自检覆盖多组有效输入、空拍保持及复位；

它验证指定算术或地址子核，不代表完整通信系统或完整译码器已经完成硬件验证。

独立自检程序已在 Icarus Verilog 13.0 中实际运行并通过。该结果不包含器件综合、静态时序分析或板级测试。

06
适用范围

用于已知丢失位置的块码恢复、部分存储失效建模及擦除译码器算术验证。一般模式需要可配置列选择和二元消元控制。

07
工程上需要注意

已知位含错会使恢复结果错误。

擦除数小不必然保证一般码可恢复。

实数矩阵秩不能替代二元域秩。

固定模式RTL不覆盖任意擦除集合。

擦除恢复的唯一性由擦除列子矩阵满列秩确定。明确位置知识使恢复转化为有限域线性求解，但依赖其余数据真实可靠。

内容依据：每日精学第 199 课《二元线性码的擦除恢复方程》。图表沿用原课固定参数数值结果，属于数值验证，不代表设备实测。

阅读7
分享
写评论...