校验码

何为校验码

1. 校验码是指能够发现或自动纠正错误的数据编码，也被称为检错纠错码。原理是通过增加一些冗余码，来检验或纠错编码。
2. 通常某种编码有许多码字组成，任意两个合法码字之间最少变化的二进制位数被称为数据校验码的码距，例如1100和1101之间的码距为1，因为只有最低位翻转了改变。1001和0010之间的码距为3，因为只有1位没有变化。
3. 对于码距不小于2的数据校验码，开始具有检错的能力。码距越大，检错纠错的能力就越强，而且检错能力总是大于等于纠错能力。
4. 常用的校验码有奇偶校验码、海明校验码和循环冗余校验码。

码距与检错、纠错有何关系？

1. 在一个码组内为了检测e个误码，要求最小码距d应该满足：d>=e+1
2. 在一个码组内为了纠正t个误码，要求最小码距d应该满足：d>=2t+1

循环冗余校验码CRC

只能用来检错，不能用于纠错的校验码。

原理：在编码时，尾部添加一些校验信息，在编码后与生成校验码的生成式相除，余数为0则表示编码无错误,否则表示传输过程中有问题。

什么是模2除法？ 模2除法是指在做除法运算的过程中不计其进位的除法。

例题：原始报文为"11001010101"，其生产多项式为$X^4+X^3+X+1$。对其进行CRC编码后的结果为？

1. 多项式转二进制编码：$X^4+X^3+X+1$ = 11011
2. 在原始报文后加生成多项式长度减1个0：报文为110010101010000
3. 结果为0011

Alt text

另外一例

海明校验码

海明码明确规定校验位的位置是位于整个信息编码中的$2^n$位置，例如$2^0 = 1、2^1 = 2、2^2 = 4位$

例题：求信息1011的海明码。

1. 明确校验位与信息位公式关系$2^r>=4+r+1，4代表的是信息长度，r代表的是校验码的长度，所以r = 3，即校验码为3位。
2. 列出校验位公式
   1. 7 = $2^2 + 2^1 + 2^0$、6=$2^2 + 2^1$、5 = $2^2 + 2^0$、3 = $2^1 + 2^0$，依据其二进制位数，推算下列校验码
   2. $r_2 = I _4 \oplus I_3 \oplus I_2$、$r_1 = I _4 \oplus I_3 \oplus I_1$、$r_0 = I _4 \oplus I_2 \oplus I_1$
   3. 根据公式得出$r_2 = 1 \oplus 0 \oplus 1 = 0，r_1 = 1 \oplus 0 \oplus 1 = 0，r_0 = 1 \oplus 1 \oplus 1 = 1$
   4. 因此信息1011的海明码为1010101

海明校验码