海明校验码的笔记

海明校验码

简述

海明校验码由 Richard Hamming 提出，是一种多重（复式）的奇偶检错系统，用于检错和纠错。

海明校验是对偶校验的扩展，引入了更多的校验位来弥补奇偶校验的局限性。

原理

假设有效信息有 \(k\) 位，分成 \(r\) 组，要组成 \(n\) 位的海明校验码。每组设一个校验位，则需要 \(r\) 个校验位，\(r\) 个校验位组成一个 \(r\) 位的指误字，可以表示 \(2^r\) 种状态，如果指误字是全 0 则表示无误，因此有 \(2^r-1\) 种状态表示错误，所以如果要海明校验码能发现并纠正一位的错误，则必须要满足下面的是关系式（香农第二定理）： \[ n=k+r\leq2^r-1 \] 假设 \(k=8\)，则代入公式得到： \[ 8+r\leq2^r-1 \] 导出： \[ r\geq4 \] 故取 \(r=4\)

校验码计算

假设原始信息如下：

位置	8	7	6	5	4	3	2	1
信息	0	1	1	0	1	1	1	0

首先我们知道校验码位数为 4，确定校验码的位置在 1，2，4，8 上，得到新的信息如下：

位置	12	11	10	9	8	7	6	5	4	3	2	1
信息	0	1	1	0	H8	1	1	1	H4	0	H2	H1

随后我们计算校验码的值，每一个校验码只计算其对应二进制位为 1 的位置，即：

位置	二进制码
1	0001
2	0010
3	0011
4	0100
5	0101
6	0110
7	0111
8	1000
9	1001
10	1010
11	1011
12	1100

那么海明码的计算为：

海明码	出现的位置	对应位置上的值异或	结果
H1	3，5，7，9，11	\(0\oplus1\oplus1\oplus0\oplus1\)	1
H2	3，6，7，10，11	\(0\oplus1\oplus1\oplus1\oplus1\)	0
H4	5，6，7，12	\(1\oplus1\oplus1\oplus0\)	1
H8	9，10，11，12	\(0\oplus1\oplus1\oplus0\)	0

即对应信息位的偶校验码——保持为偶数个1（包括自身）

最终得到的信息为：

位置	12	11	10	9	8	7	6	5	4	3	2	1
信息	0	1	1	0	0	1	1	1	1	0	0	1

其中海明校验码为 H8H4H2H1 = 0101

校验和纠错

假设信息 0110 0111 1001 被错误传输为 0111 0111 1001

我们对信息重新算出校验码 H8H4H2H1 = 1100

而我们可以从信息中提取出原校验码为 0101

我们对其进行异或得到 \(0101\oplus1100=1001\)，即第 9 位出错

脚本

def createHamming(data: str):
    """
    对原数据加入海明校验码，并返回 Hamming 对象
    >>> h = h = createHamming('01101110')
    >>> h.msg(), h.code()
    ('01101110', '0101')

    `Parameters`:
        data - 原数据
    
    `Returns`:
        Hamming 对象
    """
    k = len(data)
    for r in itertools.count():
        if k + r <= (1 << r) - 1:
            break
    itdata = iter(data[::-1])
    newdata = [int(next(itdata)) if (i & (i - 1)) else None for i in range(1, k + r + 1)]
    for i, v in enumerate(newdata):
        if v is None:
            t = 0
            for j in range(i + 1, len(newdata)):
                if newdata[j] is None:
                    continue
                if ((j + 1) & (i + 1)):
                    t ^= newdata[j]
            newdata[i] = t
    return ''.join(map(str, newdata[::-1]))