海明校验码.ppt

1、海明校验码,海明校验码是以奇偶校验为基础，校验位是多位。 一、什么是码距? 码距就是两个码字C1与C2之间不同的比特数。如：1100与1010的码距为2；1111与0000的码距为4。 一个编码系统的码距就是整个编码系统中任意(所有)两个码字的最小距离。若一个编码系统有四种编码分别为：0000，0011，1100，1111，此编码系统中0000与1111的码距为4；0000与0011的码距为2，是此编码系统的最小码距。因此该编码系统的码距为2。,二、海明码的组成 海明码是由Richard Hamming于1950年提出的，它具有一位纠错能力。由编码纠错理论得知：任何一种编码是否具有检错能力和纠

2、错能力，都与编码的最小距离有关。根据纠错理论得： L-1=D+C 且 DC 即编码最小距离L 越大，则其检测错误的位数D 也越大，纠正错误的位数C 也越大，且纠错能力恒小于或等于检错能力。如当编码最小距离L=3时，这种编码可视为最多能检错两位，或能检错一位、纠错一位。可见，倘若能在信息编码中增加几位检测位，增大L，便能提高检错和纠错能力。海明码就是根据这一理论提出的。,设欲检测的二进制代码为n位，为使其具有纠错能力，需添加k位检测位，组成n+k位的代码。为了能准确对错误定位以及指出代码没错，新增添的检测位数k应满足： 2kn+k+1 （海明不等式） 由此可求得不同代码长度n所需检测位的位数k，

3、如表1： 表1 代码长度与检测位位数的关系,K的位数确定后，便可由它们所承担的检测任务，设定它们在被传送代码中的位置及它们的取值 。 设n+k位代码自左至右依次编为第1，2，3，.，n+k位，而将k位检测位记为Ci（i=1，2，4，8），分别安插在n+k位代码编号的第1，2，4，8，2k-1位上。这些检测位的位置设置，是为了保证它们能分别承担n+k位信息中，不同数位所组成的“小组”的奇偶检查任务，使检测位和它所负责检测的小组中1的个数为奇数或为偶数，具体分配如下：,C1 检测g1小组包含第1,3,5,7,9,11位 C2 检测g2小组包含第2,3,6,7,10,11,14,15位 C4 检测g

4、3小组包含第4,5,6,7,12,13,14,15位 C8 检测g4小组包含第 8,9,10,11,12,13,14,15,24位 . . . 其余检测位的小组所包含的位也可类推。,这种小组的划分有如下特点： 每个小组gi有一位且仅有一位为它所独占，这一位是其它小组所没有的，即gi小组独占第2i-1位（i=1,2,3,） 每两个小组gi和gj共同占有一位是其它小组所没有的，即每两个gi和gj共同占有第2i-1+ 2j-1位（i,j=1,2,） 每三个小组gi、gj和gl共同占有第2i-1+ 2j-1 + 2l-1位，是其它小组所没有的； 依次类推，便可确定每组所包含的各位。,例如：欲传递信息为

5、b4b3b2b1(n=4)，根据2kn+k+1，可求出配置成海明码需增添检测位k=3，且它们位置的安排如下： 二进制序号 1 2 3 4 5 6 7 名称 C1 C2 b4 C4 b3 b2 b1 如果按照配偶原则来配置海明码，则 C1 应使1,3,5,7位中的“1”的个数为偶数； C2 应使2,3,6,7位中的“1”的个数为偶数； C4 应使4,5,6,7位中的“1”的个数为偶数； 故 C1应为3位5位7位，即C1b4b3b1； C2应为3位6位7位，即C2b4b2b1； C4应为5位6位7位，即C4b3b2b1；,令b4b3b2b10101，则 C1b4b3b10110； C2b4b2b1

6、0011； C4b3b2b11010； 故0101的海明码应为：C1 C2 b4 C4 b3 b2 b1，即0100101。,三、海明码的纠错过程 海明码的纠错过程，实际上是对传送后的海明码形成新的检测位Pi（i=1,2,4,8），根据Pi的状态，便可直接指出错误的位置。Pi的状态是由原检测位Ci及其所在小组内“1”的个数确定的。倘若按配偶原则配置的海明码，其传送后形成新的检测位Pi应为0，否则说明传送有错，并且还可以直接指出出错的位置。由于Pi和Ci有其对应关系，故Pi可由下式确定： P1=1357，即P1=C1b4b3b1 P2=2367，即P2=C2b4b2b1 P4=4567，即P4=

7、C4b3b2b1,设已知传送的正确海明码（按配偶原则配置）为0100101，若传送后接收到的海明码为0100111，其出错位可按下述步骤进行： 令： 二进制序号 1 2 3 4 5 6 7 正确的海明码 0 1 0 0 1 0 1 接收到的海明码 0 1 0 0 1 1 1 则新的检测位为： P4=4567，即P4=0111=1 P2=2367，即P2=1011=1 P1=1357，即P1=0011=0,由此可见，传送结果P4、P2均不呈偶数，显然出了差错。那么，错位在哪一位呢？极为有意思的是，P4、P2、P1所构成的二进制值恰恰是出错的位置，即P4P2P1=110，表示第六位出错。发现错误后，计算机便自动地将错误的第六位“1”纠正为“0”。,又如，若收到按偶配置的海明码为1100101，则经检测得： P4=4567，即P4=0101=0 P2=2367，即P2=1001=0 P1=1357，即P1=1011=1 所以，出错位为：P4P2P1=001，即第一位。可是第一位不是欲传送的信息位，而是检测位，在一般情况下，可以不予纠正。,以上均以n=4为例，其实对任意不同n位的信息，均可按上述步骤配置海明码，即先求出需增加的检测位位数k，再确定