差错控制方法-计算机网络

差错控制的方法有两种, 第一种方法是改善通信线路的性能, 使错码出现的概率降低到满足系统要求的程度, 但这种方法受经济和技术的限制, 达不到理想的效果； 第二种方法是采用抗干扰编码和纠错编码将传输中出现的某些错码检测出来, 并用某种方法纠正检出的错码, 以达到提高实际传输质量的目的。 第二种方法最为常用, 目前广泛采用方法的有奇偶校验、方块校验和循环冗余校验等。

1.奇偶校验

奇偶校验又称为字符校验、垂直冗余校验(Vertical Redundancy Check, VRC), 其是以字符为单位的校验方法, 是最简单的一种校验方法。 奇偶校验的工作方式是： 在每个字符编码的后面另外增加一个二进制校验位, 主要目的是使整个编码中1 的个数成为奇数或偶数,如果使编码中1 的个数成为奇数则称为奇校验； 反之, 则称为偶校验。

例如, 字符R 的ASCII 编码为1010010, 后面增加一位进行奇校验10100100 (使1 的个数为奇数), 传输时其中一位出错, 如传成了10110100, 则奇校验就能检查出错误。 若传输有两位出错, 如10111100, 奇校验就不能检查出错误了。 在实际传输过程中, 偶然一位出错的机会最多, 故这种简单的校验方法还是很有用处的。

奇偶校验有如下主要特点：

(1) 只能发现单个比特差错, 如果有多个比特出错, 奇偶校验法无效；

(2) 一般只能用于对通信要求较低的异步传输和同步传输。

2.方块校验

方块校验又称为报文校验、水平冗余校验(Level Redundancy Check, LRC), 其是在奇偶校验方法的基础上, 在一批字符传输之后, 另外再增加一个检验字符, 该检验字符的编码方法是使每一位纵向代码中1 的个数也成为奇数或偶数。 例如, 6 个字符传输, 其方块校验如下。

采用这种方法, 不仅可以检验出1 位、2 位或3 位的错误, 还可以自纠正1 位出错, 使误码率降至原误码率的百分之一到万分之一, 纠错效果明显, 因此方块校验适用于中、低速传输系统和反馈重传系统。

3.循环冗余校验

循环冗余校验(Cyclic Redundancy Check, CRC) 是使用最广泛并且检错能力很强的一种校验方法。 循环冗余校验的工作方式是： 在发送端产生一个循环冗余码, 附加在信息数据帧后面一起发送到接收端, 接收端收到的信息按发送端形成循环冗余码同样的算法进行除法运算, 若余数为“0”, 就表示接收的数据正确, 若余数不为“0”, 则表明数据在传输的过程中出错, 发送端需重传数据。

该方法不产生奇偶校验码, 而是把整个数据块当成一串连续的二进制数据。 从代数结构来说, 把各位看成是一个多项式的系数, 则该数据块就和一个n 次的多项式相对应。

例如, 信息码110001 有6 位(从0 位到5 位), 表示多项式为M(x)= x5 + x4 + x0, 6个多项式的系数分别是1、1、0、0、0、1。

1) 生成多项式

在用CRC 进行校验时, 发送端和接收端应使用相同的除数多项式G(x), 称为生成多项式。 CRC 生成多项式由协议规定, 目前已有多种生成多项式列入国际标准中, 其具体形式如下。

CRC-12 G(x)= x12 + x11 + x3 + x2 + x + 1

CRC-16 G(x)= x16 + x15 + x2 + 1

CRC-CCITT 　G(x)= x16 + x12 + x5 + 1(www.xing528.com)

CRC-32 G(x)= x32 + x26 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x+1

生成的多项式G(x) 的结构及验错效果都是经过严格的数学分析与实验之后才确定的。要计算信息码多项式的校验码, 生成多项式必须比该多项式短。

2) 基本思想和运算规则

循环冗余校验的基本思想： 把要传输的信息码堪称是一个多项式M(x) 的系数, 在发送前, 将多项式用生成多项式G(x) 来除, 将相除结果的余数作为校验码跟在原信息码之后一同发送出去。 在接收端, 把接收到的含校验码的信息码再用同一个生成多项式来除, 如果在传输过程中无差错, 则应该除尽, 即余数应为0； 若除不尽, 则说明传输过程中有差错,应要求对方重新发送一次。

运算规则： 多项式以2 为模运算, 加法不进位, 减法不借位； 加法和减法两者都与异或运算相同； 长除法同二进制运算是一样的, 只是作减法时按模2 进行, 如果减出的值最高位为0, 则商为0, 如果减出的值最高位为1, 则商为1。

3) 检验和信息编码的求取方法

设r 为生成多项式G(x) 的阶。

(1) 数据多项式M(x) 的后面附加r 个“0”, 得到一个新的多项式M′(x)。

(2) 模2 除法求得M′(x) /G(x) 的余数。

(3) 该余数直接附加在原数据多项式M(x) 的系数序列的后面, 结果即为最后要发送的检验和信息编码多项式T(x)。

例 假设准备发送的数据信息码是1101011011, 生成多项式G(x) =x4+x+1, 计算信息编码多项式T(x)。

解 　M(x) =1101011011

G(x) =10011

r=4

信息码附加4 个0 后形成新的多项式M′(x) = 11010110110000用模2 除法求M′(x) /G(x) 余数的过程为

式中, 帧为1101011011； 除数为10011； 附加4 个0 后形成的串为11010110000； 传输的帧为11010110111110。 将余数1110 直接附加在M(x) 的后面, 求得要传输的信息编码多项式为

T(x) =11010110111110

采用循环冗余校验后, 其误码率比方块校验可再降低1 ～3 个数量级, 故在数据通信系统中应用较多。 循环冗余校验用软件实现比较麻烦, 而且速度比较慢, 但用硬件的移位寄存器和异或门实现循环冗余校验编码、译码和检错, 则简单而快速。