海明码(也叫汉明码)具有一位纠错能力。本文以1010110这个二进制数为例解释海明码的编码和校验方法
确定校验码的位数x
设数据有n位,校验码有x位。则校验码一共有2x种取值方式。其中需要一种取值方式表示数据正确,剩下2x-1种取值方式表示有一位数据出错。因为编码后的二进制串有n+x位,因此x应该满足
2x-1 ≥ n+x
使不等式成立的x的最小值就是校验码的位数。在本例中,n=7,解得x=4。
确定校验码的位置
校验码在二进制串中的位置为2的整数幂。剩下的位置为数据。如图所示。
位置 | |||||||||||
内容 | x1 | x2 | x3 | x4 |
确认校验位数据位关系
将每个位置,都拆成校验位位置值相加,可知道一个校验位跟哪些数据位有关系
求出校验位的值
以求x2的值为例。为了直观,将表格中的位置用二进制表示。
位置 | |||||||||||
内容 | x1 | x2 | 1 | x3 | 1 | 0 | x4 | 1 | 0 |
为了求出x2,要使所有位置的第二位是1的数据(即形如**1*的位置的数据)的异或值为0。即x2^1^1^0^1^0 = 0。因此x2 = 1。
同理可得x1 = 0, x3 = 1, x4 = 0。
位置 | |||||||||||
内容 |
因此1010110的海明码为01110100110。
校验
假设位置为1011的数据由0变成了1,校验过程为:
将所有位置形如***1, **1*, *1**, 1***的数据分别异或。
***1: 0^1^0^0^1^1 = 1
**1*: 1^1^1^0^1^1 = 1
*1**: 1^0^1^0 = 0
1***: 0^1^1^1 = 1
以上四组中,如果一组异或值为1,说明该组中有数据出错了。***1 **1* 1***的异或都为1,说明出错数据的位置为1011。
CRC冗余校验
CRC的实现原理十分易于硬件实现,因此被广泛的应用于计算机网络上的差错控制。CRC校验码需根据CRC生成多项式进行。
关于软考中涉及到的海明码和CRC校验码,主要是两种的验证方式。海明码的校验过程比较复杂,在计算机中不经常用,而CRC校验码比较容易,先确定校验码的位数,以及除数是什么?所以个人感觉想要掌握这两种情况,就需要分析的方式。
实例:原始报文为11001010101,其多项式为X4+X3+X+1。在原始报文的后面若干个0(等于校验码的位数,而生成多项式的最高幂次就是校验位数,即使用该生成多项式产生的校验码为4位)作为被除数,除以生成多项式所对应的二进制数。
X4+X3+X+1对应的二进制为11011,则除数作为11011
运算时可借位,但被借的位数值不变,如01减10=11
然后把添加到原始报文的后面就是结果110010101010011。