海明校验码
两个长度相等的字符串的海明距离是在相同位置上不同的字符的个数,也就是将一个字符串替换成另一个字符串需要的替换的次数。海明距离与检错和纠错的关系:
1.海明距离为d+1的编码能检测出d位差错。
因为在距离为d+1的检验码中,只改变d位的值,不可能产生另一个合法码。如奇偶校验码,海明距离为2,能查出单个错。
2.海明距离为2d+1的编码,能纠正d位差错。
因为此时,如果一个码字有d位发生差错,它仍然距离原来的码字距离最近,可以直接恢复为该码。
(奇偶校验码,海明距离为2,可以检出单个错)
纠正单比特错的冗余位下界,m为数据位数,r为校验位数
(m+R+1)≤2^r
1.每一个码字从左到右编号,最左边为第1位
2.校验位和数据位
3.每一个校验位设置根据:包括自己在内的一些位的集合的奇偶值(奇数或偶数)。
海明码纠错过程(只纠错1位)
循环冗余检错码CRC
可以检测到所有长度小于等于r的突发错误
广泛用于各种网络,几乎所有的局域网
使用CRC编码时发送方和接收方必须预先商定一个生成多项式G(x),假设有一个m为的帧M(x),使用G(x)生成的帧的步骤如下:
小结: