查看“差错控制”的源代码


实际通信链路都不是理想的,比特在传输过程中可能会产生差错,1可能会变成0, 0也可能会变成1,这就是比特差错。比特差错是传输差错中的一种。

通常利用编码技术进行差错控制，主要有两类：自动重传请求 ARQ 和前向纠错 FEC。在 ARQ方式中,接收端检测到差错时,就设法通知发送端重发,直到接收到正确的码字为止。在FEC方式中,接收端不但能发现差错,而且能确定比特串的错误位置,从而加以纠正。因此,差错控制又可分为检错编码和纠错编码。

== 检错编码 ==

检错编码都采用冗余编码技术,其核心思想是在有效数据(信息位)被发送前,先按某种关系附加一定的冗余位,构成一个符合某一规则的码字后再发送。当要发送的有效数据变化时,相应的冗余位也随之变化,使得码字遵从不变的规则。接收端根据收到的码字是否仍符合原规则来判断是否出错。常见的检错编码有奇偶校验码和循环冗余码。

=== 奇偶校验码 ===

奇偶校验码是奇校验码和偶校验码的统称，是一种最基本的检错码。它由 n-1 位信息元和1位校验元组成,如果是奇校验码,那么在附加一个校验元后,码长为n的码字中“1”的个数为奇数;如果是偶校验码,那么在附加一个校验元以后,码长为n的码字中“1”的个数为偶数。它只能检测奇数位的出错情况,但并不知道哪些位错了,也不能发现偶数位的出错情况。

=== 循环冗余码 ===

循环冗余码(Cyclic Redundancy Code, CRC)又称多项式码,任何一个由二进制数位串组成的代码都可与一个只含有 0 和 1 两个系数的多项式建立对应关系。

给定一个m bit的帧或报文，发送器生成一个rbit的序列,称为帧检验序列(FCS)。这样所形成的帧将由m+r比特组成。发送方和接收方事先商定一个多项式G(x) (最高位和最低位必须为1),使这个带检验码的帧刚好能被预先确定的多项式G(x)整除。接收方用相同的多项式去除收到的帧,如果无余数，那么认为无差错。

假设一个帧有m位,其对应的多项式为M(x),则计算冗余码的步骤如下:

# 加0。假设G(x)的阶为r,在帧的低位端加上r个0。
# 模2除。利用模2除法，用G(x)对应的数据串去除上一步中计算出的数据串，得到的余数即为冗余码(共r位,前面的0不可省略)。

多项式以2为模运算。按照模2运算规则,加法不进位,减法不借位,它刚好是异或操作。乘除法类似于二进制的运算,只是在做加减法时按模2规则进行。

通过循环冗余码(CRC)的检错技术,数据链路层做到了对帧的无差错接收。也就是说,凡是接收端数据链路层接受的帧,我们都认为这些帧在传输过程中没有产生差错;而接收端丢弃的帧虽然也收到了,但最终因为有差错而被丢弃,即未被接受。

<blockquote>注意：循环冗余码（CRC）是具有纠错功能的，只是数据链路层仅使用了它的检错功能，检测到帧出错则直接丢弃，是为了方便协议的实现。
</blockquote>
== 纠错编码 ==

在数据通信的过程中,解决差错问题的一种方法是在每个要发送的数据块上附加足够的冗余信息,使接收方能够推导出发送方实际送出的应该是什么样的比特串。最常见的纠错编码是海明码,其实现原理是在有效信息位中加入几个校验位形成海明码,并把海明码的每个二进制位分配到几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验位的值发生变化，这不但可以发现错位，而且能指出错位的位置，为自动纠错提供依据。