能够自我检错并纠错的编码-校验码

发表于 2024-04-28 分类于计算机组成原理阅读次数：

作者：小牛呼噜噜，首发于公众号「小牛呼噜噜」

哈喽，大家好呀，我是呼噜噜，今天我们来科普一个概念 校验码

在计算机的世界中，通信无处不存在，数据在传输过程中传输的都是0和1，然而由于网络的波动和不稳定性，传输过程中，信号的丢失与失真是很常见的，为了保证数据的准确性，引入校验码

那什么是校验码？校验码是指具有一定的检错和纠错能力的一种特殊的数据编码方法，也称作检错纠错码。其原理主要是通过增加一些冗余码，来检验或纠错编码，比如丢失某一比特的数据，可以通过校验码发现丢失，并还能找回来

本文我们来聊聊3个最常见的校验码：奇偶校验码、海明校验码、循环冗余校验码CRC

奇偶校验码

奇偶校验码Parity Check，在需要传输的一串二进制数据(有效信息位)中，添加一位冗余码(校验位)，即奇偶校验码=有效信息位+校验位

具体可分为，奇校验和偶校验

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

比如现在有8比特的数据，其中7位是有效信息位，还有1位是校验位，校验位在最高位还是最低位都可以，我们这里以在最低位为例：

我们可以发现，奇校验就是校验有效信息位+校验位中，1的个数是否是奇数；偶校验就是校验有效信息位+校验位中，1的个数是否是偶数。我们人类可以直接通过数1的个数来分辨，但对于计算机来说，利用异或运算就能直接判断1的个数

异或运算，简单来说就是ab2个值，如果相同的话为0 ，不同的话则为1
异或的数学符号为“⊕”，计算机符号为“xor”

当传输过程中，只要有1位数据发生了变化，此时奇偶校验码中1的个数就会发生奇偶转换，也就能够检测到出错，但并不能纠错，因为无法确认哪一位出问题了，即有检错能力无纠错能力

另外如果是2位出现了误码，可能会出现奇偶校验码中的1的个数，并没有发生奇偶转换，那么会误以为还是正常的咧！

奇偶校验只能检1位错，并且无纠错能力，但其也有优点，比如开销足够小，常用与校验1字节长(8位)的数据，因为1字节长的数据如果出问题，大概率是1位出问题，2位及其以上出错的概率较低。一般用于储存器读写和网络通讯传输数据等场景

循环冗余校验码

循环冗余校验码Cyclic Redundancy Check，简称CRC，是一种根据网络数据包或计算机文件等数据产生简短固定位数校验码的一种信道编码技术，主要用来检测或校验数据传输或者保存后可能出现的错误

CRC通过某种数学运算来建立数据位和校验位的约定关系，它的基本思想：

发送端和接收端双方约好一个生成多项式，我们这里用G(X)来代称
发送端基于有效信息数据和生成多项式G(X)相除，计算出余数(差错检测码)，再将差错检测码拼在有效信息数据后，作为发送数据
接收端接受到的数据除以生成多项式G(X)，可以除尽则编码正确；若有余数，则余数指明出错位所在的位置

模二算术运算

上面我们CRC中的除法是模二除法，所谓模二算术运算，与四则运算相同，模二运算也包括模二加、模二减、模二乘、模二除这四种二进制运算；与四则运算不同的是模二运算不考虑进位和借位

模二加法：0+0=0，0+1=1，1+0=1，1+1=0（相同为0，相异为1，类似于异或）
模二减法：0-0=0，0-1=1，1-0=1，1-1=0（相同为0，相异为1，类似于异或）
模二乘法：0x0=0，0x1=0，1x0=0，1x1=1（有0结果0，与普通四则运算里的乘法一样，唯一的区别是，模二乘法在部分积相加时按模二加，模二除法部分余数相减时按模二减）
模二除法：是模二乘法的逆运算，也是我们重点需要理解的，我们这里直接举个例子(二进制)：

1111000/1101=1011余111，其实我们可以发现模二除法计算过程中，主要用到了模二乘法和模二减法

模二除法与CRC算法密切相关，如果某一步被除数最高位为1，则可除，即对应位商为1；当最后余数的位数小于除数位数时，除法停止；当被除数的位数小于除数位数时，则商数为0，被除数就是余数

生成多项式

需要注意的是，我们上面所说的生成多项式其实是常数

一个r位的二进制常数可以用r-1次的生成多项式表示，比如G=1101,其G(x)=x^3+x^2+1

通过例子体会CRC

我们这里再举一个例子，比如有效信息数据1111和生成多项式G(x)=x^3+x^2+1

发送端：

约定的常数G=1101，有4位
有效信息数据左移(4-1)位，同时右侧补0，得1111000
1111000与1101做模二除法，得余数111
将余数加(模二加法)到有效信息数据后，得1111111=1111000 + 111

接收端：

接收到的数据1111111/1101,若余数为0，则数据正确

至于CRC的证明和漏检率，是经过数学证明的，因为推导过程比较复杂，且数学公式太多，本文就不赘述了，大家感兴趣地话，自行去找论文研究

CRC校验码如果任意一位发生错误(前提不是差错检测码部分出错)，则都会得到一个确定的余数，那么当选择合适的生成多项式时，会使得余数各不相同，所以能进行1位纠错，但纠错能力较为有限

但CRC是目前计算机通信领域最为普遍的校验方式，因为CRC校验码的检错能力极强，且检测成本较低，如果发现错误，直接触发网络数据表重传机制，对通信效率和安全提供了保障

因此在网络通讯、编码器和电路的检测等领域使用较为广泛。在检错的正确率与速度、成本等方面，都比奇偶校验等校验方式具有优势

海明校验码

海明码Hamming Code，也被称为汉明码，由Richard Hamming于1950年提出，其实际上就是多重奇偶校验码，用于数据的校验与纠正

其原理是在有效信息位中加入多个校验位形成海明码，将海明码中的每一位分组，进行奇偶校验；如果某一位出问题，会及时检错，并且校验位还能标注出错的位置

关注我，我们再聊的深入一点，比如我们接下来以101101100为例，来写出偶校验的海明码，来全面讲解海明码的具体原理与纠错实现

确认校验位位数

首先就是要加入多个校验位中多少个校验位，怎么确认其位数？

假设校验码有n位(也被称为编码字)，有效信息位有m位，校验位有r位。我们可以知道校验位的状态有2^r - 1个状态，要想校验位能够区分整个校验码是否正确，校验位的状态的个数要足够覆盖有效信息位加上校验位本身，因为校验位也有可能出错，那么就有2^r - 1>=m+r，即2^r >=m+r+1

记住这个上面这个公式，我们再看看常见的数据位和校验位之间的位数关系：

我们再来看看101101100，其m=9，由公式2^r >=m+r+1，可得r=4，所以n=m+r=13

再补充一个概念，码距，两个合法码字对应位上数字的不同位的个数

00和01，其码距为1，00和11其码距为2
一般来说，码距越大，其检测错误的位数越大，纠正错误的位数也越大(当码距不小于 2 的数据校验码，开始具有检错的能力)，另外纠错能力恒小于等于检错能力

确认校验位分布

海明码规定，校验位在校验码中的位置，是2的整数幂处，即2^0、2^1、2^2......

计算各校验位的值

我们接着把检验码中，各有效信息位都转化成校验位累加关系，实质是校验位的状态能够覆盖整个校验码的各位，如下：

1=1
2=2
3=1+2
4=4
5=1+4
6=2+4
7=1+2+4
8=8
9=1+8
10=2+8
11=1+2+8
12=4+8
13=1+4+8

上述各位的表达式，可能不够清晰，我们可以再通过表格来将上述表达式，重新排版一下：

我们把校验位单独拎出来，当列名，其他有效信息位当行号

横向看，每一位有效信息位，可以被哪几个校验位覆盖(控制)
纵向看，将有效信息位以校验位为基准，进行分组校验(奇偶检验)

你说那么多干嘛，我只想知道各校验位的值怎么算！

其实这些都是铺垫，举个例子，我们来求解一下H1校验位的值

H1这个组，有效消息位索引是3、5、7、9、11、13的值，然后加上H1这个校验位，1⊕1⊕0⊕1⊕0⊕0⊕H1需要满足偶校验的标准，所以H1位的值=1

同理可得H2=0,H3=1,H4=1，大家可以自行去算算

1
2
3

1⊕1⊕1⊕1⊕0⊕H2=0 ->H2=0
1⊕0⊕1⊕1⊕0⊕H3=0 ->H3=1
1⊕0⊕1⊕1⊕0⊕H4=0 ->H4=1

最后我们可以得到最终的海明码：

假如第6位报错，如何检错纠错？

假设由于网络波动，电压变化等各种原因，导致第6位(最终的海明码)出错，其值变为0，我们来看看海明码如何检错和纠错？

H1分组校验：1⊕1⊕0⊕1⊕0⊕0 ⊕1=0(从高位到低位)，偶校验通过
H2分组校验：1⊕1⊕1⊕0⊕0 ⊕0=1，偶校验不通过
H3分组校验：1⊕0⊕1⊕0⊕0 ⊕1=1，偶校验不通过
H4分组校验：1⊕0⊕1⊕1⊕0 ⊕1，偶校验通过

所以我们可以很轻易地知道H2和H3组中有问题，取二者交集，索引6、7两位最有可能出错；然后又因为H1校验位已经校验过索引7，所以最终索引6出错，其值应该被纠正为1

但如果2位发生错误，6、7位同时发生错误，H1、H2、H3分组校验不通过，不知道错误在哪个位置，但可以知道数据有误。所以海明码具有1位纠错能力，2位检错能力

当然我们可以提升其检错和纠错能力，加入的奇偶校验位的数目越多，错误检错和纠错能力随之提升，但代价是成本也随之更高

参考资料：

https://en.wikipedia.org/wiki/Hamming_code

https://www.cnblogs.com/scrutable/p/6052127.html

https://en.wikipedia.org/wiki/Cyclic_redundancy_check

本文就到这里啦，感谢阅读，原创不易，各位读者感觉有对你们帮助的话，点赞转发收藏在看，能否一气呵成！

提前祝大家五一快乐~