搜索
纠错编码-海明码在数据通信的过程中，解决差错问题的一种方法是在每个要发送的数据块上附加足够的冗余信息，使接收方能够通过这些冗余信息推导出实际发送出的应该是什么样的比特串。最常见的纠错码是海明码，它能发现两比特错，但只能纠正单比特错。汉明编码是将码字内的位从最左边开始依次编号，第1位是1号，第2位是2号……第n位是n号，编号为2的幂的位(1号位，2号位，4号位，8号位等)是校验位，其余的位填入位数据。每个校验位的取值应使得包括自己在内的一些位的集合服从规定的奇偶性(例如偶性要求这些位的集合中1的个数是偶数)。为了知道编号为k的数据位对哪些检测位有影响，将编号k改写成2的幂的和，例如11=1+2+8，29：1+4+8+16。1个位只由扩展式中所示编号的位检测，例如编号为11的位只由编号为1、2和8的检测位检测。m个信息位插入r个校验位组成n=m+r位码字，它们必须满足的关系是：2r≥n+1。以典型的4位数据编码为例，汉明码将加入3个校验码，从而实际传输7位码字：数据位：1234567代码：P1P2D8P3D4D2D1说明：Px为校验码，Dx为数据码。下面根据图举例说明编码的方法。图海明编码的例子当对8位数数据进行海明编码时，其校验关系如下表所示。表校验关系表海明码纠错过程(接收端)首先将差错计数器置“0”。当海明码数据到达接收端后，接收端逐个检查各个校验位的奇偶性。如发现某一校验位和它所检测的集合的奇偶性不正确，就将该检验位的编号加到差错计数器中。待所有校验位核对完毕，若差错计数器仍为0值，则说明该码字接收无误。反之，差错计数器的值即为出错位的编号，将该位求反就可得到正确结果。假设传送的信息为1001011，把各个数据放在3，5，6，7，9，10，11等位置上，l，2，4，8位留做校验位。根据上图，3、5、7、9、11的二进制编码的第一位为1，所以3、5、7、9、11号位参加第1位校验．若按偶校验计算．1号位应为1。也可用异或计算类似地，3、6、7、10、ll号位参加2位校验，5、6、7号位参加4位校验，9、10和11号位参加8位校验，全部按偶校验计算，最终得到：如果这个码字传输中出错，比如说6号位出错，即变成：当接收端按照同样规则计算奇偶位时，发现1和8号位的奇偶性正确，2和4号位的奇偶性不对，于是2+4=6，立即可确认错在6号位。在上例中，r=4，因而m24-4-1=11，即数据位可用到11位，共组成15位的码字，可检测出单个位的错误。