Alex_McAvoy

想要成为渔夫的猎手

数据链路层差错控制与常见校验码

【概述】

帧在传输过程中会出现帧错位错,造成这两种差错的来源是噪声,其可分为两方面:

  • 线路本身电气特性造成的随机噪声:信道固有、随机存在,可通过提高信噪比来减少
  • 外界原因造成的短暂冲击噪声:由于外界冲击造成、偶然发生,可通过编码技术来检错和纠错

对于帧错,通常在数据链路层引入定时器编号机制,当定时器到达设定的时间而帧的确认帧未到达时,发送方将重发该帧,同时,为保证接收方不会收到重复帧,对每个发送的帧进行编号,从而保证每一帧都能有且仅有一次正确地交付目的结点

对于位错,通常采用检错编码纠错编码的方法,关于这两种方法的具体介绍见下

【检错编码】

概述

检错编码是利用自动重传请求 ARQ 的方式进行差错控制,在接收端检测出错后,就通知发送端重发,直到接收到正确的编码位置

具体来说,检测编码采用了冗余编码技术,核心思想是在信息位发送前,先按一定关系附加一定的冗余校验位,构成一个符合某一规则的校验码后再发送,在接收方收到校验码后,根据有效位重新生成冗余校验位,与原冗余校验位进行比较,判断是否出现错误

在检测出错误后,有三种处理方案:请求重发、删除数据、通过余数的值由接收端自行纠正(CRC 码)

常见的检错编码有能检测奇数位错误奇偶校验码,以及能确定一位具体出错位置并纠正的循环冗余校验码

奇偶校验码

奇偶校验码是奇校验码和偶校验码的统称,是最基本的一种检错码,可以检测出奇数位错误,无法确定出错的位置

对于若干位信息位,再其前或其后增加一位的被称为奇偶校验位的冗余位,其取值将使得整个校验码(有效信息位和校验位)中 1 的个数为奇数或偶数

对于奇校验码来说,整个校验码中 1 的个数为奇数;对于偶校验码来说,整个校验码中 1 的个数为偶数

循环冗余校验码

循环冗余校验码(Cyclic Redundancy Code,CRC),又称多项式码,其基于线性编码理论,可以检测出一位错误,在 $k$ 位信息位后再拼接 $r$ 位的校验位,整个编码长度为 $n=k+r$ 位

一个 $k$ 位的帧可以看成从 $x^{k-1}$ 到 $x^0$ 的 $k$ 次多项式的系数序列,这个多项式的阶数是 $k-1$,高位是 $x^{k-1}$ 项的系数,举例来说,对于 1110011,其表示成多项式为 $x^6+x^5+x^4+x+1$

发送方和接收方会事先商定一个阶为 $r$ 的多项式 $G(x)$,在发送方,会将 $k$ 位的信息位左移 $r$ 位,低端补 0,生成长度为 $n=k+r$ 的带检验码的帧

之后,将带检验码的帧对阶为 $r$ 的多项式 $G(x)$ 作模 $2$ 除法,得到的 $r$ 位余数即长度为 $r$ 的冗余校验位,称为帧检验序列(FCS)

最后,将 $k$ 位信息位与 $r$ 位帧检验序列拼接,即可得到长度为 $n=k+r$ 位循环冗余校验码

接收方会用这个多项式 $G(x)$ 来除以收到的循环冗余校验码,如果余数为 $0$,则认为无差错,若余数不为 $0$,则说明该余数对应的十进制位出错(左端为高位,右端为低位)


举例来说,设生成多项式为 $G(x)=x^3+x^2+1$,要发送的信息为 101001

生成多项式的最高幂次为 $3$,即有 $r=3$;信息位长度为 $6$,即 $k=6$;同时,生成多项式对应的二进制码为 1101

首先对要发送的信息码向左移 $r$ 位,低位补 $0$,有:101001000

之后,对 101001000 用生成多项式对应的二进制码 1101 进行模 $2$ 除法,产生余数 001,即帧检验序列,具体过程如下图

此时,得到编码后的 CRC 码 101001001

对于接收方来说,假若收到的 CRC 码为 101001011,对其与生成多项式 $G(x)$ 对应的二进制码 1101 进行模 $2$ 除法,得到余数为 010,说明第 $2$ 位出错

【纠错编码】

概述

纠错编码是利用前向纠错 FEC 的方式进行差错控制,在接收端检测出错后,可以确定二进制编码的出错位置,并加以纠正

具体来说,检测编码采用了冗余编码技术,核心思想是在信息位发送前,先按一定关系附加一定的冗余校验位,构成一个符合某一规则的校验码后再发送,在接收方收到校验码后,根据一定规则推测发送方实际送出的应该是什么样的编码

最常见的纠错编码是海明码

纠错理论

对于任意两个合法码字之间最少变化的二进制位数,称为码距,简单来说,就是两个长度相同的编码对应位不同的个数

例如:11001101 间的码距为 $1$,10010010 间的码距为 $3$

对于码距不小于 $2$ 的数据校验码,开始具有检错能力,码距越大,检错、纠错的能力就越强,且检错能力总是大于等于纠错能力

设可检测错误的位数为 $D$,可纠正错误的位数为 $C$,编码的码距为 $L$,那么有:

海明码

海明码纠错 $d$ 位需要码距为 $2d+1$ 的编码方案,检错 $d$ 位需要码距为 $d+1$ 的编码方案

对于 $m$ 位信息位,将插入 $r$ 位校验位组成 $n=m+r$ 位码字,要求满足以下关系:

下面,以 $n=4$ 的数据编码 $D_4D_3D_2D_1=1010$ 为例,说明发送端计算海明码与接收端检验海明码的过程

对于发送端,会将码字的位编号,规定校验位 $P_i$ 位于数据位位号 $2^{i-1}$ 的位置上,对于 $4$ 位数据编码 $D_4D_3D_2D_1$,将会插入 $3$ 位校验码 $P_3P_2P_1$,从而实际传输 $7$ 位码字 $H_7H_6H_5H_4H_3H_2H_1$

之后,将每个数据位用多个校验位进行校验,被校验数据位的海明位号等于校验该数据位的将由改写各校验位海明位号,进行分组

对于校验位 $P_i$,其值为该校验位校验的所有数据位求异或

由此,可得到 1010 所对应的海明码为

其中,带有下划线的为校验位,其余为原信息位

对于接收端,会将每个校验位 $P_i$ 与参与形成该校验位的信息位求异或

若求得的 $r$ 个校验位值均为 0,说明没有出现错误,否则说明出错,且这个 $r$ 位二进制数对应的十进制数就是错误位的位号,将其取反,即可进行纠错

感谢您对我的支持,让我继续努力分享有用的技术与知识点!