一文搞懂奇偶校验、海明码和CRC

1. 为什么要有校验码？

  因为在数据存取和传送的过程中，由于元器件或者噪音的干扰等原因会出现错误，这个时候我们就需要采取相应的措施，发现并纠正错误，对于错误的检测和校正，大多采取“冗余校验”的思想，即除原数据外，额外增加若干位编码，这些新增的代码称为校验位。

2. 奇偶校验

  是一种常用的错误检测方法，用于校验代码传输的正确性。它根据被传输的一组二进制代码的数位中“1”的个数是奇数还是偶数来进行校验。如果采用奇数的方式，则称为奇校验；反之，则称为偶校验。

校验位的计算

  • 奇校验 ：如果数据单元中1的数量已经是奇数，则校验位设置为0；否则，校验位设置为1。
  • 偶校验 ：如果数据单元中1的数量已经是偶数，则校验位设置为0；否则，校验位设置为1。

举个栗子🌰

一个七位数的数据单元1011011

  • 奇校验编码：01011011
  • 偶校验编码：11011011

红色是校验位，可以在数据的前面也可以在数据的后面

总结

  奇偶校验是一种简单且易于实现的错误检测技术。虽然它不能解决所有的错误情况，但其低成本和实用性使它成为许多通信和存储系统的首选错误检测方法。随着技术的发展，更复杂的错误检测和纠正算法被开发出来，但奇偶校验仍然是计算机科学教育和初级通信系统中的重要组成部分。

2. CRC（循环冗余校验）

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

校验位的计算

  • 首先通过给定的生成多项式来确定除数，然后将要进行校验或者编码的数据进行模2除法（异或），取最后的余数然后与数据为拼接即可

举个栗子🌰

假设要传输的数据为1101011011，给定的生成多项式为G(X)=x4+x+1

根据题目中的生成多项式可以得出除数为10011，下面开始进行计算：

计算是首先要进行补零，零的个数取决于生成多项式的最高次幂

1
2
3
4
5
6
7
8
9
10
11
            1100001010
      _______________
10011 ) 11010110110000
        10011.........
         1001110110000
         10011........
              10110000
              10011...
                101000
                10011.
                  1110

经过上面的计算得出校验码位1110，所以实际发送的数据为11010110111110

当客户端收到这个数据之后，要进行CRC校验

1
2
3
4
5
6
7
8
9
10
11
12
            110000101
      _________________
10011 ) 11010110111110
        10011.........
         1001110111110
         10011........
              10111110
              10011...
                100110
                10011.
                     0

经过计算，得出的余数为0，所以说明这个数据没有差错，这就是CRC整个编码以及检错的过程

3. 海明校验码

  又称汉明码，是一种在计算机通讯中用于错误检测和纠正的编码方法。它是由理查德·海明于1950年发明的。它的核心原理是将数据分割成固定长度的块，每个块都用二进制表示，并在每个块中添加额外的校验位。这些校验位能够检测和纠正一个或多个位的错误。

校验位与数据位的关系

  • 2k−1>=m+k

m代表数据位，k代表校验位，校验位所在的位置是2n，其余都是数据位

举个栗子🌰

假设原始数据为01101110

位置 8 7 6 5 4 3 2 1
原始信息位 0 1 1 0 1 1 1 0

根据上述公式，当 m（信息位）=8时，k（校验位）最小可以取 4 ，所以可以得到如下表格：

位置 12 11 10 9 8 7 6 5 4 3 2 1
新的信息位 0 1 1 0 H8 1 1 1 H4 0 H2 H1

下面开始计算校验位的值

十进制对应二进制的数字如下

位置 二进制码
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
9 1001
10 1010
11 1011
12 1100
海明码 出现的位置 对应位置上的值异或 结果
H1 3，5，7，9，11 0⊕1⊕1⊕0⊕1 1
H2 3，6，7，10，11 0⊕1⊕1⊕1⊕1 0
H4 5，6，7，12 1⊕1⊕1⊕0 1
H8 9，10，11，12 0⊕1⊕1⊕0 0

这里计算的规律是，拿H1举例，H1在第一位，对应的二进制编码就是 1，所以我们要根据上面的进制表，找到第一位也是 1 的对应的位置，有 3,5,7,9,11，然后在找到这几个位置对应的数据位求异或，即可得到H1对应的海明码，其它以此类推……

通过上面的计算，我们就可以得到一个经过编码之后的数据：0110 0111 1001

位置 12 11 10 9 8 7 6 5 4 3 2 1
最终信息位 0 1 1 0 0 1 1 1 1 0 0 1

接收端收到对应的数据之后，开始校验数据是否有错误

假设 0110 0111 1001 ->传输为 0111 0111 1001

继续根据上面的方式，重新计算H1，H2，H4，H8校验位，计算的结果为1100

然后拿之前的校验码和新算出来的校验码求异或0101 ⊕ 1100 = 1001 = 9，所以可以判断出是第9位出现了错误，修改之后就完成了纠错

以上就是海明码检错以及纠错的过程

如果你认真的看到这里，你一定会有一个疑问，如果出现两个以上的错误时，还能纠错吗？下面实践一下

栗子2🌰

假设出现了两个数据位的错误 0110 0111 1001 ->传输为 0101 0111 1001

位置 12 11 10 9 8 7 6 5 4 3 2 1
最终信息位 0 1 0 1 0 1 1 1 1 0 0 1

再次计算校验位H1，H2，H4，H8为0110
再次与之前的校验码求异或 0101 ⊕ 0110 = 0011 = 3
按照这次的计算结果来看，是第三位数据出现了问题，但是很明显我们出错的是第9,10位，但是，当你把第三位修改之后，再次进行校验，发现没有问题了😗

所以通过上面的第二个例子我们可以直到，海明码只能检测一位错误，当出现两个以上的错误是，纠错结果会变得不准确

最终总结

特点 奇偶校验 CRC 海明码
原理 在数据中添加一个额外的校验位，使整个数据的1的个数为奇数（奇校验）或偶数（偶校验），用于检测单个比特的错误。 利用除法操作，在发送的数据后面附加一个固定长度的校验码（CRC码），接收端通过相同的除法操作验证数据的完整性。 通过在数据中添加冗余位（校验位），使得整个码字中特定位置的位数（1的个数）具有确定的奇偶性，以便检测和纠正错误。
错误检测能力 只能检测单个比特的错误，对于两个或更多比特的错误可能无法检测。 能够检测并纠正多个比特的错误，具体取决于CRC码的长度。 可以检测并纠正单个比特的错误，有时还能检测并纠正两个比特的错误。
错误纠正能力 无错误纠正能力。 根据CRC码的长度和算法设计，可以纠正一定数量的错误。 可以纠正单个比特的错误。
开销 仅需添加一个校验位，开销最小。 需要添加固定长度的CRC码，开销适中。 需要添加多个校验位，开销相对较大。
实现复杂度 最简单，只需进行简单的位运算。 中等复杂度，需要选择合适的CRC多项式和实现除法操作。 相对较高，需要设计合适的校验位位置和计算校验位的值。
应用场景 常用于简单的数据传输和存储系统，对错误检测和纠正要求不高的场合。 广泛应用于网络通信、数据存储等领域，用于确保数据的完整性。 适用于对错误检测和纠正有较高要求的应用，如内存错误检测。

笔记到这里就结束啦，你学会了么😮