差错控制编码|计算机网络技术基础

2023-10-22 理论教育版权反馈

【摘要】：常用的差错控制编码有奇偶校验码、循环冗余校验码等。因而，对差错的漏检率接近1/2。①可检测出所有奇数位错；②可检测出所有双比特的错；③可检测出所有小于、等于冗余位长度的突发差错。

常用的差错控制编码有奇偶校验码、循环冗余校验码等。

1.奇偶校验码

奇偶校验码是一种通过增加冗余，使得码字中“1”的个数为奇数个（奇校验）或偶数个（偶校验）的编码方法，它是一种检错码。

（1）垂直偶校验。

垂直偶校验又称纵向偶校验，其编码效率为：

R=p/（p+1）

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

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

（2）水平偶校验。

水平偶校验又称横向偶校验，水平偶校验的编码效率为：

R=q/（q+1）

式中，q为码字的个数。

特点：水平偶校验不但能检测出各码字同一位上的奇数个错，而且还能检测出长度不大于码字的定长位数的所有突发差错。其漏检率要比垂直偶校验方法低，但实现水平偶校验时，一定要使用数据缓冲器。

（3）水平垂直偶校验。

水平垂直偶校验又称纵横偶校验，它的编码效率为：

R=pq/［（p+1）（q+1）］

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

特点：水平垂直偶校验能检测出所有3位或3位以下的错误、奇数个错、大部分偶数个错以及长度不大于码字的定长位数加1的突发差错，适用于中、低速传输系统和反馈重传系统。

2循环冗余校验码（CRC）

（1）循环冗余校验码的工作方法。

在发送端产生一个校验和（冗余位），附加在信息位后面一起发送，接收端对收到的信息按与发送端同样的算法进行校验，若有错，需重发。

（2）循环冗余校验码的原理。(www.chuimin.cn)

采用循环冗余校验码的方法编码，发送方和接收方必须事先商定一个生成多项式G（x），循环冗余码在发送信息编码时和在接收端校验时，都要利用生成多项式G（x）。

循环冗余码的基本思想是：

①把k位要发送的信息位对应一个k—1次信息多项式K（x），即将位中看成是系数为“0”或“1”的从xk-1到x0的多项式的系数序列，高位是xk-1项的系数，下一位是xk-2项系数，以此类推。

②若生成多项式G（x）为r阶（最高1次），则循环冗余码的冗余位（校验和）r位，r位冗余位对应于一个r—1次多项式R（x）；用多项式xr×K（x）除以生成多项式G（x），所得的余式就为R（x）。

③将r位冗余位加k位信息位的末尾，所构成的由n位（n=k+r）组成的码字，就是要发送的带校验和的循环冗余码。

④该循环冗余码对应于一个n—1次的码多项式T（x），T（x）=xr×K（x）+R（x）。

显然，这个码多项式T（x）能被G（x）除尽。利用该特征，当接收方收到循环冗余码时，再用G（x）去除它，如果有余数，则传输出错。

（3）计算校验和的简易算法。

①设生成多项式G（x）为r阶，则在k位要发送的信息位的末尾附加r个零，得到一个k+r=n位的位串，作为被除数。

②按模2做除法，用对应于G（x）的位串（称为生成码）去除上述的被除数，余数就是校验和。

注意：运算法则是模2运算，即加法不进位，减法不借位，加法和减法两者相同，都是做异或运算。

③再按模2做减法，从被除数中减去余数，结果就是要传送的带校验和的帧。

目前，常见生成多项式G（x）国际标准有以下几种：

CRC—12：G（x）=x12+x11+x3+x2+x+1

CBG—16：G（x）=x16+x 15+x2+1

CRC—CCITT:G（x）=x 16+x12+x5+1

CRC—32：G（x）=x32+x 26+x 22+x 16+x12+x 11+x10+x8+x7+x5+x4+x2+x+1

（4）循环冗余校验码的特点。

①可检测出所有奇数位错；

②可检测出所有双比特的错；

③可检测出所有小于、等于冗余位长度的突发差错。