一文搞定校验码（奇偶校验，海明，CRC 码）

效验码

• 校验码：指能够发现或能够自动纠正错误的数据编码，也称检错纠错编码。

• 实现原理：通过加一冗余码，来检验或纠错编码

• 码字 ： 由若干位代码组成的一个字

• 码距：将两个码字逐位进行对比，具有不同的位的个数称为两个码字间的距离，一种编码方案可能有若干个合法码字，各合法码字间的最小距离称为“码距。也称海明距离。

计算码距方法

计算0100和1111

• 直接观察法：可以看出，有3个数位值不同，所以码距为3.

• 异或计算法：0100?1111=1011 ，结果为1011，里面有几个1就代表有多少个数位值不同，即码距是多少，这里码距是3。

• 若码距=2，有检错能力；若码距≥3，可能还会纠错能力

奇偶校验码

校验原理

• 在原编码中加一个校验位，则原编码就变成了校验码，它的码距为2，可以检查出奇数位错误，但不能检查出偶数位错误，增加的冗余位为奇偶校验位，一般校验位设置在原编码的最左边或最右边。
• 奇校验码：整个校验码（信息位+校验位）中1的个数位奇数
• 偶校验码：整个校验码（信息位+校验位）中1的个数位偶数

奇偶校验

• 偶校验的硬件实现：各信息进行异或（模2加）运算，得到的结果即为偶校验位
  
• 奇偶校验码的码距d=2，仅能检测岀奇数位错误，无纠错能力

异或法制

奇数个一相异或 为 1
偶数个零相同或 为 1

总结

• 上述奇偶校验码不能发现偶数位错误，能发现奇数位错误，但是不能定位。

海明校验码

• 一种多重奇偶校验码。

• 实现原理：在有效信息位中加入几个校验位形成海明码，并把海明码的每一个二进制位分配到几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验位的值发生变化。

• 特点：可以发现错误，定位错误位置，自动纠正错误。 可以检测双比特错误，但只能纠正单比特错误。
  

海明校验码的分布规律

• 校验位P放在海明位号为 2 ^(i-1) 的位置上
  

海明码纠错以及定位

实现原理

• 每个校验组分别利用校验位和参与形成该校验位的信息位进行奇偶校验检查，即异或运算?，构成k个校验方程。

S1=P1?D1?D2?D4
S2=P2?D1?D3?D4
S3=P3?D2?D3?D4

• 若S1S2S3=000,则说明无错，否则说明出错。这个数的值就是出错的位置，如S1S2S3=001,表示第1位出错，即H1出错，直接将该位取反就可以达到纠错的目的。

海明码完善

总结

循环冗余校验码（CRC）

• 首先，发送端和接受端会有一个生成多项式G(x)约定,生成多项式G(x)的最高次幂为R。任意一个二进制数码都可用一个系数为0或1的多项式与之对应。比如：二进制数码 1101 对应的G(x)=1*X3+1*X2+0*X1+1*X0= X3+X2+1

• 确定生成多项式即为除数

• 在发送端，将要传送的K位二进制信息码左移R位，将它与生成多项式G(x)所对应的的二进制数码进行模2除法，产生余数，生成一个R位检验码，并附在信息码后，构成一个新的二进制码（CRC）码，共K+R位。
  

模2除算法

用于求 CRC 码

1、被除数最高位 为 1，上 1 否则 上 0
2、两者进行异或运算，一直得到校验位（一定比被除数少 1 位）

求得： 101001 的 CRC 码为 101001 001

拓展

模2运算：分为模2加、模2减、模2乘、模2除，不考虑进位和借位。

检错与纠错

注意： 余数与出错位的规律，并不是简单的余数的二进制转十进制，因为有三位对应二的三次方即为八除去正确的 000 ，即为七个一循环。

纠错概述

但是实际一般运用于检错

特点

理论上可以证明循环冗余校验码的检错能力有以下特点：
1）可检测出所有奇数个错误；
2）可检测出所有双比特的错误；
3）可检测出所有小于等于校验位长度的连续错误；

总结