3.7 数据校验码任何一种编码都由许多码字构成,任意两个码字之间会有n位代码不同,n称为它们之间的距离,这些n值中.最小的就是该编码的码距.例如，用四位二进制表示16种状态，则16种编码都用到了，此时码距为1。

若用四个二进制位表示8个状态，就可以只用其中的8种编码，而把另8种编码作为非法编码，此时码距为2。

计算机学院z000 0z001 1z010 1z011 0z100 1z101 0z110 0z111 1计算机学院3．7．1 奇偶校验奇偶校验码的原理是在每组代码中增加一个冗余位，使合法编码的最小码距由1增加到2。

(1) 校验码的构成规则偶校验：每个码字(包括校验位)中1的数目为偶数。

比如1101011 的偶校验码为1101011 1奇校验：每个码字(包括校验位)中1的数目为奇数。

比如1101011 的奇校验码为1101011 0计算机学院(2) 校验位的形成设有效信息为D7D6D5D4D3D2D1D0，则：偶校验：在发送端求校验位P= D7⊕D6⊕D5⊕D4⊕D3⊕D2⊕D1⊕D0奇校验：在发送端求校验位P= D7⊕D6⊕D5⊕D4⊕D3⊕D2⊕D1⊕D0校验电路如图所示。

计算机学院(3)校验原理偶校验在接受端求P’= D7⊕D6⊕D5⊕D4⊕D3⊕D2⊕D1⊕D0⊕P奇校验在接受端求P’= D7⊕D6⊕D5⊕D4⊕D3⊕D2⊕D1⊕D0⊕P若P’=0，则无错；若P’=1，则有错。

校验电路如图所示计算机学院发送端接收端PP’计算机学院(4)局限性奇偶校验码能发现数据代码中奇数个位出错情况，并且不能纠正错误，常用于对存储器数据的检查或者传输数据的检查。

3.7.2 海明码校验海明校验的基本思想是将有效信息按某种规律分成若干组，每组安排一个校验位进行奇偶测试。

计算机学院例求信息码01101110的海明校验码，画出能指出和纠正一位出错位的海明校验逻辑电路。

①确定海明校验位的位数设R为校验位的位数，则整个码字的位数应满足不等式：N=K＋R≤2R－1设R=3，则23－1=7，N=8＋3=11，不等式不满足；设R=4，则24－1=15，N=8＋4=12，不等式满足。

所以R最小取4。

②确定校验位的位置：位号(1～12)为2的权值的那些位，即：20、21、22、23的位置作为校验位，记作P1、P2、P3、P4，余下的为有效信息位。

即：12 11 10 9 8 7 6 5 4 3 2 1D 7D6D5D4P4 D3D2D1P3DP2 P1计算机学院③分组：有4个校验位，将12位分4组，第i位由校验位的位号之和等于i的那些校验位所校验。

如表所示，如：第11位D由P1(位6号为1)、P2(位号为2)、P4(位号为8)所校验，因为1＋2＋8=11。

校验H12 H11 H10 H9H8 H7 H6H5H4H3H2H1位的D7D6D5D4P4 D3D2 D1 P3D0 P2 P1位号0 1 1 0 1 1 1 0第一组(P1) 1√√√√√√第二组(P2) 2√√√√√√第三组(P3) 4√√√√√第四组(P4) 8√√√√√计算机学院④校验位的形成P1=第一组中的所有位(除P1外)求异或=D 6⊕D4⊕D3⊕D1⊕D=1⊕0⊕1⊕1⊕0=1P2=第二组中的所有位(除P2外)求异或=D 6⊕D5⊕D3⊕D2⊕D= 1⊕1⊕1⊕1⊕0=0P3=第三组中的所有位(除P3外)求异或=D 7⊕D3⊕D2⊕D1= 0⊕1⊕1⊕1=1P4=第四组中的所有位(除P4外)求异或=D 7⊕D6⊕D5⊕D4= 0⊕1⊕1⊕0=0计算机学院为了能检测两个错误，增加一位校验P5，放在最高位。

P5 = D7⊕D6⊕D5⊕D4⊕D3⊕D2⊕D 1⊕D⊕P1⊕P2⊕P3⊕P4= 0⊕1⊕1⊕0⊕1⊕1⊕1⊕0⊕1⊕0⊕1⊕0 = 1【例题答案】信息码0110 1110的海明校验码为：1 0110 0111100 1计算机学院计算机学院(2)校验原理在接收端分别求S 1、S 2、S 3、S 4、S 5。

S 1 = P1⊕D 6⊕D 4⊕D 3⊕D 1⊕D 0S 2 = P2⊕D 6⊕D 5⊕D 3⊕D 2⊕D 0S 3 = P3⊕D 7⊕D 3⊕D 2⊕D 1S 4 = P4⊕D 7⊕D 6⊕D 5⊕D 4S 5 = P5⊕D 7⊕D 6⊕D 5⊕D 4⊕D 3⊕D 2⊕D 1⊕D 0⊕P1⊕P2⊕P3⊕P4计算机学院z 当S 5=1时有一位错：由S 4S 3S 2S 1的二进制编码指出出错位号。

例如S 4S 3S 2S 1=1001 说明第9位出错，将其取反，即可纠错。

z当S 5=0时无错或有偶数个错(两个错的可能性比较大)z当S 4S 3S 2S 1=0000时，接收的数无错，否则有两个错。

z 【例题答案】能指出两个错误并能纠正一位出错位的海明校验逻辑电路如图所示。

计算机学院D 7 D 6 D 5 D 4 D 3 D 2 D 1 D 0 无错 一位错 两位错=1 =1 =1 =1 =1 =1 =1 =1H 12 H 11 H 10 H 9 H 7 H 6 H 5 H 31100 1011 1010 1001 0111 0110 0101 0011 00004：16 译 码 器 (设译码器高电平有效)S 4 S 3 S 2 S 1 S 5 奇偶形成线路 奇偶形成线路 奇偶形成线路 奇偶形成线路 奇偶形成线路 H 12H 11H 10H 9H 8 H 12 H 7 H 6 H 5 H 4 H 11H 10 H 7 H 6H 3H 2 H 11 H 9H 7H 5 H 3 H 1 所有位 校验 H 12 H 11 H 10 H 9 H 8 H 7 H 6 H 5 H 4 H 3 H 2 H 1 位的 D 7 D 6 D 5 D 4 P4 D 3 D 2 D 1 P3 D 0 P2 P1 位号 0 1 1 0 1 1 1 0 第一组(P1) 1 √ √ √ √√ √ 第二组(P2) 2 √ √ √ √ √ √ 第三组(P3) 4 √ √ √ √ √第四组(P4) 8 √ √ √ √ √序号也可以从低到高，如下所示：校验H1H2 H3 H4H5H6H7 H8H9H10H11H12位的P1 P2 D7P3 D6D5D4P4D3D2D1D0位号0 1 1 0 1 1 10 第一组(P1) 1√√√√√√第二组(P2) 2√√√√√√第三组(P3) 4√√√√√第四组(P4) 8√√√√√计算机学院D7D6 D5D4D3D2 D1D0无错一位错两位错=1=1=1=1=1=1=1=1H3H5H6H7H9H10 H11 H12 00110101011001111001101010111100 00004：16译码器 (设译码器高电平有效)S4S3 S2S1 S5奇偶形成线路奇偶形成线路奇偶形成线路奇偶形成线路奇偶形成线路H3H2H1H0H6 H5 H4 H0H3H6H7H10H11H3 H5H7H9H11 所有位计算机学院例题有一个（7，4）码，写出代码0011的海明效验码，画出效验电路解：（1）求信息码001的海明效验码。

①确定海明效验位的位数因为是（7，4）码，所以N=7，K=4，效验位的位数为3。

②确定效验位的位置：位号（1∽7）为2的权值的那些位，即：20、21、22的位置作为效验位，即：7 6 5 4 3 2 1D3D2D1P3 DP2 P1计算机学院计算机学院④效验位的形成P1= D 3⊕D 1⊕D 0= 0⊕1⊕1=0P2= D 3⊕D 2⊕D 0= 0⊕0⊕1=1P3= D 3⊕D 2⊕D 1= 0⊕0⊕1=1所以：信息码0011的海明效验码为：001 1 1 10③ 分组H 7 H 6 H 5 H 4 H 3 H 2 H 1 D 3 D 2 D 1 P3 D 0 P2 P1 0 0 1 1第一组（P1） √ √ √ √ 第二组（P2） √ √ √ √ 第三组（P3） √ √ √ √计算机学院(2)海明效验逻辑电路如图所示D 3 D 2 D 1 D 0 =1无错 =0有错 =1 =1 =1 =1H 7 H 6 H 5 H 30111 0110 0101 0011 00003：8 译 码 器 （设译码器高电平有效）S 3 S 2 S 1 奇偶形成线路 奇偶形成线路 奇偶形成线路H 7 H 6 H 5 H 4 H 7 H 6 H 3 H 2 H 7 H 5 H 3 H 1P 103 习题3.29、 3.30 3.31计算机学院①确定海明校验位的位数设K为有效信息的位数，设r为校验位的位数，则整个码字的位数N应满足不等式：N=K＋r≤2r －1若要求海明码能检测出2位错误，则再增加一位校验位。

z ②确定校验位的位置：位号(1～N)为2的权值的那些位，即：20、21、22、…2r－1的位置作为校验位，记作P 1、P 2、…P r ，余下的为有效信息位。

z ③分组:将N位分r组，第i位由校验位号之和等于i的那些校验位所校验。

求海明校验码的步骤z如下所示（k=8）：校验H12 H11 H10 H9H8 H7 H6H5H4H3H2H1位的D7D6D5D4P4 D3D2 D1 P3D0 P2 P1位号0 1 1 0 1 1 1 0第一组(P1) 1√√√√√√第二组(P2) 2√√√√√√第三组(P3) 4√√√√√第四组(P4) 8√√√√√计算机学院z④校验位的形成P1=第一组中的所有位(除P1外)求异或P2=第二组中的所有位(除P2外)求异或Pr=第r组中的所有位(除Pr外)求异或z为了能检测两个错误，增加一位校验P r＋1，放在最高位。

Pr＋1= 所有位(包括P1、P2、…Pr)共N位求异或计算机学院计算机学院(2)校验原理：在接收端分别求S 1、S 2、S 3、…S r S 1 =第一组中的所有位(包括P 1)求异或S 2 =第二组中的所有位(包括P 2)求异或S r =第r组中的所有位(包括P r )求异或S r＋1 = P r＋1⊕所有位(包括P 1、P 2、…P r )求异或z 当S r ＋1=1时有一位错：由S r …S 3S 2S 1的二进制编码指出出错位号,将其取反，即可纠错。

z 当S r ＋1=0时无错或有偶数个错(两个错的可能性比较大): 当S r …S 3S 2S 1=0…000时，接收的数无错，否则有两个错。

z根据此原理，能画出指出两个错误并能纠正一位出错位的海明校验逻辑电路。

数据校验的几个相关的概念z①海明重量：某码字中非零码元的个数，简称为重量。

对二进制码，即码字中1的个数。

z②海明距离：两个码字之间对应位不相同的个数。

z③最小距离：码字集合中，任意两个码字之间的距离的最小值称为最小距离。