关于海明码编码方式的学习

前言

机组课的海明（汉明）码学的不太行，课本直接不提，老师课件内容和维基百科和各种博客都有些出入，高位低位换来换去的，有些迷糊，重新学习一下（本片以《计算机组成原理》唐朔飞版为主）

简介

在电信领域中，汉明码（英语：hamming code），也称为海明码，是(7,4)汉明码推广得到的一种线性纠错码，由理查德·卫斯里·汉明于1950年发明。

用数学术语来说，汉明码是一种二元线性码。对于所有整数 r ≥ 2，存在一个分组长度 n = 2r − 1、k = 2r − r − 1 编码。因此汉明码的码率为 R = k / n = 1 − r / (2r − 1)，对于最小距离为3、分组长度为 2r − 1 的码来说是最高的。汉明码的奇偶检验矩阵的是通过列出所有长度为 r 的非零列向量构成的。

海明码本质是一种多重奇偶校验码，可检测以为错误

编码

确定校验位的个数

2^k^ >= k+n+1

其中，k为校验位的个数；n为原数据位个数

确定校验位置：2的幂次数（1，2，4，8……）

计算校验位

P1=D3$\bigoplus$ D5$\bigoplus$ D7

P2=D3$\bigoplus$ D6$\bigoplus$ D7

P4=D5$\bigoplus$ D6$\bigoplus$ D7

（直接计1的个数，1的个数为奇数则为1，个数为偶数则为0）

确定各个校验位的检测位数：

P1可理解为倒数第一位是1的二进制数，如112(3),1012(5),1112(7)

P2为倒数第二位是1的二进制数，如112(3),1102(6),1112(7)

P4位倒数第三位是1的二进制数，如1012(5),1102(6),1112(7)

通用方法

参见汉明码 - 维基百科，自由的百科全书 (wikipedia.org)

例 写出1100的海明码

确定k的位数。n=4，则k=3

（为了应试，直接记原码与校验码位数关系1->2；2~4->3；5~11->4）

确定校验码位置，即1，2，4

计算

P1=1$\bigoplus$1$\bigoplus$0（3，5，7）

P2=1$\bigoplus$0$\bigoplus$0（3，6，7）

P3=1$\bigoplus$0$\bigoplus$0（5，6，7）

得P1=0 P2=1 P3=1

则D4=0 D2=1 D1=1

补全

位置	D1	D2	D3	D4	D5	D6	D7
值	1	1	1	0	1	0	0

纠错 定义校验位Si

S1=D1$\bigoplus$D3$\bigoplus$ D5$\bigoplus$ D7

S2=D2$\bigoplus$D3$\bigoplus$ D6$\bigoplus$ D7

S3=D4$\bigoplus$D5$\bigoplus$ D6$\bigoplus$ D7

若S3 S2 S1为000，则无错误；若S3 S2 S1为001，则第一位错误，同理如下

S3 S2 S1 000 001 010 011 100 101 110 111 错误位置 无 1 2 3 4 5 6 7 检测出错误位翻转即可