差错控制技术在计算机网络中的应用

数据通信系统的基本任务是高效而无差错地传输数据。所谓差错，就是在通信过程中，接收端收到的数据与发送端实际发出的数据出现不一致的现象。由于物理线路上存在着各种干扰和噪声，数据信息在传输过程中会产生差错，出现数据丢失、改变等问题。差错检测与控制就是指在数据通信过程中能及时检测到差错发生，发现或纠正差错，将差错限制在尽可能小的范围内。

1.差错类型

通信信道的噪声分为热噪声和冲击噪声两种。由这两种噪声分别产生两种类型的差错，随机差错和突发差错。

热噪声是由传输介质导体的电子热运动产生的，它的特点是时刻存在，幅度较小且强度与频率无关，但频谱很宽，是一类随机噪声。由热噪声引起的差错称随机差错，此类差错的特点是差错是孤立的，在计算机网络应用中是极个别的。

与热噪声相比，冲击噪声幅度较大，是引起传输差错的主要原因。冲击噪声的持续时间要比数据传输中的每比特发送时间长，因而冲击噪声会引起相邻多个数据位出错。冲击噪声引起的传输差错称为突发差错。常见的突发差错是由冲击噪声（如电源开关的跳火、外界强电磁场的变换等）引起的，它的特点是：差错呈突发状，影响一批连续的比特数据（突发长度）。计算机网络中的差错主要是突发差错。

通信过程中产生的传输差错，是由随机差错和突发差错共同构成的。

2.误码率

数据传输过程中可用误码率来衡量信道数据传输的质量，误码率是指二进制码元在数据传输系统中出现差错的概率，可用下式表达：

由于差错的出现具有随机性，所以实际测量一个数据传输系统时，只有被测量的传输二进制码元足够大，才会得到较为真实的误码率值。

电话线路在300～2 400 b/s 传输率时，平均误码率在10− 4～10−6；在4 800～9 600 b/s 传输率时，平均误码率在10- 2～10- 4。而现在计算机通信系统的平均误码率要求低于10−9，所以通过普通电话线路进行计算机通信时，必须采取差错控制技术。

3.差错的控制方法

最常用的差错控制方法是差错控制编码。数据信息位在向信道发送之前，先按照某种关系附加上一定的冗余位，构成一个码字后再发送，这个过程称为差错控制编码过程。接收端收到该码字后，检查信息位和附加的冗余位之间的关系，以检查传输过程中是否有差错发生，这个过程称为检验过程。

差错控制编码可分为纠错码和检错码。

（1）纠错码。纠错码指在发送每一组信息时发送足够的附加位，接收端通过这些附加位在接收译码器的控制下不仅可以发现错误，而且还能自动地纠正错误。如果采用这种编码，传输系统中不需反馈信道就可以实现一个对多个用户的通信，但译码器设备比较复杂，且所选用的纠错码与信道干扰情况有关。某些情况为了纠正差错，要求附加的冗余码较多，这将会降低传输的效率。现在比较常见的纠错编码有海明纠错码、正反纠错码等。

（2）检错码。检错码是指在发送每一组信息时发送一些附加位，接收端通过这些附加位可以对所接收的数据进行判断，看其是否正确，如果存在错误，它不能纠正错误而是通过反馈信道传送一个应答帧把这个错误的结果告诉给发送端，让发送端重新发送该信息，直至接收端收到正确的数据为止。

差错控制方法分两类，一类是自动请求重发（ARQ），另一类是前向纠错（FEC）。

在ARQ 方式中，当接收端发现差错时，就设法通知发送端重发，直到收到正确的码字为止。ARQ 方式只使用检错码。

在FEC 方式中，接收端不但能发现差错，而且能确定二进制码元发生错误的位置，从而加以纠正。FEC 方式必须使用纠错码。

4.编码效率

衡量编码性能好坏的一个重要参数是编码效率R，它是码字中信息位所占的比例。编码效率越高，即R 越大，信道中用来传送信息码元的有效利用率就越高。编码效率计算公式为

R＝k/n＝k/(k+r)

式中，k 为码字中的信息位位数；r 为编码时外加冗余位位数；n 为编码后的码字长度。

5.奇偶检验码

奇偶校验码是一种最简单也是最基本的检错码。它是在原始数据后附加一个校验位，构成一个带有校验位的码组。偶校验时，使码组中“1”的个数为偶数；奇校验时，使码组中“1”的个数为奇数，并把整个码组一起发送出去。接收端收到信号后，根据使用的是奇检验还是偶检验对每个码组进行奇或偶校验，以确定是否有差错发生。使用奇偶检验码发送和接收数据的过程如图2.29所示。

图2.29　奇偶校验码工作过程

奇偶校验只能检测出奇数个错而不能检测出偶数个错，即奇偶校验不能检测任何偶数位的传输差错。奇偶校验简单，易于实现，在位数不长、传输速率较低的情况下常常采用。在以字符为单位的异步传输方式中常采用奇偶校验。

奇偶校验码是一种最简单也是最基本的检错码，一维奇偶校验码的编码规则是把信息码元先分组，在每组最后加一位校验码元，使该码中1 的数目为奇数或偶数，奇数时称为奇校验码，偶数时称为偶校验码。

1）垂直奇偶校验的特点及编码规则

（1）编码规则。

偶校验：ri=I1i+I2i+…+I pi（i=1， 2…，q）

奇校验：ri=I1i+I2i+…+Ipi+1（i=1， 2…，q）

垂直奇偶校验的编码效率：R=P/（P+1）。

式中，p 为码字的定长位数；q 为码字的个数。(www.xing528.com)

（2）特点。

垂直奇偶校验又称纵向奇偶校验，它能检测出每列中所有奇数个错，但检测不出偶数个的错，因而对差错的漏检率接近1/2。

2）水平奇偶校验的特点及编码规则

（1）编码规则。

偶校验：ri=Ii1+Ii2+…+I iq（i=1， 2…，p）

奇校验：ri=Ii1+Ii2+…+Iiq+1（i=1， 2…，p）

水平奇偶校验的编码效率：R=q/（q+1）。

式中，p 为码字的定长位数；q 为码字的个数。

（2）特点。

水平奇偶校验又称横向奇偶校验，它不但能检测出各段同一位上的奇数个错，而且还能检测出突发长度小于或等于P 的所有突发错误。其漏检率要比垂直奇偶校验方法低，但实现水平奇偶校验时，一定要使用数据缓冲器。

3）水平垂直奇偶校验的特点及编码规则

（1）编码规则。

若水平垂直都用偶校验，则

水平垂直奇偶校验的编码效率：R＝pq/[（p+1）（q+1）]。

（2）特点。

水平垂直奇偶校验又称纵横奇偶校验。它能检测出所有3 位或3 位以下的错误、奇数个错、大部分偶数个错以及突发长度小于或等于p+1 的突发错。可使误码率降至原误码率的百分之一到万分之一。具备较强的检错能力，但是有部分偶数个错误不能测出。水平垂直奇偶校验还可以自动纠正差错，使误码率降低2～4 个数量级，适用于中、低速传输系统和反馈重传系统。

6.循环冗余校验CRC

循环冗余校验码（CRC）是一类重要的线性分组码，又称为多项式码。利用CRC 进行检错的过程可简单描述为：在发送端将要发送的信息数据与一个通信双方共同约定的数据进行除法运算，并根据余数得出一个校验码，然后将这个校验码附加在信息数据帧之后一起发送出去。

接收端在接收到数据后，将包括校验码在内的数据帧再与约定的数据进行除法运算，若余数为“0”，则表示接收的数据正确；若余数不为“0”，则表明数据在传输的过程中出现错误。使用CRC 的过程如图2.30所示。CRC 的编码和解码简单，检错和纠错能力强，在通信领域广泛地用于实现差错控制。

图2.30　循环冗余校验（CRC）码工作过程

1）循环冗余码的工作原理

循环冗余码CRC 在发送端编码和接收端校验时，都可以利用事先约定的生成多项式G（X）来得到，k 位要发送的信息位可对应于一个（k-1）次多项式K（X），r 位冗余位则对应于一个（r -l）次多项式R（X），由r 位冗余位组成的n=k+r 位码字则对应于一个（n-1）次多项式T（X）=Xr×K（X）+R（X）。

例如：

信息码110011：信息多项式K（X）=X5+X4+X+1（k=6）

冗余码1010：冗余多项式R（X）=X3+X（r=4）

n＝k+r 位码字对应的一个（n-1）次多项式为

T（X）=Xr×K（X）+R（X）=X9+X8+X5+X4+X3+X，对应的码字为110011 1010

由信息位产生冗余位的编码过程，就是已知K（X）求R（X）的过程。在GRC 码中可以通过找到一个特定的r 次生成多项式G（X），然后用Xr×K（X）取模2 除以G（X），得到的余式就是R（X）。

2）循环冗余校验码的特点

（1）可检测出所有奇数位错。

（2）可检测出所有双比特的错。

（3）可检测出所有小于或等于校验位长度的突发错。