比特差错:比特在传输过程中可能会产生差错,1可能会变成0,0可能会变成1。
通常利用编码技术进行差错控制:自动重传请求ARQ和前向纠错FEC
1.检错编码
都采用冗余编码技术,核心思想:在有效数据被发送前,先按某种关系附加一定的冗余位,构成一个符合某一规则的码字后再发送。(看接收端收到的码字是否符合规则来判断)
1)奇偶校验码
奇校验码和偶校验码的统称,是一种最基本的检错码。由n-1位信息元和1位校验元组成。
奇校验码:n位码字中“1”的个数为奇数偶校验码:n位码字中“1”的个数为偶数
2)循环冗余码
又称多项式码。任何一个由二进制数位串组成的代码都可以与一个只含有0和1两个系数的多项式建立一一对应的关系。
给定一个m bit的帧或报文,发送器生成一个r bit的序列,称为帧检验序列(FCS)。
这样所形成的帧将由m+r比特组成。发送方和接收方事先商定一个多项式G(x)(最高最低位必须是1),使这个带校验码的帧正好能被预先确定的多项式G(x)整除。
假设有1个帧有m位,其对应的多项式为M(x),则计算冗余码的步骤如下:
1)加0。假设G(x)的阶为r,在帧的低位端加上r个0。
2)模2除。利用模2除法,用G(x)对应的数据串去除 1)中计算出的数据串,得到的余数即为冗余码。利用循环冗余码的检错技术,数据链路层做到了对帧的无差错接收(错的都被丢弃)。
2.纠错编码
最常见的是海明码。
海明码的实现原理:在有效信息位中加入几个校验位形成海明码,并把海明码的每个二进制分配到几个奇偶校验组中。当某一位出错后,就会引起有关的几个校验位的值发生变化,这不但可以发现错位,而且能指出错位的位置,为自动纠错提供依据。
步骤:
确定海明码的位数:n+k≤ 2k−12^{k}-1 (n为有效信息的位数,k为校验位的位数)确定校验位的分布: PiP_{i} 在海明位号上2i−1上2^{i-1}上分组以形成校验关系:每个数据位用多个校验位进行校验,但需要满足条件——被校验数据位的海明位号等于校验该数据位的各校验海明位号之和。另外,校验位不需要再被校验。校验位取值:校验位PiP_{i}的值为第i组(由该校验位校验的数据位)所有位求异或。校验原理:利用校验位和参加形成该校验位的信息位进行奇偶校验检查,构成k个方程:
S1=P1⊕D1⊕D2⊕D4
S2=P2⊕D1⊕D3⊕D4
S3=P3⊕D2⊕D3⊕D4
若S1S2S3的值为“000”则无错;否则就是有错,且S1S2S3的值就是错误位的位号。