海明码校验高等数学.ppt

奇偶校验码 1.奇偶校验概念 奇偶校验码是一种最简单的数据校验码，它的码距等于2，可以检测出一位错误（或奇数位错误），但不能确定出错的位置，也不能检测出偶数位错误。 奇偶校验实现方法是：由若干位有效信息（如一个字节），再加上一个二进制位（校验位）组成校验码。 图2-1奇偶校验码 奇偶校验规律 校验位的取值（0或1）将使整个校验码中“1”的个数为奇数或偶数，所以有两种可供选择的校验规律： 奇校验──整个校验码（有效信息位和校验位）中“1”的个数为奇数。 偶校验──整个校验码中“1”的个数为偶数。 2.简单奇偶校验 简单奇偶校验仅实现横向的奇偶校验，下表给出几个字节的奇偶校验码的编码结果。最高一位为校验位，其余8位为信息位。在实际应用中，多采用奇校验，因为奇校验中不存在全“0”代码，在某些场合下更便于判别。 有效信息（8位） 奇校验码（9位） 偶校验码（9位） 100000000 000000000 001010100 101010100001111111 101111111111111111 011111111 2.简单奇偶校验（续） ⑴ 校验位形成 当要把一个字节的代码D7～D0写入主存时，就同时将它们送往奇偶校验逻辑电路，该电路产生的“奇形成”信号就是校验位。它将与8位代码一起作为奇校验码写入主存。 若D7～D0中有偶数个“1”，则“奇形成”=1， 若D7～D0中有奇数个“1”，则“奇形成”=0。 奇偶校验位的形成及校验电路 图2-2 奇偶校验位的形成及校验电路 2.简单奇偶校验（续） ⑵校验检测 读出时，将读出的9位代码（8位信息位和1位校验位）同时送入奇偶校验电路检测。若读出代码无错，则“奇校验出错”=0；若读出代码中的某一位上出现错误，则“奇校验出错”=1，从而指示这个9位代码中一定有某一位出现了错误，但具体的错误位置是不能确定的。 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 1 0 1 0 1 → 0 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 1 0 0 1 1 0 0 0 3.交叉奇偶校验（续） 交叉校验可以发现两位同时出错的情况，假设第2字节的A6、A4两位均出错，横向校验位无法检出错误，但是第A6、A4位所在列的纵向校验位会显示出错，这与前述的简单奇偶校验相比要保险多了。 海明校验码 海明码是一种可以纠正一位差错的编码。它是利用在信息位为k位，增加r位冗余位，构成一个n=k+r位的码字，然后用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的一位错。它必需满足以下关系式： 2r ≥ k+r+1 或 2r ≥ n+1 海明校验码 海明码(Hamming Code )编码的关键是使用多余的奇偶校验位来识别一位错误。 码字(Code Word) 按如下方法构建： 　　1、把所有2的幂次方的数据位标记为奇偶校验位(编号为1, 2, 4, 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