补海明码校验

1、奇偶校验码1.奇偶校验概念 奇偶校验码是一种最简单的数据校验码，它的码距等于2，可以检测出一位错误(cuw)（或奇数位错误(cuw)），但不能确定出错的位置，也不能检测出偶数位错误(cuw)。 奇偶校验实现方法是：由若干位有效信息（如一个字节），再加上一个二进制位（校验位）组成校验码。 图:奇偶校验码共二十五页奇偶校验规律(gul) 校验位的取值（0或1）将使整个(zhngg)校验码中“1”的个数为奇数或偶数，所以有两种可供选择的校验规律： 奇校验整个校验码（有效信息位和校验位）中“1”的个数为奇数。 偶校验整个校验码中“1”的个数为偶数。 共二十五页2.简单(jindn)奇偶校验 简单奇偶校

2、验(xio yn)仅实现横向的奇偶校验(xio yn)，下表给出几个字节的奇偶校验(xio yn)码的编码结果。最高一位为校验(xio yn)位，其余8位为信息位。在实际应用中，多采用奇校验(xio yn)，因为奇校验(xio yn)中不存在全“0”代码，在某些场合下更便于判别。 有效信息（8位）奇校验码（9位）偶校验码（9位）00000000100000000000000000010101000010101001010101000111111100111111110111111111111111111111111011111111共二十五页2.简单(jindn)奇偶校验（续） 校验位形成(x

3、ngchng) 当要把一个字节的代码D7D0写入主存时，就同时将它们送往奇偶校验逻辑电路，该电路产生的“奇形成”信号就是校验位。它将与8位代码一起作为奇校验码写入主存。 若D7D0中有偶数个“1”，则“奇形成”=1， 若D7D0中有奇数个“1”，则“奇形成”=0。共二十五页奇偶校验(xio yn)位的形成及校验(xio yn)电路图: 奇偶校验位的形成(xngchng)及校验电路共二十五页2.简单(jindn)奇偶校验（续） 校验检测 读出时，将读出的9位代码（8位信息位和1位校验位）同时送入奇偶校验电路检测。若读出代码无错，则“奇校验出错”=0；若读出代码中的某一位上出现错误，则“奇校验出错

4、”=1，从而指示这个9位代码中一定(ydng)有某一位出现了错误，但具体的错误位置是不能确定的。共二十五页3.交叉(jioch)奇偶校验 计算机在进行大量字节（数据块）传送时，不仅每一个(y )字节有一个(y )奇偶校验位做横向校验，而且全部字节的同一位也设置一个(y )奇偶校验位做纵向校验，这种横向、纵向同时校验的方法称为交叉校验。 第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 0 0 0共二十五页3.交叉(jioch)奇偶校验（续）

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

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

7、置4：校验4位，跳过4位，校验4位，跳过4位 (4,5,6,7,12,13,14,15,20,21,22,23,) 位置8：校验8位，跳过8位，校验8位，跳过8位(8-15,24-31,40-47,) 共二十五页海明校验码 采用偶校验，如果全部校验的位置(wi zhi)中有奇数个1，把该奇偶校验位置(wi zhi)为1；如果全部校验的位置(wi zhi)中有偶数个1，把该奇偶校验位置(wi zhi)为0. 共二十五页海明校验码 举例说明： 一个字节的数据(shj)：10011010 构造数据字(Data Word),对应的校验位留空_ _ 1 _ 0 0 1 _ 1 0 1 0 计算每个校验位

8、的奇偶性 ( ?代表要设置的比特位): 共二十五页海明校验码 位置(wi zhi)1检查1,3,5,7,9,11: ? _ 1 _ 0 0 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 共二十五页海明校验码 位置(wi zhi)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

9、 _ 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 0 1 0 1 0 1 0因此码字为: 011100101010. 共二十五页海明校验码 上例中构建了一个码字 011100101010，假定实际接收到的数据 011100101110. 则接收方可以计算出哪一位出错并对其进行更正。方法就是验证每一个校验位。记下所有(suyu)出错的校验位，可以发现校验位2和8的数据不正确. 错误校验位 2 + 8 = 10, 则位置10的数据出错。一般说来，对所有(suyu)校验位进行检查, 将所有

10、(suyu)出错的校验位置相加, 得到的就是错误信息所在的位置. 共二十五页海明校验码 例1.已知：信息码为： 1 1 0 0 1 1 0 0 (k=4代表冗余(rn y)位数，即校验码位数) 求：海明码码字。 共二十五页海明校验码 解：1)把冗余(rn y)码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。 共二十五页海明校验码 2)冗余码A,B,C,D的线性码位是：(相当于监督关系式) 监督关

11、系式的推导： 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 0 0 根据上面表格(biog)得到 A B C D 共二十五页海明校验码 需要说明的是公式中参与计算的是表格中出现1的那个位 右边(yu bian)是数据位的二进制数,公式中的+表示异或 故此有如下表达式： A-1,3,5,7,9,11；(这里的1 3 5 7 9 11均为A那一列出现1的位) B-2,3,6,7,10,11；

12、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。 共二十五页海明校验码 3)把线性码位的值的偶校验(xio yn)作为冗余码的值(设冗余码初值为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 共二十五页海明校验码 例2.已知：接收的码字为：1 0 0 1 1 0 0 0 1 1 0 0(k=4代表(dibio)冗余位数，即校验码位数) 求：发送端的信息码。 共二十五

13、页海明校验码 解：1)设错误(cuw)累加器(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+0 =3 D=(0,1,1,0,0) =0 err=err+0 =3 共二十五页海明校验码 由err0可知接收码字有错， 3)码字的错误位置就是错误累加器(err)的值3。 4)纠错-对码字的第3位值取反得正确(zhngqu)码字： 1 0 1 1 1 0 0 0 1 1 0 0 5)把位于2的k次方位的冗余码删除得信息码：1 1 0 0 1 1 0 0 共二十五页内容摘要奇偶校验码。奇校验整个校验码（有效信息