第5章 补海明码校验课件

1、奇偶校验码1.奇偶校验概念奇偶校验概念 奇偶校验码是一种最简单的数据校奇偶校验码是一种最简单的数据校验码，它的码距等于验码，它的码距等于2，可以检测出一位，可以检测出一位错误（或奇数位错误），但不能确定出错错误（或奇数位错误），但不能确定出错的位置，也不能检测出偶数位错误。的位置，也不能检测出偶数位错误。 奇偶校验实现方法是：由若干位有效奇偶校验实现方法是：由若干位有效信息（如一个字节），再加上一个二进制信息（如一个字节），再加上一个二进制位（校验位）组成校验码。位（校验位）组成校验码。 图图:奇偶校验码奇偶校验码1位n位有效信息位奇偶校验位奇偶校验码奇偶校验规律 校验位的取值（校验位的取值（

2、0或或1）将使整个校）将使整个校验码中验码中“1”的个数为奇数或偶数，所以有的个数为奇数或偶数，所以有两种可供选择的校验规律：两种可供选择的校验规律： 奇校验奇校验整个校验码（有效信息位整个校验码（有效信息位和校验位）中和校验位）中“1”的个数为奇数。的个数为奇数。 偶校验偶校验整个校验码中整个校验码中“1”的个数的个数为偶数。为偶数。 2.简单奇偶校验 简单奇偶校验仅实现横向的奇偶校验，简单奇偶校验仅实现横向的奇偶校验，下表给出几个字节的奇偶校验码的编码结下表给出几个字节的奇偶校验码的编码结果。最高一位为校验位，其余果。最高一位为校验位，其余8位为信息位为信息位。在实际应用中，多采用奇校验，

3、因为位。在实际应用中，多采用奇校验，因为奇校验中不存在全奇校验中不存在全“0”代码，在某些场合代码，在某些场合下更便于判别。下更便于判别。 有效信息（有效信息（8 8位）位）奇校验码（奇校验码（9 9位）位）偶校验码（偶校验码（9 9位）位）00000000000000001 100000000000000000 0000000000000000001010100010101000 001010100010101001 1010101000101010001111111011111110 001111111011111111 1011111110111111111111111111111111

4、 111111111111111110 011111111111111112.简单奇偶校验（续） 校验位形成校验位形成 当要把一个字节的代码当要把一个字节的代码D7D0写入写入主存时，就同时将它们送往奇偶校验逻辑主存时，就同时将它们送往奇偶校验逻辑电路，该电路产生的电路，该电路产生的“奇形成奇形成”信号就是信号就是校验位。它将与校验位。它将与8位代码一起作为奇校验位代码一起作为奇校验码写入主存。码写入主存。 若若D7D0中有中有偶数偶数个个“1”，则，则“奇奇形成形成”=1， 若若D7D0中有中有奇数奇数个个“1”，则，则“奇奇形成形成”=0。奇偶校验位的形成及校验电路D7D6D5D4D3D2

5、D1D0D校奇形成偶校验出错奇校验出错偶形成AB=1=1=1=1=1=1=1=111图图: 奇偶校验位的形成及校验电路奇偶校验位的形成及校验电路2.简单奇偶校验（续） 校验检测校验检测 读出时，将读出的读出时，将读出的9位代码（位代码（8位信位信息位和息位和1位校验位）同时送入奇偶校验电位校验位）同时送入奇偶校验电路检测。若读出代码无错，则路检测。若读出代码无错，则“奇校验出奇校验出错错”=0；若读出代码中的某一位上出现；若读出代码中的某一位上出现错误，则错误，则“奇校验出错奇校验出错”=1，从而指示，从而指示这个这个9位代码中一定有某一位出现了错误，位代码中一定有某一位出现了错误，但具体的错

6、误位置是不能确定的。但具体的错误位置是不能确定的。3.交叉奇偶校验 计算机在进行大量字节（数据块）传计算机在进行大量字节（数据块）传送时，不仅每一个字节有一个奇偶校验送时，不仅每一个字节有一个奇偶校验位做横向校验，而且全部字节的同一位位做横向校验，而且全部字节的同一位也设置一个奇偶校验位做纵向校验，这也设置一个奇偶校验位做纵向校验，这种横向、纵向同时校验的方法称为交叉种横向、纵向同时校验的方法称为交叉校验。校验。 第第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

7、 1 0 1 0 1 0 1 0 0 1 1 0 0 03.交叉奇偶校验（续） 交叉校验可以发现两位同时出错的交叉校验可以发现两位同时出错的情况，假设第情况，假设第2字节的字节的A6、A4两位均出错，两位均出错，横向校验位无法检出错误，但是第横向校验位无法检出错误，但是第A6、A4位所在列的纵向校验位会显示出错，这位所在列的纵向校验位会显示出错，这与前述的简单奇偶校验相比要保险多了。与前述的简单奇偶校验相比要保险多了。 海明校验码 海明码是一种可以纠正一位差错的编海明码是一种可以纠正一位差错的编码。它是利用在信息位为码。它是利用在信息位为k位，增加位，增加r位冗位冗余位，构成一个余位，构成一个

8、n=k+r位的码字，然后用位的码字，然后用r个监督关系式产生的个监督关系式产生的r个校正因子来区分个校正因子来区分无错和在码字中的无错和在码字中的n个不同位置的一位错。个不同位置的一位错。它必需满足以下关系式：它必需满足以下关系式： 2r k+r+1 或或 2r n+1海明校验码 海明码海明码(Hamming Code )编码的关键是使编码的关键是使用多余的奇偶校验位来识别一位错误。用多余的奇偶校验位来识别一位错误。 码字码字(Code Word) 按如下方法构建：按如下方法构建： 1、把所有、把所有2的幂次方的数据位标记为的幂次方的数据位标记为奇偶校验位奇偶校验位(编号为编号为1, 2, 4

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

10、位，校验位，校验2位，跳位，跳过过2位位 (2,3,6,7,10,11,14,15,) 位置位置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,) 海明校验码 采用偶校验，如果全部校验的位置中有奇数个1，把该奇偶校验位置为1；如果全部校验的位置中有偶数个1，把该奇偶校验位置为0. 海明校验码 举例说明： 一个字节的数据：10011010 构造数据字(Data Word),对应的校验

11、位留空_ _ 1 _ 0 0 1 _ 1 0 1 0 计算每个校验位的奇偶性 ( ?代表要设置的比特位): 海明校验码 位置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 海明校验码 位置4检查4,5,6,7,12: 0 1 1 ? 0 0 1 _ 1 0 1 0. 奇数个1，因此位置4设为1，即: 0 1

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

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

14、 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 根据上面表格得到 A B C D 海明校验码 需要说明的是公式中参与计算的是表格中出现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。 海明校验码 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 海明校验码 例例2.已知：接收的码字为： 1 0 0 1 1 0 0 0 1 1 0 0(k=4代表冗余位数，即校验码位数) 求：发送端的信息码。 海明校验码 解：1)设错误累加器(err)初值=0 2)求出冗余码的偶校验和，并按码位累加到err中： A=(1,0,1,0,1,0)=1