数据通信基础：差错控制 2021年5月26日
Study
0 条评论

一、差错控制

在数据传输中出现错误总是不可避免的，因此需要采用有效的差错控制方法。在数据通信中常用的办法是检错和纠错码。出现差错的原因分两种：

  • 热噪声引起的随机错误
  • 冲击噪声引起的突发错误

差错控制的原理很简单。在被传送的k位信息后附加r位冗余位，被传送的数据共k+r位，而这r位冗余位是用某种明确定义的算法直接从k位信息计算得出的，接收方对收到的信息应用同一算法，将结果与发送方给它的结果进行比较，若不相等则数据出现了差错。

  • 如果接收方知道有差错发生，但不知道是怎样的差错，向发送方请求重传，这种策略称为检错。
  • 如果接收方知道有差错发生，而且知道是怎样的差错，这种策略称为纠错。

二、奇偶校验

奇偶校验较简单，串口通信中使用奇偶校验作为数据校验的方法。它分为奇校验和偶校验两种，均是添加1位校验位，根据信息码中1的个数来决定校验位的取值，使得填入校验位后，1的个数为奇数（奇校验）或偶数（偶校验）。

例：
奇校验 1000110（ 0）
偶校验 1000110（ 1）

使用1位奇偶校验的方法能够检测出一位错误，但无法判断是哪一位出错。

当发生两位同时出错的情况时，奇偶校验也无法检测出来。所以奇偶校验通常用于对少量数据的校验，如一个字节。

三、海明码

海明码是奇偶校验的一种扩充。和奇偶校验的不同之处在于海明码采用多位校验码的方式，在这些多个校验位中的每一位都对不同的信息数据位进行奇偶校验，通过合理地安排每个校验位对原始数据进行的校验的位组合，可以达到发现错误、纠正错误的目的(当出现两位错误时，海明码能够查错，但无法纠错)。

还需要记住以下几个关键的关系。

  • 可查出多少位错误：可以发现“ ≤码距-1” 位的错误。
  • 可以纠正多少位错误：可以纠正“ <码距/2” 位的错误，因此如果要能够纠正n位错误，所需最小的码距应该是“ 2n+1”。

1、海明码的原理

在数据中间加入几个校验码，码距均匀拉大，当某一位出错，会引起几个校验位的值发生变化。

2、海明不等式

校验码个数为k，可以表示2k个信息，1个信息用来表示“没有错误”，其余2k -1个表示数据中存在错误，如果满足2k -1≥m+k（ m+k为编码后的数编总长度），则在理论上k个校验码就可以判断是哪一位（包括信息码和校验码）出现了问题。

3、海明码的编码规则

校验位依次放在第2i(i=0,1,2,3…)位，其余位置为信息位。

k3k2k1r2k0r1r0
7654321

4个信息位k0,k1,k2,k3；3个校验位r0,r1,r2。

第 i 个信息位的位数为参与校验它的校验位的位数之和。如上例7=4+2+1；6=4+2；5=4+1；3=2+1。

从上式可得，k3要参与r2,r1和r0的生成，k2参与r2和r1的生成，k1参与r2,r0的生成，k0参与r1和r0的生成。

则产生下列式子
r0=k3⊕k1⊕k0
r1=k3⊕k2⊕k0
r2=k3⊕k2⊕k1
其中⊕代表异或

B1⊕B3⊕B5⊕B7=0
B2⊕B3⊕B6⊕B7=0
B4⊕B5⊕B5⊕B7=0

若三个校验方程都成立，即方程式右边都等于0，则说明没有出现错误。若不成立，即方程式右边不等于0，说明有错。从三个方程式右边的值，可以判断那一位出错。出错位置为从下向上看相应的二进制数值，若三个方程式右边的值为100，说明第4位出错。

例：
求信息1011的海明码。

7654321位数
k3k2k1k0信息位
r2r1r0校验位
7654321位数
1011信息位
r2r1r0校验位
7654321位数
1011信息位
001校验位

四、循环冗余校验码

广泛地在网络通信及磁盘存储时采用。

1、多项式

在循环冗余校验(CRC)码中，无一例外地要提到多项式的概念。一个二进制数可以以一个多项式来表示。如1011表示为多项式X3+X1+X0，如果把这里的x替换为2，这个多项式的值就是该数的值。从这个转换可以看出多项式最高幂次为n，则转换为二进制数有n+1位。

2、编码组成

编码的组成是由K位信息码，加上R位的校验码。

3、校验码的生成

校验码的生成步骤如下：

  1. 将K位数据C(x)左移R位，给校验位留下空间，得到移位后的多项式为C(x) × XR。
  2. 将这移位后的信息多项式除以生成多项式，得到R位的余数多项式。
  3. 将余数作为校验码嵌入信息位左移后的空间。

循环冗余校验码的纠错能力取决于K值和R值。在实践中，K值往往取得非常大，远远大于R的值，提高了编码效率。在这种情况下，循环冗余校验就只能检错不能纠错。

一般来说，R位生成多项式可检测出所有双错、奇数位错和突发错位小于或等于R的突发错误。

检查信息码是否有CRC错误：
用待检查的信息码作被除数，除以生成多项式，如果能够整除就说明没有错误，否则就是出错了。
注意：当CRC检查出现错误时，它是不会进行纠错的，通常是让信息的发送方重发一遍。