校验码

基础知识

码距：任何一种编码都由许多码字构成，任意两个码字之间最少变化的二进制尾数就被称为数据校验码的码距（即取最小的），用于检测有效编码发生错误

码距的计算

10 与 01

是两个合法编码，他们之间的码距为2

用4位二进制表示16种状态，则有16种不同的码字，此时码距为1

如 0000 与 0001

检验错误

假如有一组有效的二进制数字0000，0011，1100，0110，1001，1010，0101,这一组的码距是2，在传输过程中如果0000被传为0001，只有一位发生错误，那么计算机就可以检测出来这个错误，而且不管是哪一个编码，只要误传的位数为1那么都可以检测出来。

但是假如有一组有效的三位二进制数数据000,001,010,011,101,110,111这一组的码距就是1，在传输过程中如果000被误传为001,由于001也是有效数据，所以就会将000当作001了，无法检测发生了错误。

校验方式

奇偶校验

奇偶校验的编码方式是：由若干位有效信息（如一个字节），再加上一个二进制位（校验位）组成校验码

奇校验：整个校验码（有信心和校验位种）1的个数为奇数

**偶校验：**整个校验码（有信心和校验位种）1的个数为偶数

只可以校验1位错误，不可纠错

循环冗余校验码CRC

原理

可检错，不可纠错

CRC的编码方式是：在k位信息码之后拼接r位校验码

CRC编码规律如下：

把接收到的CRC码用约定多项式G(x)去除，如果正确，余数为0，出错，不为0.

不同位出错其余数不同

模2除法

CRC主要利用了模2除法

加法不进位，减法不借位

例子： $$ \begin{align} &原始报文为 1100 1010 101,\ &其生成多项式为 x^4+x^3+x+1 \ &对其CRC编码后结果为? \end{align} $$ [答案]:11001010101 0011

[解析]:

按多项式系数得到除数与K+1=5，然后把模2除法得到的K位结果附加在最后

海明码校验

可检错，也可纠错

海明校验码的原理是：

在有效信息位中加入几个校验位形成海明码, 使码距比较均匀地拉大，并把海明码的每个二进制位分配到几个奇偶校 验组中。

当某一位出错后，就会引起有关的几个校验位的值发生变化， 这不但可以发现错误，还能指出错误的位置，为自动纠错提供了依据

✨确定校验位个数的公式 $$ \begin{align} & \begin{cases} r:校验位个数\ m:数据位个数 \end{cases} \ \ &2^r-1>=m+r \end{align} $$ 纠错原理

多个位通过异或互相印证

例题：