常用校验码（奇偶校验码、海明校验码、CRC校验码）

Love The Way You Lie 2021-08-19 22:38 2759阅读 0赞

转载自：[https://www.cnblogs.com/VersionP1/p/7779251.html][https_www.cnblogs.com_VersionP1_p_7779251.html] ，作者： [FunnyOne ][FunnyOne]

# [常用校验码（奇偶校验码、海明校验码、CRC校验码）][https_www.cnblogs.com_VersionP1_p_7779251.html] #

[一、奇偶校验码][Link 1]  
[二、海明校验码][Link 2]  
[三、CRC校验码][CRC]

计算机系统运行时,各个部之间要进行数据交换.交换的过程中，会有发生误码的可能（即0变成1或1变成0），由于计算机的储存是通过二进制代码来实现的的，误码会导致储存的内容发生改变。为确保数据在传送过程正确无误,常使用检验码. 我们常使用的检验码有三种. 分别是**奇偶校验码**、**海明校验码**和**循环冗余校验码(CRC)** 。

## ##

一、奇偶校验码

学习资料：[常用校验码][Link 3]

概念：

奇偶校验码是**奇校验码**和**偶校验码**的统称. 它们都是通过在要校验的编码上加一位校验位组成.

校验方法：

如果是奇校验加上校验位后,编码中1的个数为**奇数个**。如果是偶校验加上校验位后,编码中1的个数为**偶数个**。

### 分类： ###

1.  水平奇偶校验码：对每一个数据的编码添加校验位,使信息位与校验位处于同一行

例子：

当原编码在传输、储存的过程中发生了误码，1的数量就会改变，然后就能校验出该过程出现了错误。

1.  垂直奇偶校验码：把数据分成若干组,一组数据排成一行,再加一行校验码. 针对每一行列采用奇校验 或 偶校验

![format_png][]

缺点：

1.  只能检测出奇数位出错. 如果发生偶数位错误就无法检测

设原编码为0000，传输的过程中变成了1001。如果使用奇校验，原编码是00001，传输过后会变成10011，1仍然是奇数个，无法校验；如果使用偶校验，原编码是00000，传输过后会变成10010，1仍然是偶数个，同样无法校验。

1.  奇偶校验码无法检测出哪位出错.所以属于无法矫正错误的校验码。

校验过程中只知道1的数量发生变化，对于哪个地方发生变化无从知道。

### 二、海明校验码 ###

学习资料：[海明校验码][Link 4]

实现原理：

它的实现原理，是在m个数据位之外加上k个校验位，从而形成一个m+k位的新的码字，使新的码字的[码距][Link 5]比较均匀地拉大。把数据的每一个二进制位分配在几个不同的偶校验位的组合中，**当某一位出错后，就会引起相关的几个校验位的值发生变化，这不但可以发现出错，还能指出是哪一位出错**，为进一步自动纠错提供了依据。

两个码组对应位上数字的不同位的个数称为码组的距离，简称码距

例：

这两个二进制码中，有三个不相同的位置，所以码距为3.

须知：

1.  海明校验码是放在2的幂次位上的，即“1,2,4,8,16,32······”；
2.  信息位为m的原始数据，需要加入k位的校验码，它满足m+k+1<2^k；

例子：

要计算原始信息位为101101100的海明校验码。

先用m+k+1<2^k计算出校验位：9+k+1 <2^k→k=4，即校验位为4位。

因为海明校验码是放在2的幂次位上，所以插在位置1，2，4，8中

![format_png 1][]

![format_png 2][]

用到的校验码是看 **当前位置**由哪几个 **校验码所在的位置**的和

*  例如

校验码的位置是1，2，4，8。位置3= 1 + 2，所以位置3用到的校验码是1和2；位置7 = 1 + 2 + 4组成的，所以位置7用到的校验码是1，2和4。

然后将校验码校验的位置记录下来：

*  校验码1（位置1）：3，5，7，9，11，13
 *  校验码2（位置2）：3，6，7，10，11
 *  校验码3（位置4）：5，6，7，12，13
 *  校验码4（位置8）：9，10，11，12，13

注意：后面的数字串是位置的下标，不是值，值还是0或1。

然后做异或运算（相同时为0，不同时为1）

*  校验码1（位置1）：1 xor 0 xor 1 xor 0 xor 1 xor 0 = 1
 *  校验码2（位置2）：1 xor 1 xor 1 xor 1 xor 1 = 1
 *  校验码3（位置4）：0 xor 1 xor 1 xor 0 xor 0 = 0
 *  校验码4（位置8）：0 xor 1 xor 1 xor 0 xor 0 = 0

![format_png 3][]

### 三、循环冗余校验码(CRC校验) ###

学习资料：[CRC的校验原理以及例子][CRC 1]

原理：CRC检验原理实际上就是在一个p位二进制数据序列之后附加一个r位二进制检验码(序列)，从而构成一个总长为n＝p＋r位的二进制序列；附加在数据序列之后的这个检验码与数据序列的内容之间存在着某种特定的关系。如果因干扰等原因使数据序列中的某一位或某些位发生错误，这种特定关系就会被破坏。

实现步骤：

双方事先约定了一个R次多项式g(x)，即CRC码

CRC码的特点：

*  位数要少于原编码
 *  收尾为1
 *  自行决定

例：

原编码：1001001011

则CRC码可以为10011，也可以为11001等

**但是**：10010这种不可以，因为它的尾巴不是1，1001101011也不行，因为它的位数与原编码的一致。

要注意的是：CRC码并非是校验码，但需要通过CRC码来获得校验码。具体校验码的话要先让原编码加上CRC码位数个0（即CRC码有的多少位，就要加上多少位0在原编码的后面）然后用新原编码除CRC码，得到的**余数就是校验码**

例：

原编码=1010001101

CRC码设为：110101

校验码有5位，因此

新原编码：101000110100000

然后用新原编码除以CRC码：

![format_png 4][]

校验码就是01110

校验方法

用原编码与校验码进行模2减法，获得最终原编码。此时最终原编码除以CRC码是可以整除的，由于接收方也有相同的CRC码，在数据传输的过程中不发生错误，接收方用接收到的数据除以CRC码也是可以整除的，此时为无错误。同时，不能整除，说明传输过程中数据发生了错误。

[https_www.cnblogs.com_VersionP1_p_7779251.html]: https://www.cnblogs.com/VersionP1/p/7779251.html
[FunnyOne]: https://home.cnblogs.com/u/VersionP1/
[Link 1]: https://www.cnblogs.com/VersionP1/p/7779251.html#1
[Link 2]: https://www.cnblogs.com/VersionP1/p/7779251.html#3
[CRC]: https://www.cnblogs.com/VersionP1/p/7779251.html#4
[Link 3]: http://blog.csdn.net/ncepu_xu/article/details/70208630
[format_png]: /images/20210726/c246f875c8de4db0a93e0b593e87d5a2.png
[Link 4]: http://blog.csdn.net/u010927640/article/details/49531781?locationNum=3&fps=1
[Link 5]: https://www.cnblogs.com/VersionP1/p/7779251.html#2
[format_png 1]: /images/20210726/e8f50dc5283045348d9c75cf15fb7be1.png
[format_png 2]: /images/20210726/a17299460f2b46a797d5a8b3b5e61c19.png
[format_png 3]: /images/20210726/c6492e474b32449b90d4d65e8095f65a.png
[CRC 1]: http://blog.csdn.net/qq_32616315/article/details/71374965
[format_png 4]: /images/20210726/9d0666ea91af4f3d99d99db045761b51.png