校验码

type

status

date

slug

summary

校验码基础知识

在数据存取和传送过程中，由于元器件或者噪音的干扰等原因出现错误，这时候我们需要采取相应的措施，发现错误并纠正错误。

对于错误的检测和纠正，通常采取“冗余校验”的思想，即除原数据外，额外增加若干位编码，这些新增的代码称为校验

码距

若干位代码组成的一个字称为码字，而两个码字具有不同代码的位数为这两个码字的距离，而码制里各种码字间最小的距离称为码距。

💡

比如8421码，1001和0000，有两位不同，所以距离是2，而0010和0011的距离为1，是最小的距离，故8421码码距为1

码距的作用:码距和这种类型的码的检错，纠错能力有关。

💡

如100000000和010000000，码距为2 如果数据中有一位变化了，如100000000变为110000000 我们可以很容易地判断出数据出错了，因为110000000不符合编码规则

奇偶校验码（只可检错，不可纠错）

编码方式

无论数据位多少位，校验位只有一位

数据位和校验位一共所含的1个数为奇数，称为奇校验

数据位和校验位一共所含的1个数为偶数，称为偶校验

💡

如下：（加粗为校验位）

数据	奇校验的编码	偶校验的编码
00000000	100000000	000000000
01010100	001010100	101010100
01111111	001111111	101111111

校验方式

在数据传输之前，我们会求一次校验位，传输后，会求一次校验位，那么，在奇偶校验中，我们通过比较这两个校验位是否相同，一般是采用异或的方式，若结果为1，则说明有奇数个错误，结果为0，则说明正确或者偶数个错误。

💡

举例：用1表示男，0表示女，使用奇校验码，将男用10表示，女用01表示。则在接收数据之后，通过异或检查1的个数，如果为奇数个1（01，10），则表示数据正确，如果为偶数个1（00，11），则数据发生错误。但是如果，男的10发生两个比特位的改变，变成01，则无法检测出错误。

由于数据传输过程一般是出现一位错误，而奇偶校验码能发现奇数个错误，所以奇偶校验的实用价值还是很高的。

例题

答案：C

CRC循环冗余校验码（只可检错，不可纠错）

引入

为什么大批量的数据不用奇偶校验码呢？

💡

在每个字符后增加一位校验位会增加大量的额外开销；尤其在网络通信中，对传输的二进制比特流没有必要再分解成一个个字符，因而无法采用奇偶校验码。

模2运算

模2运算不考虑加法进位和减法借位，上商的原则是当部分余数首位是１时商取１，反之商取0。然后按模2相减原则求得最高位后面几位的余数。这样当被除数逐步除完时，最后的余数位数比除数少一位。这样得到的余数就是校验位。

校验方式

数据信息M(x)为一个n位的二进制数据，将M(x)左移k位后，用一个约定的“生成多项式”G(x)相除，G(x)是一个k+1位的二进制数，相除后得到的k位余数就是校验位。校验位拼接到M(x)后，形成一个n+k位的代码，称该代码为循环冗余校验 ( CRC ) 码，也称（n+k,n）码。

一个CRC码一定能被生成多项式整除，当数据和校验位一起送到接受端后，只要将接受到的数据和校验位用同样的生成多项式相除，如果正好除尽，表明没有发生错误；若除不尽，则表明某些数据位发生了错误。通常要求重传一次。

例题

答案：D

海明校验码（既可检错，又可纠错）

引入

奇偶校验码和CRC码都具有一定的局限性，也就是只能检测奇数的错误，并且不能改正错误，这也就意味着数据一旦传输错误，我们必须要重新上传，那么，我们有办法确定错误发生的位置么？

只要确定了错误发生的位置，改正其实就是取反。

奇偶校验码是在数据的前面或者后面加上一位校验位，CRC校验码是在数据的后面加上k位校验码，那么，如果我们将数据分段，分成某些小段，这样是不是能判断错误发生的位置呢？

海明校验码

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

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

校验位计算公式

2^r ≥ m + r + 1

其中：r为校验码的位数，m为数据位的位数

例题

答案：A

💡

问题1： 2^r ≥ 32 + r + 1,可知r≥6 问题2: 海明校验码的解题技巧：从右往左数，找到数据位D（s）的位序（包含校验位），将其写为2^i+2^j……的形式，则D(s)由第（i+ 1）,（j + 1）……个校验位进行校验。 D5的位序为10，10 = 8 + 2，即10 = 2^3 + 2^1, 所以答案为B。

校验码基础知识

码距

奇偶校验码（只可检错，不可纠错）

编码方式

校验方式

CRC循环冗余校验码（只可检错，不可纠错）

引入

模2运算

校验方式

海明校验码（既可检错，又可纠错）

引入

海明校验码

校验位计算公式

总结