引言
二元 Hamming 码 [7,4,3] 能纠正任意一位翻转。但其最小距离为 3,因此不能可靠地区分一位翻转与两位翻转。两位翻转产生的伴随式与某个单错相同,若译码器把它当成单错来“纠正”,反而会出错。
添加一个总奇偶校验位可以解决这一问题,得到扩展 Hamming 码 [8,4,4]。若明确保证翻转的位数不超过二,译码器可以:
- 纠正任意一位翻转;
- 把任意两位翻转识别为不可纠正;
- 不会把单错和双错混淆。
这称为 SECDED,即单错纠正、双错检测。本节从头构造译码器,也会精确指出它不能保证什么。每个实际单错都得到纠正,每个实际双错都会被标记;至多两位翻转的保证则使我们能够从伴随式判断发生的是哪一类。没有这个保证时,同一译码器可能返回一个有效但错误的码字。
以下所有运算都在 F2 中进行,所以 1+1=0。字按从左到右的位置 1,…,8 索引,并写成行向量。
校验矩阵
用向量 hi∈F23 标记位置 i:
h1=(1,0,0),h2=(0,1,0),h3=(0,0,1),h4=(1,1,0),
h5=(1,0,1),h6=(0,1,1),h7=(1,1,1),h8=(0,0,0).
前七个标签恰好是 F23 的七个非零向量,第八个是零向量。因此八个标签互不相同,下面的大部分结论都由这一事实推动。
定义 1.2.1
(扩展 Hamming 校验矩阵)
定义 F2 上的 4×8 矩阵 H:第 i 列的前三项是列向量 hi,每列第四项均为 1。具体地,
H=10010101001111011011011111110001=(H7101).其中 H7 是列为 h1,…,h7 的 3×7 Hamming 校验矩阵,1 是长度为 7 的全一行。扩展 Hamming 码为
C={x∈F28:HxT=0}.
记录各行检查的位置很有用:第一行检查 {1,4,5,7},第二行检查 {2,4,6,7},第三行检查 {3,5,6,7},第四行检查全部八位。
矩阵 H 的秩为 4。因此 C 是长度为 8、维数 k=4 的线性码,共有 24=16 个码字。
考察 H 的第 1,2,3,8 列:
1001,0101,0011,0001.把它们并排组成的 4×4 矩阵是下三角矩阵,对角线全为 1,行列式为 1=0。故四列线性无关,H 的秩至少为 4;它只有四行,秩也不可能更大。由秩—零化度定理,dimkerH=8−4=4。
四项校验的含义
写 x=(x1,…,x8) 和 x1:7=(x1,…,x7)。条件 HxT=0 分成
H7x1:7T=0和x1+x2+⋯+x8=0.
由于第八列以 h8=0 开头,前三行只涉及前七位;它们说明 x1:7 恰是一个 [7,4,3] Hamming 码字。第四行说明整个字的重量为偶数。
因此,给定 Hamming 码字 y∈F27,恰有一个位 x8 使 (y,x8)∈C,即
x8=y1+⋯+y7.
当 y 重量为偶数时此位为 0,为奇数时此位为 1。所以 C 正是 Hamming 码的奇偶扩展。这也符合维数计算:Hamming 码有 16 个码字,每个都唯一扩展。
概念视角代数
校验矩阵同时生成这个码
H 的每一行重量都是偶数,任意两行共有的位置数也是偶数:第 1 至 3 行两两共有两个位置,各自与第 4 行共有四个。因此每一行都通过全部四个校验,属于 C。由于 H 的秩为 4=dimC,它的行构成一组基底,所以 C 等于自身的对偶码。此外 wt(x+y)=wtx+wty−2∣x∩y∣,而正交的字共有偶数个 1,所以能被四整除的重量在相加后仍能被四整除。由行重量 4,4,4,8 出发,每个码字的重量都是 0、4 或 8,再次得到 d≥4。
最小距离为四
化简。 C 是线性码。码字 a,b 的距离等于 a+b 的重量,而 a+b 仍是码字。因此最小距离等于非零码字的最小重量。
关键恒等式。 若 x 的支集为 S,则 HxT=i∈S∑(第 i 列),从而
HxT=(i∈S∑hi, ∣S∣mod2).排除奇数重量。 若 ∣S∣ 为奇数,最后一项是 1,故 x∈/C。这一步同时排除重量 1 和 3;它依赖全一行。
排除重量二。 若 S={i,j} 且 i=j,前三项是 hi+hj。在 F23 中,hi+hj=0 当且仅当 hi=hj;标签互异,故 hi+hj=0,x∈/C。这是标签互异所起的作用。其中也包括 j=8:此时 hi+h8=hi,而 i≤7 时它非零。
达到重量四。 取 x=11010001,其支集为 {1,2,4,8}。于是
h1+h2+h4+h8=(1,0,0)+(0,1,0)+(1,1,0)+(0,0,0)=(0,0,0),且 ∣S∣=4 为偶数,所以 HxT=0,x 是重量为 4 的码字。
证明透视
矩阵每部分各司其职
关键一步是那条恒等式:它把伴随式拆成支集上标签之和与支集大小的奇偶性。拆开之后,H 的每部分只做一件事。奇偶校验行一步排除所有奇数重量;八个标签互异(包括零标签 h8)则排除重量二。单独任何一部分都不能保证距离为 4:仅有 Hamming 矩阵 H7 时允许重量为 3 的字 1101000,仅有奇偶校验行时允许重量为 2 的字 11000000。最后一步不可省略:排除重量一至三只证明 d≥4,具体码字 11010001 才证明 d≤4,论证至此闭合。
下文的译码器读取的,正是伴随式这种“标签部分加奇偶部分”的拆分。
伴随式与检测
收到 r∈F28 时,其伴随式为
HrT=(u,z),u=H7r1:7T∈F23,z=r1+⋯+r8∈F2.
设发送的是 c∈C,错误模式为 e,接收字为 r=c+e。则 HrT=HcT+HeT=HeT:伴随式只取决于错误,与发送的码字无关。 根据关键恒等式,支集为 S 的错误满足
u=i∈S∑hi,z=∣S∣mod2.
定理 1.2.5
(距离 d 可检测至多 d−1 个错误)
设线性码 C 的最小距离为 d,且 1≤wt(e)≤d−1。那么对每个 c∈C,c+e 都不是码字。
若 c+e∈C,由线性性得 e=(c+e)+c∈C。但 e 非零且重量小于 d,与 d 的定义矛盾。
这里 d=4,故重量为 1、2 或 3 的每个错误都产生非零伴随式,因而不能通过“HrT=0 吗?”的码字成员检验。
这是关于尝试纠正之前的检测:它本身没有说明随后纠错译码器会对接收字做什么。
SECDED 译码器及其保证
定理 1.2.6
(在至多两位翻转的保证下精确分类)
假设 r=c+e,其中 c∈C 且 wt(e)≤2。那么伴随式 (u,z) 决定错误重量,以下规则涵盖所有情况。
- u=0, z=0。 没有错误,r=c。
- z=1。 恰有一位翻转。其位置是满足 hi=u 的唯一 i∈{1,…,8}。特别地,u=0 指出第 8 位奇偶校验位。翻转 ri 即恢复 c。
- z=0, u=0。 恰有两位翻转。译码器必须标记为不可纠正,不能试图确定是哪一对位置。
分别考虑错误重量。
- 重量 0: 伴随式是 (0,0)。
- 重量 1,位置 i: 伴随式是 (hi,1)。八个标签互异,而 ∣F23∣=8,所以每个 u 恰对应一个位置,i 由 u 确定。
- 重量 2,位置 i=j: 伴随式是 (hi+hj,0)。上文已证明 hi+hj=0,故 u=0。
三个结果集合 {(0,0)}、{z=1}、{z=0,u=0} 两两不交。因此在给定保证下,观察到的情况确定 e 的重量。
为什么不能确定那一对? 两位置错误有 (28)=28 种,但非零 u 只有 7 种。每个非零 u 恰是 4 对标签之和:对每个位置 i,配对位置 j 由 hj=hi+u 唯一确定,得到 8 个有序对,即 4 个无序对。所以规则 3 总有四重歧义。
若译码器只读 u,并像 [7,4,3] Hamming 译码器那样翻转标签为 u 的位置,就会把双错变成三错。从 c=00000000 出发翻转第 1、2 位,接收 11000000,其 u=110=h4。翻转第 4 位得 11010000,其前七位是 Hamming 码字 1101000,于是数据部分被“确定地”改错。规则 3 正是为阻止这种情况:当 z=0 且 u=0 时,不翻转任何位。
要纠正所有 t 位错误,需要 d≥2t+1;所以 d=4 只给出 t=1,而不是 t=2。具体地,11100010 是码字(支集 {1,2,3,7},标签之和为零,大小为偶数),而接收字 11000000 与 00000000 和 11100010 的距离都是 2。多出的一个单位距离换来的是检测第二个错误,而不是纠正它。
译码过程实例
三个例子中发送的码字都是 c=00000000。
接收字是 r=00001000。逐行检查:
- 第一行检查 {1,4,5,7},其中有一个 1,所以结果为 1。
- 第二行检查 {2,4,6,7},没有 1,结果为 0。
- 第三行检查 {3,5,6,7},其中有一个 1,结果为 1。
- 第四行总共数到一个 1,结果为 1。
伴随式为 (u,z)=(101,1)。因 z=1,使用规则 2;u=101=h5,所以翻转第 5 位,输出正确的 00000000。
接收字为 r=11000000。第一行因第 1 位给出 1,第二行因第 2 位给出 1,第三行为 0,第四行数到两个 1,给出 0。
伴随式为 (110,0)。由于 z=0 且 u=0,规则 3 适用,译码器标记该字不可纠正。
再比较第 3、7 位错误,接收字为 r′=00100010。其 u=h3+h7=(0,0,1)+(1,1,1)=(1,1,0),且 z=0,故伴随式同为 (110,0)。
事实上,产生 u=110 的四对是 {1,2}、{3,7}、{4,8}、{5,6};单靠伴随式无法选择其中一对。
接收字为 r=11010000。第一行看到第 1、4 位,给出 0;第二行看到第 2、4 位,给出 0;第三行为 0;第四行数到三个 1,给出 1。
伴随式为 (000,1),非零,因此错误被检测出来:r∈/C。
然而,按规则译码时 z=1 且 u=0=h8,译码器翻转第 8 位并输出 11010001。它确是非零码字,却不是发送的码字;这是误纠正。
下面的互动图让你翻转所选码字的任意位,并显示伴随式 (u, z)、所用规则与译码器输出,可见单位翻转被纠正、双位翻转被标记、三位翻转被误纠。
探索MATH4260 · [8,4,4]
向 [8,4,4] 码加入错误并读出伴随式
先选定发送的码字 c,再在位置 1 至 8 切换错误位。图中会形成 r = c + e,用 H 的四行算出伴随式 (u, z),应用三条 SECDED 规则,并把译码器输出与 c 比较。
按位置列出的字 | 位置 1 | 位置 2 | 位置 3 | 位置 4 | 位置 5 | 位置 6 | 位置 7 | 位置 8 |
|---|
| 发送 c | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
|---|
| 错误 e | 0 | 0 | 0 | 0 | 1* | 0 | 0 | 0 |
|---|
| 接收 r | 0 | 0 | 0 | 0 | 1* | 0 | 0 | 0 |
|---|
| 译码器输出 | 0 | 0 | 0 | 0 | 0* | 0 | 0 | 0 |
|---|
H 各行的伴随式| 行 | 校验的位置 | 其中 r = 1 的位置 | 该行之和 |
|---|
| 1 | {1,4,5,7} | {5} | 1 |
|---|
| 2 | {2,4,6,7} | 无 | 0 |
|---|
| 3 | {3,5,6,7} | {5} | 1 |
|---|
| 4 | {1,2,3,4,5,6,7,8} | {5} | 1 |
|---|
伴随式 (u, z) = (101, 1). 规则 2:z = 1,假定有一位翻转,位置 i 满足 h_i = u;此处 i = 5。
- 错误重量 wt(e)
- 1
- 保证 wt(e) ≤ 2 成立
- 是
- 伴随式 (u, z)
- (101, 1)
- 结果
- 正确
- 接收 r
- 00001000
- 译码器输出
- 00000000
结果: 正确. 保证之内的单一翻转:规则 2 翻转位置 5,恢复了 c。
为何总奇偶校验位能区分各种情况
c + e 的伴随式只取决于 e:u 是翻转位置标签 h_i 之和,z 是翻转个数的奇偶性。
在 wt(e) ≤ 2 的保证下,z = 1 表示恰有一位翻转,而八个标签互不相同,所以 u 指出其位置;z = 0 且 u ≠ 0 表示两位翻转,因为 i ≠ j 时 h_i + h_j ≠ 0。
超出保证时,三位翻转同样有 z = 1,规则 2 会再改动一个位置,输出 c 加上一个重量为 4 的码字,是有效但错误的码字。
本图采用本节固定的码及其 H。确定性规则会应用于任何重量的错误集合;完整的分类只在 wt(e) ≤ 2 下成立。图中没有为任何错误模式的出现概率建模。
超出保证范围
反例模式
有效输出不一定是正确输出
容易产生的说法。 “SECDED 纠正每个单错、检测每个双错,因此只要输出码字时没有报警,消息就是对的。”
反例。 第三个实例推翻了这一说法。三位翻转产生 (000,1),与第 8 位单错的伴随式相同。译码器返回有效码字 11010001,没有报警,但消息错误。
更严重的失败。 错误 e=11010001 本身就是码字,因此 HeT=0,r=e 被当作无错误通过。译码器输出错误码字,完全没有警告。
第三个例子并非偶然:下一个定理表明每个三位错误都会如此。
设 wt(e)=3。那么 c+e 的伴随式满足 z=1;按上述规则译码时,译码器翻转一位,输出一个不同于 c 的码字。
奇数重量给出 z=1。译码器翻转满足 hi=u 的位置 i;翻转后伴随式变为
(u+hi, 1+1)=(0,0),因此输出 c+e+ei 是码字,故 e+ei∈C。此外 e+ei 非零,因为重量为 3 的向量不能等于重量为 1 的向量,所以输出不同于 c。C 没有重量小于 4 的非零码字,而 e+ei 的重量至多为 4,因此其重量恰为 4。
准确的保证如下:
- 无需任何错误重量保证: 纠正之前的成员检验能检测每个重量为 1 至 3 的错误。每个单错都会被纠正,但伴随式本身不能证实实际错误重量。一些重量为 4 的错误,即本身为码字的错误(如 11010001),完全检测不到。
- 保证 wt(e)≤2 时: 单错被纠正,双错被标记;任何具体双错位置对都无法确定。
若不说明保证就说“检测两个、纠正一个”,容易引出错误结论。在允许三位翻转的模型里,纠错规则会把每个可检测的三错变成无提示的错误答案。本节不声称物理硬件中任何错误模式的概率,也不声称对有意选择错误的对手提供安全性。
快速检查
(在至多两位翻转的保证下,伴随式为 (011,1)。译码器如何操作?)
解答 · 答案
由于 z=1,恰有一位翻转。标签 u=011=h6,故翻转第 6 位。
练习
快速检查
(字 1101000 是 [7,4,3] Hamming 码字。求其扩展码字,并用 H 验证。)
解答 · 引导解答
y=(1,1,0,1,0,0,0)。先验证它是 Hamming 码字:支集为 {1,2,4},且 h1+h2+h4=(0,0,0)。y 的重量为奇数 3,所以奇偶校验位 x8=1,扩展字为 x=11010001。
用 H 验证:第一行检查的 {1,4,5,7} 中,第 1、4 位为 1,和为 0;第二行检查的 {2,4,6,7} 中,第 2、4 位为 1,和为 0;第三行检查的 {3,5,6,7} 中没有 1,和为 0;第四行总共数到四个 1,和为 0。故 HxT=0,x∈C。
快速检查
(发送码字 c=11010001,只有奇偶校验位翻转。计算伴随式,并在至多两位翻转的保证下译码。)
解答 · 引导解答
接收字为 r=11010000。因 e=e8,伴随式为 (h8,1)=(000,1)。逐行看:第一行第 1、4 位为 1,结果为 0;第二行第 2、4 位为 1,结果为 0;第三行没有 1,结果为 0;第四行有三个 1,结果为 1。规则 2 对 u=0 适用,译码器翻转第 8 位,正确恢复 11010001。
这个接收字与三错实例中的完全相同:同一个 r 可来自 11010001 的单错,也可来自 00000000 的三错。只有所给保证能选择第一种解释。
快速检查
(从 00000000 出发,说明位置 {1,2} 与 {3,7} 的错误产生相同伴随式,并解释译码器必须如何处理。)
解答 · 引导解答
对 {1,2},h1+h2=(1,0,0)+(0,1,0)=(1,1,0),且 z=0。对 {3,7},h3+h7=(0,0,1)+(1,1,1)=(1,1,0),且 z=0。两者都给出 (110,0);{4,8} 和 {5,6} 也给出同一结果。
由于 z=0、u=0,规则 3 适用。在保证下译码器知道恰有两位翻转,却无法知道哪两位,必须标记不可纠正。若翻转四对候选中任何一对,在四种可能情况中有三种会输出错误码字。
快速检查
(从 00000000 出发,翻转第 1、2、4、8 位。接收端观察到什么?)
解答 · 引导解答
接收字是 r=11010001。第一行看到 {1,4},结果为 0;第二行看到 {2,4},结果为 0;第三行没有看到 1,结果为 0;第四行数到四个 1,结果为 0。伴随式为 (000,0),接收端把 11010001 当作无错误接受。
此错误本身是非零码字,故不可检测。检测定理只覆盖重量不超过 d−1=3 的错误,因而在这里不提供保证。
快速检查
(在至多两位翻转的保证下,解释译码器为什么能纠正单错并标记双错。若这个保证不成立,实际发生三位翻转,解释同一规则为什么会误纠正。)
解答 · 引导解答
单错。 第 i 位单错给出 (hi,1)。八个标签互异并覆盖整个 F23,所以 u 恰指出一个位置;翻转该位便恢复 c。
双错。 {i,j} 两位翻转给出 (hi+hj,0)。因为 hi=hj,u 非零,伴随式既不是 (0,0),也不属于 z=1 的情况。故规则 3 触发并标记该字。由于每个非零 u 来自四对不同位置,无法恢复哪一对出错。
三错。 三位翻转的重量为奇数,故 z=1,与单错无法区分。译码器翻转标签为 u 的位置,落到码字 c+e+ei。其中 e+ei 是重量为 4 的非零码字,所以输出错误。例如 {1,2,4} 的错误给出 (000,1),译码器输出 11010001 而非 00000000。
分类保证依赖所述假设。没有这个假设时,z=1 的伴随式不能证明仅有一位翻转。