软件设计师精讲 校验码概述

https://www.bilibili.com/video/BV13U4y1E7oA/?p=8

校验码

考点1：奇偶校验码

考点2：CRC循环冗余校验码

考点3：海明校验码

https://www.bilibili.com/video/BV13U4y1E7oA/?p=9

校验码-校验码基础知识

码距：任何一种编码都由许多码字构成，任意两个码字之间最少变化的二进制位数就称为数据校验码的码距。

例如：用4位二进制表示16种状态，则有16个不同的码字，此时码距为1。如 0000 和 0001。

校验码-奇偶校验

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

奇校验：整个校验码（有效信息位和校验位）中“1”的个数为奇数。

假如：最开始传递信息的时候，“男”用1位二进制 "0" 来表示，“女”用二进制“1”来表示，传递信息的过程当中，1位二进制不好区分对错，如果接收方接收到1个“1”的话，如果要确定有没有错误，就不能确定，因为仍然在合法的码字当中，可以通过扩大码距所谓的校验一般都是通过扩大码距来进行校验、解决问题的。

例：如果采用奇校验的方式，信息位拼接上校验位之后，里面“1”的个数是奇数，拼接过程当中，信息位+校验位，“男”的“0”就变成“01”（后面加“1”，保持奇数个“1”），女的“1”就变成“10”（后面加“0”，保持奇数个“1”），接收方在接收后首先就是检查有多少个“1”，此时如果接收方收到了“00”或者“11”就可以确认传输数据有错（偶数个“1”不满足奇校验）。

偶校验：整个校验码（有效信息位和校验位）中“1”的个数为偶数。

注意：其实如果发送“11”，收到了“00”，奇偶校验就不能确认数据有错（同时存在多位错误），所以奇偶校验是有局限性的，只能检错部分情况，且并不能确定是哪个位置出错，所以奇偶校验只能进行检错，不能纠错。

奇偶校验，可检查1位（奇数位）的错误，不可纠错。

例题讲解

以下关于采用一位奇校验方法的叙述中，正确的是（C）。

A、若所有奇数位出错，则可以检测出该错误但无法纠正错误

B、若所有偶数位出错，则可以检测出该错误并加以纠正

C、若有奇数个数据位出错，则可以检测出该错误但无法纠正错误

D、若有偶数个数据位出错，则可以检测出该错误并加以纠正

https://www.bilibili.com/video/BV13U4y1E7oA/?p=10

CRC循环冗余校验码

CRC校验，可检错，不可纠错。

CRC的编码方法是：在k位信息码之后拼接r位校验码。应用CRC码的关键是如何从k位信息位简便地得到r位校验位（编码），以及如何从k+r位信息码判断是否出错。

把接收到的CRC码用约定的生成多项式G（X）去除（模二除法），如果正确，则余数为0；如果某一位出错，则余数不为0。不同的位数出错其余数不同，余数和出错位序号之间有惟一的对应关系。

例题讲解

在（D）校验方法中，采用模2运算来构造校验位。

A、水平奇偶

B、垂直奇偶

C、海明码

D、循环冗余

https://www.bilibili.com/video/BV13U4y1E7oA/?p=11

海明校验码

海明校验，可检错，也可纠错。

海明校验码的原理是：在有效信息位中加入几个校验位形成海明码，使码距比较均匀地拉大，

并把海明码的每个二进制位分配到几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验位的值发生变化，

这不但可以发现错误，还能指出错误的位置，为自动纠错提供了依据。

校验位求取公式：2^r≥m+r+1，也可以写成：2^r-1≥m+r，r是最小值，m是信息位的个数。

比如：要传递16位信息，那这16位信息在编码的过程当中，要2^r≥16+r+1，r=4时，2^r=16，2^r≥16+r+1不成立；

r>=5，才满足2^r≥16+r+1，所以海明校验位是5位。

要求能够通过信息位将校验码位数求出来。

具体校验位放在哪里呢？5个校验码分别放在 2⁰,2¹,2²,2³,2⁴。

也就是放在1，2，4，8，16位上，其它位置放上信息位