1.奇偶校验码
码距:任意两个码字之间最少变化的二进制位数。
00和01变化1位(码距1);00和11变化2位(码距2)
奇偶校验码的编码方法:由若干位有效信息,再加上一个二进制位(校验位)组成校验码。
1)奇校验:整个校验码(有效信息位和校验位)中1的个数为奇数
2)偶校验:整个校验码(有效信息位和校验位)中1的个数为偶数。
对于奇偶校验,只能检测出奇数个错误或者1位错误,例如11变为00,还是偶数个1,偶数的错误0和1会相互抵消,无法检错,并且不可以纠错。
2.CRC循环冗余校验
把接收到的CRC码用约定的生成多项式G(X)除(模二除法[异或]),如果正确则余数为0; 如果某1位出错,则余数不为0。不同的位数出错,其余数不同,余数和出错位序号之间有唯一对应关系。
要发送的数据为1101011011。采用CRC的生成多项式是 P(X)=X4+X+1(除数10011)
编码时在原始数据后加(多项式长度-1)个0,即4个0,运算后余数为1110
CRC校验不可纠错,可检错。
3.海明校验码
海明码是一种既能检错也能纠错的校验码,校验原理是多重奇偶校验。
在数据位之间插入k个校验位,通过扩大码距来实现检错和纠错。
公式:2k-1≥n+k(数据位是 n 位,校验位是 k 位,k取满足条件的最小值)
校验位位置:确定为2的幂次方位数,即1、2、4、8、16等
举例:1010,根据公式n=4,k=3,海明码个数:n+k=7,假设采用偶校验(1的个数为偶数)
P1P21P3010(校验位位于1、2、4的位置)
① | ② | ③ | ④ | ⑤ | ⑥ | ⑦ | |
校验码 | P1 | P2 | 1 | P3 | 0 | 1 | 0 |
001 | 010 | 011 | 100 | 101 | 110 | 111 |
P1(001):③011⑤101⑦111→100→1
P2(010):③011⑥110⑦111→110→0
P3(100):⑤101⑥110⑦111→010→1
海明校验码:1 0 1 1 0 1 0