计算机基础知识——校验码概述

1 码距

2 奇偶校验

3 CRC循环冗余校验码

3.1 多项式

3.2 编码的组成

3.3 生成多项式

3.4 校验码的生成

4 海明校验码和恒比码

4.1 校验方程

4.2 恒比码

1 码距

码距是恒量一种编码方式的抗错误能力的一个指标。数字信息在传输和存取的过程中，由于各种意外情况的发生，数据可能会发生错误，即所谓误码。一种编码，如果所有可能的码字都是合法码字，如ASCII,当码字中的一位发生错误时，这个错误的码仍然在编码体系中，这样我们称这种编码的码距小，如果我们把编码体系变得稀疏一点，使得很多的信号值不在编码体系之内，这样，合法的码字如果出现错误，可能就变成了不合法的编码，这样的编码的码距就大。
定义：一个编码系统中任意两个合法的编码之间的不同的二进制位称为这两个码字的码距。该编码系统的任意两个编码之间的距离的最小值称为该编码系统的码距。
显然，码距越大，编码系统的抗偶然错误能力越强，甚至可以纠错（纠错详见各种编码的介
绍）。同时，码距的增加，使得必须提供更多的空间来存放码字，数据冗余增加，编码效率则降低
了，软件设计师需要综合考虑系统效率和系统健壮性两个方面，在众多的编码体系中选择适合特定
目标系统的编码。

2 奇偶校验

奇偶校验较为简单，被广泛地采用，常见的串口通信中基本都使用奇偶校验作为数据校验的方
法。
一个码距为1的编码系统加上一位奇偶校验码后，码距就成为2。产生奇偶校验时将信息数据的各位进行模二加法，直接使用这个加法的结果的称为奇校验。把这个加法值取反后作为校验码的称为偶校验。从直观的角度而言，奇校验的规则是：信息数据中各位中1的个数为奇数，校验码为1,否则校验码为0,偶校验则相反。
使用一位奇偶校验的方法能够检测出一位错误，但无法判断是哪一位出错。当两位同时出错
时，奇偶校验也无法检测出来。所以奇偶校验通常用于对少量数据的校验，如一个字节。在串口通
信中，通常是一个字节带上起始位、结束位和校验位共11位来传送。
如果对一位奇偶校验进行扩充，在若干个带有奇偶校验码的数据之后，再附上一个纵向的奇偶校验数据，这样，在出现一个错误的情况下，就能找到这个错误。而如果出现两个以上的错误，则可能无法判断误码的位置。这种方式在移动通信领域中被广泛采用。

3 CRC循环冗余校验码

这种方式已经被广泛地在网络通信及磁盘存储时采用，所以在历年考试中出现的概率也比较
大。先看几个基本概念。

3.1 多项式

在循环冗余校验码中，无一例外地要提到多项式的概念。一个二进制数可以以一个多项式来表
示。如1011表示为多项式 $x^{3}+x^{1}+x^{0}$ ，在这里，x并不表示未知数这个概念，如果把这里的x替换为2,这个多项式的值就是该数的值。从这个转换我们可以看出多项式最高幂次为n，则转换为二进制数有n+1位。

3.2 编码的组成

循环冗余校验码校验由k位信息码，加上R位的校验码。

3.3 生成多项式

和海明码的校验方程一样，生成多项式非常重要，以至于考试中总是直接给出。
由k位信息码如何生成R位的校验码的关键在于生成多项式。这个多项式是编码方程和解码方程共同约定的，编码方程将信息码的多项式除以生成多项式，将得到余数多项式作为校验码，解码方
程将收到的信息除以生成多项式，如果余数为0，则认为没有错误。如果不为0，余数则作为确定错误位置的依据。
生成多项式并非任意指定，它必须具备以下条件：最高位和最低位为1,2。数据发生错误时，余数
不为0，对余数补0后，继续做按位除，余数循环出现，这也是冗余循环校验中循环一词的来源。

3.4 校验码的生成

将k位数据 $C(x)$ 左移R位，给校验位留下空间，得到移位后的多项式： $C(x)*x^{R}$ 。
将移位后的信息多项式除以生成多项式，得到R位的余数多项式。
将余数嵌入信息位左移后的空间。
例：信息位为10100110 生成多项式： $a(x)=x^{5}+x^{4}+x+1$

则： $C(x)=x^{7}+x^{5}+x^{2}+x$

$C(x)*x^{R}=x^{5}*(x^{7}+x^{5}+x^{2}+x) =x^{12}+x^{10}+x^{7}+x^{6}$

求余式：

得到余式为 $x^{4}+x^{3}$ 即校验码为11000，所以得到CRC码是：1010011011000。
循环冗余校验码的纠错能力取决于k值和R值。在实践中，k取值往往取得非常大，远远大于R的
值，提高了编码效率。在这种情况下，循环冗余校验就只能检错不能纠错。一般来说，R位生成多项式可检测出所有双错、奇数位错和突发位错小于等于R的突发错误。使用循环冗余校验码能用很少的校验码检测出大多数的错误，检错能力是非常强的，这使得它得到了广泛的应用。

4 海明校验码和恒比码

海明校验码是奇偶校验的另一种扩充。和上面提到的奇偶校验不同之处在于海明码采用多位校验码的方式，在这些校验位中的每一位都对不同的信息数据位进行奇偶校验，通过合理地安排每个校验位对原始数据进行校验位组合，可以达到发现错误，纠正错误的目的。
假设数据位有m位，如何设定校验位k的长度才能满足纠正一位错误的要求呢？我们这里做一个
简单的推导。
k位的校验码可以有个 $2^{k}$ 值。显然，其中一个值表示数据是正确的，而剩下的 $2^{k}-1$ 个值意味着数据中存在错误，如果能够满足： $2^{k}-1>m+k$ （m + k为编码后的总长度），在理论上k个校验码就可以判断是哪一位（包括信息码和校验码）出现问题。

4.1 校验方程

校验方程是指示每个校验位对哪些信息位进行校验的等式。
确定了k的值后，如何确定每k位中的每一位对哪些数据进行校验呢？上面的推导只是说能够做
的，那么如何达到纠错的目的呢？但是幸好考试中都会列出海明校验方程。例如：

$\begin{matrix} \\ b_{1}\bigoplus b_{3}\bigoplus b_{5}\bigoplus b_{7}=0 \\ b_{2} \bigoplus b_{3} \bigoplus b_{6} \bigoplus b_{7}=0 \\ b_{4} \bigoplus b_{5} \bigoplus b_{6} \bigoplus b_{7}=0 \end{matrix}$

其中 $\bigoplus$ 表示逻辑加
在一般情况下，校验码会被插入到数据的1,2,4,8, …位置，那么，在数据生成时，按照提供的海
明校验方程计算出b1,b2,b4, …各位，在数据校验时，按照海明检验方程进行计算，如果所有的方程式计算都为0,则表示数据是正确的。如果出现1位错误，则至少有一个方程不为0.海明码的特殊之处在于，只要将①②③3个方程左边计算数据按③②①排列，得到的二进制数值就是该数据中出错的位，例如第6位出错，则③②①为110等于二进制的6。
当出现两位错误时，这种海明码能够查错，但无法纠错。