Thursday, August 7, 2008

第3章: 数据链路层习题讲解

停止等待ARQ

例:信道速率为4Kb/s,采用停止等待协议。传播时延Tp=20ms。确认帧长度和处理时间均可忽略。问帧长为多少才能使信道利用率达到至少50%

解:信道利用率1/2=Tf/TT=Tf/(Tf+2Tp)

Tf=2Tp=2*20ms=40ms

则帧长Lf=Tf*C=40ms*4Kb/s=160b


选择重传ARQ

例:使用一个64Kb/s的无错卫星通道发送512字节的数据帧(在一个方向上),而在另一个方向上返回很短的确认帧。对于窗口大小为1715127的最大速率是多少?

解:发送时延Tf512*8b/64000b/s=64ms ##CONTINUE##

传播时延Tp270ms 卫星的传播时延

周期TT= Tf+2Tp=64+2*270=604ms

窗口大小(604ms*64Kb/s)/(8b*512)≈9帧才能保持通道不空。

对于窗口值1512*8b/0.604s=6781b/s=6.8Kb/s

对于窗口值76781*7=47467b/s=47.5Kb/s

对于窗口值超过9帧,速率到达完全速率64Kb/s


1.为了进行差错控制,必须对传送的数据帧进行校验。在局域网中广泛使用的校验方法是 _____校验。CRC-16标准规定的生成多项式为g(x)=x16+x15+x2+1,它产生的校验码是_____位,接收端发现错误后采取的措施是_____。如果CRC的生成多项式为g(x)=x4+x+1,信息码字为10110,则计算出的CRC校验码是_____。要检查出d位错,码字之间的海明距离最小值应为_____

A.奇偶(ParityB.海明(HammingC.格雷(GrayD.循环冗余(Cyclic Redundancy

A.2 B.4 C. 16 D.32

A.自动纠错 B.报告上层协议 C.自动请求重发 D.重新生成原始数据

A.0100 B.1010 C.0111 D.1111

A.d B.d+1 C.d-1 D.2d+1

分析:奇偶检验是串口通信中最常使用的是数据校验的方法。一个码距为1的编码系统加上一位就校验码后,码距就成为2。产生奇偶校验时将信息数据的各位进行模二加法,直接使用这个加法的结果作为校验码的称为奇校验。把这个加法值取反后作为校验码的称为偶校验。简单来说,奇校验的规则是:信息数据中各位中1的个数为奇数,校验码为1,否则校验码为0。偶校验则相反。

格雷码(又称循环码或反射码),为解决采用脉码调制方式PCM的 无线电通信中,由于线路中的脉冲干扰严重而造成误码率太多这一严重问题而提出的,格雷码的编码规则是使任何两个相邻代码只有一个二进制位的状态不同,其余 三个二进制位必须有相同状态。它的好处在于从某一编码变到下一个编码时只有一位状态发生变化,有利于得到更好的译码波形,或者在从模拟到数字、从数字到模 拟的转换电路中得到更好的运行结果。

CRC校验码的编码过程。由于CRC-32CRC-16CCITTCRC-4的编码过程基本一致,只有位数和生成多项式不一样。为了叙述简单,下面用一个CRC-4编码的例子来说明CRC的编码过程。设待发送的数据t(x)12位的二进制数据100100011100CRC-4的生成多项式为g(x)= x4+x+1,阶数r4,即10011。首先在t(x)的末尾添加40构成,数据块就成了1001000111000000。然后用g(x)去除,不用管商是多少,只需要求得余数y(x)

目前常用的差错控制技术有一下3种。

1.ARQ: 反馈纠错,是在发送端采用某种能发现一定程度传输差错的简单编码方法对所传信息进行编码,加入少量监督码元,在接受端则根据编码规则对收到的编码信号进行 检查,一旦检测出有错码时,即向发信端发出询问的信号,要求重发。发信端收到询问信号时,立即重发已发生传输差错的那部分发信息,直到正确收到为止。

2.FEC:前向纠错,发送端采用某种在解码时能纠正一定程度传输差错的较复杂的编码方法,使接受端在收到信码中不仅能发现错码,还能够纠正错码。设备比较复杂。

3.ARQ/FEC:混合纠错,少量纠错在接受端自动纠正,差错较严重,超出自行纠正能力时,就向发送端发出询问信号,要求重发。

在分组编码中两个码组对应位置上取值不同(10)的位数,称为码组的距离,简称码距,又称海明距离,通常用d表示。例如:000101之间码距d=2000111之间码距d=3。对于(nk)码,允许使用码组为2k个,各码组之间距离最小值称为最小码距,通常用d0表示。

最小码距d0的大小与信道编码的检纠错能力密切相关。分组编码最小码距与检纠错能力的关系有以下三条结论。

1.在一个码组内为了检测e个误码,要求最小码距应满足:d0≥e+1

2.在一个码组内为了纠正t个误码,要求最小码距应满足:d0≥2t+1

3.在一个码组内为了纠正t个误码,同时能检测e个误码(e>t,要求最小码距应满足:d0≥e+t+1

题中两个码字的海明距离为d,则需要d个单比特就可以把一个码字转换成另一个码字;为了检查出d个错(单比特错),需要使用海明距离为d+1的编码;为了纠正d个错,需要使用海明距离为2d+1的编码。

答案:D C C D B


2.使用海明码进行前向纠错,如果冗余为4位,哪么信息位最多可以用到_____位,假定码字位a6 a5 a4 a3 a2 a1 a0 ,并且有下面的监督关系式:

S2= a2 +a4 +a5 +a6

S1= a1 +a3 +a5 +a6

S0= a0 +a3 +a4 +a6

S2 S1 S0=110,则表示出错位是_____

A.6 B.8 C.11 D.16

A. a3 B. a4 C. a5 D. a6

分析:本题考查海明编码知识。

海明码属于线性分组编码方式,大多数分组码属于线性编码,其基本原理是,是信息码元与监督码元通过线性方程式联系起来。线性码建立在代数学群论的基础上,各许用码组的集合构成代数学中的群,故又称为群码。注意以下两个问题。

1.校验和监督关系式:r各监督关系式能只是一个错码的2r-1个可能位置。一般情况下,若码长为n,信息码为k,则监督码数r=r-k。若希望用r个监督码构造出r个监督关系式来指示一位错码的n种可能位置,则要求:

2r-1≥n2r-1≥k+r+1

2.海明码的编码效率:m=1-r/n,当n很大时,效率是很高的。

题中当r=4,则k最大为11

在海明码这些多个校验位中的每一位都对不同的信息数据位进行奇偶校验,通过合理的安排每个校验位对原始数据进行的校验的位组合,可以达到发现错误,校正错误的目的。

S2 S1 S0=110,得k=3。码字位a6 a5 a4 a3 a2 a1 a0,所以m=4

校验方程是指示每个校验位对相应的信息位进行校验的等式。一般情况下,校验码会被插入到数据的1248,…,2n位置,那么,在数据生成时,按照提供的海明码校验方程计算出b1,b2,b4,…bn,可知S0= a0S1= a1S2= a3,推出错码位置关系如下表所示:

错码位置关系表

S2 S1 S0

000

001

010

100

011

101

110

111

错码位置

无错

a0

a1

a2

a3

a4

a5

a6

答案:C C


3.码是一些码字组成的集合。一对码字之间的海明距离是_____,一个码的海明距离是所有不同码字的海明距离的_____。如果要检查出d位错,哪么码的海明距离是_____。如果信息长度为5位,要求纠正1位错,按照海明编码,需要增加的校验位是_____位。以太网中使用的校验码标准是_____

A.码字之间不同的位数 B.两个码字之间相同的位数

C.两个码字的校验和之和 D.两个码字的校验和之差

A.平均值 B.最大值 C.最小值 D.任意值

A.d-1 B.d+1 C.2d-1 D.2d+1

A.3 B.4 C.5 D.6

A.CRC-12 B.CRC-CCITT C.CRC-16 D.CRC-32

码距是指两个码字逐位比较,其不同字符的个数就是两个码字的距离。所以一个码制的距离定义为:在这个编码制中各个码字之间的最小距离称位码距。例如4位二进制数中16个代码的码距为1,若合法的增大码距,可以提高发现错误的能力。D个单比特错就可以把一个码字转换成另一个码字。为了检查出d个错误,需要使用海明距离为2d+1的编码。

对于信息位长度位k,监督码长度为r,则要指示一位错的nn=k+r)个可能位置,即纠正一位错,则必须满足如下关系:2r-1≥n=k+r。故当信息位为5时,满足2r-1≥k+r=5+r,则r=4

在以太网中是使用CRC来校验数据的传输是否出错的,通常使用CRC-32生成多项式作为标准校验式,并且在以太网中,CRC不校验前同步码和帧定界符。如果不记得以太网是使用什么校验时,但是记得以太网的帧格式的最后一个域FCS4个字节,哪么也可以知道其检验码为CRC-32

要注意的是CRC-CCITT的表达式也是16位,但是和CRC-16是不同的校验式。其中4个多项式已成为国际标准:

CRC-12=x12+x11+x3+x2+x+1

CRC-16=x16+x15+x2+1

CRC-CCITT=x16+x12+x5+1

CRC-32= x32+x26+x23+x22+x16+x12+x11+x10+ x8+x7+x5+ x4+x2+x+1

答案:A C B B D

No comments: