|
汉明码历史 汉明码（Hamming Code），是在电信领域的一种线性调试码，以发明者理查德·卫斯里·汉明的名字命名。汉明码在传输的消息流中插入验证码，当计算机存储或移动数据时，可能会产生数据位错误，以侦测并更正单一比特错误。由于汉明编码简单，它们被广泛应用于内存（RAM）和磁盘纠错的编码。汉明码不仅可以用来检测转移数据时发送的错误，还可以用来修正作物。(汉明码只能发现和修正一位错误，对于两位及两位以上的错误无法发现和纠正)。 1940年，汉明于贝尔实验室（Bell Labs）工作，运用贝尔模型V（Bell Model V）电脑，一个周期时间在几秒钟内的机电继电器机器。输入端是依靠打孔卡（Punched Card），这不免有些读取错误。在平日，特殊代码将发现错误并闪灯（flash lights），使得操作者能够纠正这个错误。在周末和下班期间，在没有操作者的情况下，机器只会简单地转移到下一个工作。汉明在周末工作，他对于不可靠的读卡机发生错误后，总是必须重新开始项目变得愈来愈沮丧。在接下来的几年中，他为了解决调试的问题，开发了功能日益强大的调试算法。在1950年，他发表了今日所称的汉明码。现在汉明码有着广泛的应用。 汉明码原理 设将要进行检测的二进制源码为n位，为使其具有纠错能力，需要再加上k位的检测位，组成n+k=m位的二进制。那么，新增加的检测位数k应满足：
这就是汉明码不等式，规定所得到的m位编码$2^k(k \geq 0 | 2^k < n+k)$位上插入特殊的校验码，其余位把源码按顺序放置。n位二进制和校验码位数k的关系： n k最小值
1 2
2~4 3
5~11 4
12~26 5
27~57 6
57~120 7
汉明码编码方式1编码规则：在新的编码的$2^{(k-1)} (k \geq 0)$位上填入0(即校验位)。 在新的编码的其余位把源码按原顺序填入校验位的编码方式为：第k位校验码从则从新的编码的第$2^{(k-1)}$位开始，每计算$2^{(k-1)}$位的异或，跳$2^{(k-1)}$位，再计算下一组$2^{(k-1)}$位的异或，填入$2^{(k-1)}$位。 比如：第1位校验码位于新的编码的第1位$2^{(1-1)}==1$(汉明码从1位开始)，计算1,3,5,7,9,11,13,15,…位的异或，填入新的编码的第1位。第2位校验码位于新的编码的第2位$2^{(2-1)}==2$，计算2,3,6,7,10,11,14,15,…位的异或，填入新的编码的第2位。第3位校验码位于新的编码的第4位$2^{(3-1)}==4$，计算4,5,6,7,12,13,14,15,20,21,22,23,…位的异或，填入新的编码的第4位。第4位校验码位于新的编码的第8位$2^{(4-1)}==8$，计算8-15,24-31,40-47,…位的异或，填入新的编码的第8位。第5位校验码位于新的编码的第16位$2^{(5-1)}==16$，计算16-31,48-63,80-95,…位的异或，填入新的编码的第16位。
编码示例： 以10101源码为例，$n=5$,由公式$2^k-1 \geq n+k$得$k=4$，如下表所示编码结果为001101011。 1 2 3 4 5 6 7 8 9
$2^{(1-1)}$校验位 $2^{(1-1)}$校验位 1 $2^{(1-1)}$校验位 0 1 0 $2^{(1-1)}$校验位 1
0 0 1 0 0 1 0 0 1
0(计算1，3，5，7，9位异或) 0(计算2，3，6，7位异或) 1 1(计算4,5,6,7位异或) 0 1 0 (计算8，9位异或) 1
计算校验码的第1位（1,3,5,7,9进行异或）: 结果为0，所以汉明码第2^0位为0，结果为0 _ 1 _ 0 10 _ 1 计算校验码的第2位（2,3,6,7进行异或）: 结果为0，所以汉明码第2^1位为0，结果为001 _ 0 10 _ 1 计算校验码的第3位（4,5,6,7进行异或）: 结果为1，所以汉明码第2^2位为0，结果为0011 0 10 _ 1 计算校验码的第4位（8, 9进行异或）: 结果为0，所以汉明码第2^3位为1，结果为001101011 所以最终编码为001101011.
汉明码编码方式2通过k值将源码分为$P_n$组，第1组为$2^0$，第2组为$2^1$，第3组为$2^2$，同理以此类推分组按照$2^{(k-1)}$。同时分组后插入的校验码的位置也是按照次规律插入，$2^0$位插入第1个校验码，即$P_1$组第1位，$2^1$位插入第2个校验码，即$P_2$组第1位，$2^2$位插入第3个校验码，即$P_3$组第1位，以此类推。 P1组包含(1(校验码),3,5,7,9,11...位)
P2组包含(2(校验码),3,6,7,10,11,14,15...位)
P3组包含(4(校验码),5,6,7,12,13,14,15...位)
...
同时也可以通过下表方式来划分组。 编号 1 2 3 4 5 6 7 8
二进制 0001 0010 0011 0100 0110 0111 1000 1001 将编号转成二进制从右向左，如果第1位是1，例如编号是1,3,5,7....的就分入P1组，如果第2位是1的，例如编号2,3,6,7,10...的就分入第P2组，以此类推将所有的编号分入相应的组中。 当分好组之后，P1组中第1位（校验位）应使1，3，5，7，9，11...位中“1”的个数为偶数。P2组中第2位（校验位）应使2，3，6，7，10，11，14，15...位中“1”的个数为偶数。P3组中第4位（校验位）应使4，5，6，7，12，13，14，15...位中“1”的个数为偶数。汉明码还存在配奇原则，与之相反。
编码示例： 以10101源码为例，$n=5$,由公式$2^k-1 \geq n+k$得$k=4$，如下表所示编码结果为001101011，C1,C2,C3,C4为插入的校验码。 1 2 3 4 5 6 7 8 9
$2^{(1-1)}$校验位 $2^{(1-1)}$校验位 1 $2^{(1-1)}$校验位 0 1 0 $2^{(1-1)}$校验位 1
C1 C2 B1 C3 B2 B3 B4 C4 B5 如果按照配偶原则来配置汉明码，则C1应使1,3,5,7,9位中“1”的个数为偶数；C2应使2,3,6,7位中“1”的个数为偶数；C3应使4,5,6,7位中“1”的个数为偶数；C4应使8,9位中的“1”的个数为偶数。所以10101源码的汉明码为001101011。 汉明码的纠错 根据以上说的汉明码的配偶原则和配奇原则我们来看汉明码的纠错。设接收到的错误汉明码（按配偶原则配置）是001101001，我们可以根据上述规律来确定出错位。 序号 1 2 3 4 5 6 7 8 9
接收到的汉明码 0 0 1 1 0 1 0 1 1 那么新的检测位为： P1=1位^3位^5位^7位^9位，得到0。 P2=2位^3位^6位^7位，得到0。 P3=4位^5位^6位^7位，得到0。 P4=8位^9位，得到1。 根据P4P3P2P1构成的二进制是1000，将1000转换成十进制为8，说明是第8位出错，或者根据配偶原则的规律，其“1”的个数必须是偶数也能判断出是第8位，所以第8位应将“1”改为“0”，那么正确的汉明码应为001101011。 汉明码属于分组奇偶校验，P4P3P2P1=0000，说明接收方生成的校验位和收到的校验位相同，否则不同说明出错。由于分组时校验位只参加一组奇偶校验，有效信息参加至少两组奇偶校验，若果校验位出错，P4P3P2P1的某一位将为1，刚好对应位号8、4、2、1；若果有效信息出错，将引起P4P3P2P1中至少两位为1。
以上博文参考自：
|
