1.奇偶监督码

奇偶校验码也称奇偶监督码，它是一种最简单的线性分组检错编码方式。其方法是首先把信源编码后的信息数据流分成等长码组，在每一信息码组之后加入一位（1bit）监督码元作为奇偶检验位，使得总码长n（包括信息位k和监督位1）中的码重为偶数（称为偶校验码）或为奇数（称为奇校验码）。如果在传输过程中任何一个码组发生一位（或奇数位）错误，则收到的码组必然不再符合奇偶校验的规律，因此可以发现误码。奇校验和偶校验两者具有完全相同的工作原理和检错能力，原则上采用任一种都是可以的。

由于每两个1的模2相加为0，故利用模2加法可以判断一个码组中码重是奇数或是偶数。模2加法等同于“异或”运算。下面以偶监督为例。

对于偶校验，应满足

故监督位码元a 0可由下式求出，即

不难理解，这种奇偶校验编码只能检出单个或奇数个误码，而无法检知偶数个误码，对于连续多位的突发性误码也不能检知，故检错能力有限。另外，该编码后码组的最小码距为d 0=2，故没有纠错码能力。奇偶监督码常用于反馈纠错法。

2.行列监督码

行列监督码是二维的奇偶监督码，又称为矩阵码，这种码可以克服奇偶监督码不能发现偶数个差错的缺点，并且是一种用以纠正突发差错的简单纠正编码。

其基本原理与简单的奇偶监督码相似，不同的是每个码元要受到纵和横的两次监督。具体编码方法如下：将若干个所要传送的码组编成一个矩阵，矩阵中每一行为一码组，每行的最后加上一个监督码元，进行奇偶监督，矩阵中的每一列则由不同码组相同位置的码元组成，在每列最后也加上一个监督码元，进行奇偶监督。每一行每一列都是一个奇偶监督码，当某一行（或某一列）出现偶数个差错时，该行（或该列）虽不能发现，但只要差错所在的列（或行），没有同时出现偶数个差错，则这种差错仍然可以被发现。矩阵码不能发现的差错只有这样一类：差错数正好为4的倍数，而且差错位置正好构成矩形的4个角。因此，矩阵码发现错码的能力是十分强的，它的编码效率比奇偶监督码要低。

3.恒比码

恒比码又称为定比码。在恒比码中，每个码组“1”和“0”都保持固定的比例，故得此名。这种码在检测时，只要计算接收到的码组中“1”的数目是否对就知道有无错误。在我国用电传机传输汉字时，只使用阿拉伯数字代表汉字。这时采用的所谓“保护电码”就是“3∶2”或称“5中取3”的恒比码，即每个码组的长度为5，其中“1”的个数总是3，而“0”的个数总是2，如表2-1所示。

表2-1　恒比码编码

本来以5位码元组成的码组总共可以有25=32种，而恒比码规定只有确切地含有3个“1”，2个“0”的那些码组为准用码组，而有3个“1”，2个“0”的5位码组共有多少？这是“5中 取3”求组合的算法，组合数为

一般情况下，从“n中取m”（m＜n）恒比码的码组数为

恒比码适用于传输字母和符号。

4.循环冗余校验码（CRC）

循环码是一种重要的线性码，它有3个主要数学特征：

（1）循环码具有循环性，即循环码中任一码组循环一位（将最右端的码移至左端）以后，仍为该码中的一个码组。

（2）循环码组中任两个码组之和（模2）必定为该码组集合中的一个码组。

（3）循环码每个码组中，各码元之间还存在一个循环依赖关系，b代表码元，则有

用多项式码作为检验码时，发送器和接收器必须具有相同的生成多项式g（x），其最高、最低项系数必须为1。CRC编码过程是将要发送的二进制序列看作是多项式的系数，除以生成多项式，然后把余数挂在原多项式之后。CRC译码过程是接收方用同一生成多项式除以接收到的CRC编码，若余数为零，则传输无错。编码译码方法：

（1）令r为生成多项式g（x）的阶，将r个“0”附加在信息（数据）元的低端，使其长度变为k+r位，相应于多项式x r·m（x）。

（2）x r·m（x）÷g（x）[mod2]，得余数。

（3）x r·m（x）与余数对应位异或，得编码信息T（x）。

（4）接收器收到发来的编码信息后，用同一个生成多项式g（x）除以编码信息，若余数为零，则表示接收到正确的编码信息，否则有错。

（5）把收到的正确编码信息T（x）去掉尾部r位，即得数据信息M（x）。

设接收到的信息不是发送的编码信息T（x），而是T（x）+E（x）。(www.daowen.com)

例如：有差错的编码信息为

其中，1101011011为T（x）；0100010000为E（x）。若接收到的有差错的编码信息为T（x）+E（x），用g（x）除以T（x）+E（x），则得余数为E（x）/g（x）的余数。因为T（x）/g（x）余数为零，所以[T（x）+E（x）]/g（x），E（x）/g（x）这时应该有余数，若无余数则检不出错。

有r位校验位的多项式码将能检测所有不大于r位的突发错，故只要k-1＜r，就能检测出所有突发错，这是一个很有用的结论。生成多项式g（x）的国际标准如表2-2所示。

表2-2　生成多项式g（x）的标准

CRC—16和CRC—CCITT两种生成多项式生成的CRC码可以捕捉一位错、二位错、具有奇数个错的全部错误，可以捕捉突发错长度小于16的全部错误、长度为17的突发错的99%～99.8%、长度为18以上的突发错的99%～99.7%。CRC—16和CRC—CCITT可以用硬件实现。

5.海明码

错误的纠正可以通过两种方式进行。一种方式是发现错误时，接收方可以让发送方重新发送整个数据单元；另一种方式是可以采用纠错码，自动纠正错误。

（1）纠正单比特错误所需的冗余比特数。理论上，可以自动纠正任何一种二进制比特错误。但是纠错码比检错码要复杂得多，并且需要更多的冗余比特位。纠正多比特错误和突发错误所需要的冗余比特位数非常巨大，因此这样做一般是十分低效的。这里只讨论单比特错误的纠正。

设要发送的数据单元的位数为m，为纠正一个单比特错误，冗余位的位数r应该是多少呢？因为要发送的二进制码字为m+r位，任何一位都有可能发生错误（包括冗余位），要表示哪一位发生错误，需要m+r种状态，另外还有一种无任何差错的状态，所以，冗余位应能够表示m+r+1种状态。通过以上的分析，r应满足如下条件：

由R.W.Hamming提出了一种海明码技术，该技术使用这些冗余位来发现错误并纠正错误。

（2）冗余比特的定位。

（3）确定冗余比特的值。海明码中每一位数据位由几个冗余位共同检验，那么某一个数据位到底由哪几个冗余位检验呢？可以由如下方法得到：将这一位的编号展开成2的乘幂的和，那么每一项所对应的位就是该数据位的检验位，也就是说该数据位要受这几个冗余位检验。例如7=20+21+22=1+2+4，所以数据位7的检验位是1、2和4，就是说7要受冗余位r1、r2和r4检验。

从以上的分析我们可以得出如下结论：r1检验所有编号被21整除后为1的位，也就是所有的奇数位。r2检验所有编号大于或等于2并且被22整除后余数为3和2的位。r4检验所有编号大于或等于4并且被23整除后余数位7、6、5和4的位。r8检验所有编号大于或等于8并且被2整除后余数为15、14、13、12、11、10、9和8的位。依此类推。也就是说：从第1位开始，每取1位空1位，再每取1位空1位……所取得的位要受r1的检验；从第2位开始，每取2位空2位，再每取2位空2位……所取得的位要受r2的检验；从第4位开始，每取4位空4位，再每取4位空4位……所取得的位要受r4的检验；从第8位开始，每取8位空8位，再每取8位空8位……所取得的位要受r8的检验。

校验采用偶校验的形式。比特序列10011101的海明码实现过程如下：首先，确定冗余位的位数：因为24≥8+4+1，所以冗余位的位数为4。然后分别计算冗余位（r1，r2，r4，r8）的值，则比特序列10011101的海明码为100101101111。

（4）错误检测与纠正。接收方接收到一个海明码后，对每一个冗余位及其相关的数据位进行偶校验，然后将新的校验位的值按照冗余比特位置（…r8r4 r2r1）排成一个二进制数。如果该二进制数为0，则无错误。如果该二进制数不为零，该二进制数的值就指出了错误的位置。一旦确定了错误的位置，接收方就可以将该比特取反，并纠正该错误。例如海明码100101101111，在传输的过程中变成了100100101111，也就是说第7位发生了错误，通过对r8、r4、r2和r1的计算，得到r8=0，r4=1，r2=1，r1=1，r8r4r2r1=7，说明在第7位发生错误。