海明码校验 (1)

1、奇偶校验码1.奇偶校验概念 奇偶校验码是一种最简单的数据校验码，它的码距等于2，可以检测出一位错误（或奇数位错误），但不能确定出错的位置，也不能检测出偶数位错误。 奇偶校验实现方法是：由若干位有效信息（如一个字节），再加上一个二进制位（校验位）组成校验码。 图2-1奇偶校验码1奇偶校验规律 校验位的取值（0或1）将使整个校验码中“1”的个数为奇数或偶数，所以有两种可供选择的校验规律： 奇校验整个校验码（有效信息位和校验位）中“1”的个数为奇数。 偶校验整个校验码中“1”的个数为偶数。 22.简单奇偶校验 简单奇偶校验仅实现横向的奇偶校验，下表给出几个字节的奇偶校验码的编码结果。最高一位为校验位

2、，其余8位为信息位。在实际应用中，多采用奇校验，因为奇校验中不存在全“0”代码，在某些场合下更便于判别。 有效信息（8位）奇校验码（9位）偶校验码（9位）1001011032.简单奇偶校验（续） 校验位形成 当要把一个字节的代码D7D0写入主存时，就同时将它们送往奇偶校验逻辑电路，该电路产生的“奇形成”信号就是校验位。它将与8位代码一起作为奇校验码写入主存。 若D7D0中有偶数个“1”，则“奇形成”=1， 若D7D0中有奇数个“1”，则“奇形成”=0。4奇偶校验位的形成及校验电路图2-2 奇偶校验位的形成及校验电路52.简单奇偶校验（续） 校验检测 读出时，将读出的9位代码（8位信息位和1位校

3、验位）同时送入奇偶校验电路检测。若读出代码无错，则“奇校验出错”=0；若读出代码中的某一位上出现错误，则“奇校验出错”=1，从而指示这个9位代码中一定有某一位出现了错误，但具体的错误位置是不能确定的。63.交叉奇偶校验 计算机在进行大量字节（数据块）传送时，不仅每一个字节有一个奇偶校验位做横向校验，而且全部字节的同一位也设置一个奇偶校验位做纵向校验，这种横向、纵向同时校验的方法称为交叉校验。 第1字节 1 1 0 0 1 0 1 1 1 第2字节 0 1 0 1 1 1 0 0 0 第3字节 1 0 0 1 1 0 1 0 0 第4字节 1 0 0 1 0 1 0 1 0 1 0 0 1 1

4、0 0 073.交叉奇偶校验（续） 交叉校验可以发现两位同时出错的情况，假设第2字节的A6、A4两位均出错，横向校验位无法检出错误，但是第A6、A4位所在列的纵向校验位会显示出错，这与前述的简单奇偶校验相比要保险多了。 8海明校验码 海明码是一种可以纠正一位差错的编码。它是利用在信息位为k位，增加r位冗余位，构成一个n=k+r位的码字，然后用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的一位错。它必需满足以下关系式： 2r k+r+1 或 2r n+19海明校验码 海明码(Hamming Code )编码的关键是使用多余的奇偶校验位来识别一位错误。 码字(Code Wor

5、d) 按如下方法构建： 1、把所有2的幂次方的数据位标记为奇偶校验位(编号为1, 2, 4, 8, 16, 32, 64等的位置) 2、其他数据位用于待编码数据. (编号为3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17等的位置) 10海明校验码 3、每个奇偶校验位的值代表了代码字中部分数据位的奇偶性，其所在位置决定了要校验和跳过的比特位顺序。 位置1：校验1位，跳过1位，校验1位，跳过1位(1,3,5,7,9,11,13,15,) 位置2：校验2位，跳过2位，校验2位，跳过2位 (2,3,6,7,10,11,14,15,) 位置4：校验4位，跳过4位，校验4

6、位，跳过4位 (4,5,6,7,12,13,14,15,20,21,22,23,) 位置8：校验8位，跳过8位，校验8位，跳过8位(8-15,24-31,40-47,) 11海明校验码 采用偶校验，如果全部校验的位置中有奇数个1，把该奇偶校验位置为1；如果全部校验的位置中有偶数个1，把该奇偶校验位置为0. 12海明校验码 举例说明： 一个字节的数据：10011010 构造数据字(Data Word),对应的校验位留空_ _ 1 _ 0 0 1 _ 1 0 1 0 计算每个校验位的奇偶性 ( ?代表要设置的比特位): 13海明校验码 位置1检查1,3,5,7,9,11: ? _ 1 _ 0 0

7、1 _ 1 0 1 0. 偶数个1，因此位置1设为0，即: 0 _ 1 _ 0 0 1 _ 1 0 1 0位置2检查2,3,6,7,10,11: 0 ? 1 _ 0 0 1 _ 1 0 1 0. 奇数个1，因此位置2设为1，即: 0 1 1 _ 0 0 1 _ 1 0 1 0 14海明校验码 位置4检查4,5,6,7,12: 0 1 1 ? 0 0 1 _ 1 0 1 0. 奇数个1，因此位置4设为1，即: 0 1 1 1 0 0 1 _ 1 0 1 0位置8检查8,9,10,11,12: 0 1 1 1 0 0 1 ? 1 0 1 0. 偶数个1，因此位置8设为0，即: 0 1 1 1 0

8、0 1 0 1 0 1 0因此码字为: 0. 15海明校验码 上例中构建了一个码字 011100101010，假定实际接收到的数据 011100101110. 则接收方可以计算出哪一位出错并对其进行更正。方法就是验证每一个校验位。记下所有出错的校验位，可以发现校验位2和8的数据不正确. 错误校验位 2 + 8 = 10, 则位置10的数据出错。一般说来，对所有校验位进行检查, 将所有出错的校验位置相加, 得到的就是错误信息所在的位置. 16海明校验码 例1.已知：信息码为： 1 1 0 0 1 1 0 0 (r=4代表冗余位数，即校验码位数) 求：海明码码字。 17海明校验码 解：1)把冗余码

9、A、B、C、，顺序插入信息码中，得海明码 码字: A B 1 C 1 0 0 D 1 1 0 0 码位: 1 2 3 4 5 6 7 8 9 10 11 12 其中A,B,C,D分别插于2的k次方位(k=0,1,2,3)。码位分别为1,2,4,8。 18海明校验码 2)冗余码A,B,C,D的线性码位是：(相当于监督关系式) 监督关系式的推导： D C B A 1 0 0 0 1 2 0 0 1 0 3 0 0 1 1 4 0 1 0 0 5 0 1 0 1 6 0 1 1 0 7 0 1 1 1 8 1 0 0 0 9 1 0 0 1 10 1 0 1 0 11 1 0 1 1 12 1 1

10、0 0 根据上面表格得到 A B C D 19海明校验码 需要说明的是公式中参与计算的是表格中出现1的那个位 右边是数据位的二进制数,公式中的+表示异或 故此有如下表达式： A-1,3,5,7,9,11；(这里的1 3 5 7 9 11均为A那一列出现1的位) B-2,3,6,7,10,11； C-4,5,6,7,12；(注 5=4+1；6=4+2；7=4+2+1；12=8+4) D-8,9,10,11,12。 20海明校验码 3)把线性码位的值的偶校验作为冗余码的值(设冗余码初值为0)： A=(0,1,1,0,1,0)=1 B=(0,1,0,0,1,0)=0 C=(0,1,0,0,0) =1 D=(0,1,1,0,0) =0 4)海明码为:1 0 1 1 1 0 0 0 1 1 0 0 21海明校验码 例2.已知：接收的码字为：1 0 0 1 1 0 0 0 1 1 0 0(r=4代表冗余位数，即校验码位数) 求：发送端的信息码。 22海明校验码 解：1)设错误累加器(err)初值=0 2)求出冗余码的偶校验和，并按码位累加到err中： A=(1,0,1,0,1,0)=1 err=err+20=1 B=(0,0,0,0,1,0)=1 err=err+21=3 C=(1,1,0,0,0) =0 err=err