差错控制编码方法-计算机网络与通信

1．奇偶校验码

奇偶校验码（PCC）是奇校验码和偶校验码的统称，是一种有效检测单个错误的检错方法。它的基本校验思想是在原信息代码的最后添加一位用于奇校验或偶校验的代码，这样最终的帧代码是由n-1 位信元码和1 位校验码组成。加上校验码的目的就是要让传输的帧中“1”的个数固定为奇数（采用奇校验时）或偶数（采用偶校验时），然后通过接收端对接收到的帧中“1”的个数的实际计算结果与所选定的校验方式进行比较，就可以判断出对应帧数据在传输过程中是否出错了。如果是奇校验码，在附加上一个校验码以后，码长为n 的码中“1”的个数为奇数；如果是偶校验码，则在附加上一个校验码以后，码长为n 的码中“1”的个数为偶数（0 个“1”也看成是偶数个“1”）。奇偶校验方法可以通过电路路来实现，也可以通过软件来实现。

假设现在要传输一个ASCII 字符，它的高7 位代码为1011010，现在要采用奇校验验方法，则该字符的校验码为“1”，放在最后一位，整个ASCII 字符代码就是1011010 1，因为该字符中高7 位信息代码中的“1”的个数是偶数个（4 个），必须再加一个“1”才能为奇数；同理，如果采用偶校验方法，则该字符的校验码为“0”，整个ASCII 字符代码就是1011010 0，因为该字符中高7 位信息代码中的“1”的个数已是偶数个（4 个），所以最后一位中不能再是“1”，只能为“0”。

奇偶校验方法只可以用来检查单个码元错误，检错能力较差，所以一般只用于本身误码率较低的环境，如用于以太局域网中、用于磁盘的数据存储中等。

思考：作为课堂练习，大家分析一下，如果所传输的二进制序列是11101100101，现要采用奇校验，则校验位的值是什么？采用偶校验呢？如果信息位中同时有2 位出错，还能检测出来吗？

2．循环冗余校验码

循环冗余码校验（Cycle Redundancy Check，CRC）是目前在数据通信和计算机网络中应用最广泛的一种校验编码方法，CRC 的漏检率要比前述奇偶校验码低得多。

CRC 校验原理看起来比较复杂、难懂，因为大多数书中基本上都是以二进制的多项式形式来说明的。其实其原理很简单，根本思想就是先在要发送的帧后面附加一个数（这个数就是用来校验的校验码，但要注意，这里的数也是二进制序列的，下同），生成一个新帧发送给接收端。当然，这个附加的数不是随意的，它要使所生成的新帧能被与发送端和接收端共同选定的某个特定数整除（注意，这里不是直接采用二进制除法，而是采用一种称为模2 除法的方法，即没有借位进位）。到达接收端后，再把接收到的新帧除以（同样采用模2 除法）这个选定的除数。因为在发送端发送数据帧之前就已附加了一个数，做了去余处理（也就已经能整除了），所A 结果应该没有余数。如果有余数，则表明该帧在传输过程中出现了差错。

具体来说，CRC 校验的实现分为以下几个步骤：

（1）先选择（可以随机选择，也可按标准选择，具体在后面介绍）一个用于在接收端进行校验时，对接收的帧进行除法运算的除数（二进制比特串，通常是以多项方式表示，所以CRC 又称多项式编码方法，这个多项式又称生成多项式）。(www.xing528.com)

（2）根据所选定的除数二进制位数（假设为k 位），在要发送的数据帧（假设为m 位）后面加上k－1 位“0”，接着以这个加了k－1 个“0”的新帧（一共是m+k－1 位）以“模2除法”方式除以上面这个除数，所得到的余数（也是二进制的比特串）就是该帧的CRC 校验码，又称FCS（帧校验序列）。但要注意的是，余数的位数比除数位数只能少一位，哪怕前面位是0，甚至是全为0（正好整除时）也都不能省略。

（3）再把这个校验码附加在原数据帧（就是m 位的帧，注意不是在后面形成的m+k－1位的帧）后面，建一个新帧发送到接收端，最后在接收端再把这个新帧以“模2 除法”方式除以前面选择的除数，如果没有余数，则表明该帧在传输过程中没出错，否则出现了差错。

从上面可以看出，CRC 校验中有两个关键点：一是要预先确定一个发送端和接收端都用来作为除数的二进制比特串（或多项式）；二是把原始帧与上面选定的除数进行二进制除法运算，计算出FCS。前者可以随机选择，也可按国际上通行的标准选择，但最高位和最低位必须均为“1”。例如，在IBM 的SDLC（同步数据链路控制）规程中使用CRC-16（也就是这个除数一共是 17 位） 生成多项式 g（x）=x16+x15+x2+1 （对应二进制比特串为11000000000000101）；而在ISO HDLC（高级数据链路控制）规程、ITU 的SDLC、X.25、V34、V.41、V.42 等中使用CCITT-16 生成多项式g（x）=x16+x15+x5+1（对应二进制比特串为11000000000100001）。

下面以一个例子来具体说明整个过程。现假设选择的CRC 生成多项式为g（x）=x4+x3+1，求二进制序列10110011 的CRC 校验码。下面是具体的计算过程：

（1）首先把生成多项式转换成二进制数，由g（x）=x4+x3+1 可以知道，它一共是5 位（总位数等于最高位的幂次加1，即4+1=5），然后根据多项式各项的含义（多项式只列出二进制值为1 的位，也就是这个二进制的第4 位、第3 位、第0 位的二进制均为1，其他位为0）很快就可得到它的二进制比特串为11001。

（2）因为生成多项式的位数为5，根据前面的介绍得知，CRC 校验码的位数为4（校验码的位数比生成多项式的位数少1）。因为原数据帧为10110011，在它后面再加4 个0，得到101100110000，然后把这个数以“模2 除法”方式除以生成多项式，得到的结果为0100（注意“模2 除法”的运算法则）。

（3）用上步计算得到的CRC 校验替换帧101100110000 后面的4 个“0”，得到新的帧101100110100。再把这个新帧发送到接收端。

（4）当以上新帧到达接收端后，接收端会用上面选定的除数11001 以“模2 除法”方式去除这个新帧，验证余数是否为0，如果为0，则证明该帧数据在传输过程中没有出现差错，否则就出现了差错。

思考：大家做一个练习：假设CRC 生成多项式为g（x）=x5+x4+x+1，要发送的二进制序列为100101110，求CRC 校验码是多少？