海明码校验

奇偶校验码 1.奇偶校验概念 奇偶校验码是一种最简单的数据校 验码，它的码距等于2，可以检测出一位 错误（或奇数位错误），但不能确定出错 的位置，也不能检测出偶数位错误。 奇偶校验实现方法是：由若干位有效 信息（如一个字节），再加上一个二进制 位（校验位）组成校验码。 图2-1奇偶校验 码 1位 n位 有效信息位 奇偶校验位 奇偶校验码 奇偶校验规律 校验位的取值（0或1）将使整个校 验码中“1”的个数为奇数或偶数，所以有 两种可供选择的校验规律： 奇校验──整个校验码（有效信息位 和校验位）中“1”的个数为奇数。 偶校验──整个校验码中“1”的个数 为偶数。 2.简单奇偶校验 简单奇偶校验仅实现横向的奇偶校验， 下表给出几个字节的奇偶校验码的编码结 果。最高一位为校验位，其余8位为信息 位。在实际应用中，多采用奇校验，因为 奇校验中不存在全“0”代码，在某些场合 下更便于判别。 有效信息（8位） 奇校验码（9位） 偶校验码（9位） 00000000 100000000 000000000 01010100 001010100 101010100 01111111 001111111 101111111 11111111 111111111 011111111 2.简单奇偶校验（续） ⑴ 校验位形成 当要把一个字节的代码D7～D0写入 主存时，就同时将它们送往奇偶校验逻辑 电路，该电路产生的“奇形成”信号就是校 验位。它将与8位代码一起作为奇校验码 写入主存。 若D7～D0中有偶数个“1”，则“奇形 成”=1， 若D7～D0中有奇数个“1”，则“奇形 成”=0。 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 ) 按如下方法构建： • 　　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,5,7,9,11,13,15,…) • 　　位置2：校验2位，跳过2位，校验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,…) • 　　… 海明校验码 • 冗余码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 0 0 • 　　根据上面表格得到 A B C D 海明校验码 采用偶校验，如果全部校验的位置中 有奇数个1，把该奇偶校验位置为1；如果 全部校验的位置中有偶数个1，把该奇偶 校验位置为0. 海明校验码 • 举例说明： • 　　一个字节的数据：10011010 • 　　构造数据字(Data Word),对应的校验 位留空_ _ 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 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的数据出错。一般说来，对所有 校验位进行检查, 将所有出错的校验位置 相加, 得到的就是错误信息所在的位置. 海明校纠错