第三章 数据链路层 (1)
3.1 差错检测与校正
3.2 数据链路层的功能
什么是差错？
在通信中，由于线路本身电气特性的随机噪声、信号的衰减和畸变、相邻线路的窜扰或外界因素的影响，接收端收到的二进制数位（码元）和发送端实际发送的数据不一致。
差错检测与校正：把差错控制在允许的范围内。
差错检测与校正
有两种不同的差错：
随机差错：随机热噪声
随机热噪声是信道固有的、持续存在的
码元的差错是独立的，和前后的码元无关
随机错的概率很低，物理信道的设计保证相当大的信噪比
突发差错：冲击噪声
外界的因素，持续时间短，突发性
传输中产生差错的主要原因
突发长度：突发差错发生的第一个码元到有错的最后一个码元间所有码元的个数。比如 4800bps信道上的 10ms的冲击噪声的突发长度为 48比特传输差错的特性（ 1）
误码率：衡量物理信道的质量
差错控制编码：信息位 (k)＋冗余位 (r)
检错码和纠错码
检错码：自动发现差错
纠错码：不仅能发现差错而且能够自动纠正
编码效率 R：码字中信息位所占的比例
R=k/(k+r)
漏检率：信息位出错但是接收者无法了解到的概率传输差错的特性（ 2）
的负若干次方来表示常常用接收的总码元数发生差错的码元数 10?eP
差错控制的方式
差错控制,ARQ和 FEC
ARQ,Automatic Request for Repeat
接收方检测错误，通知发送方重传
双向信道，发送方缓存发送的数据
FEC,Forward Error Correction
接收方不仅可以检测错误，而且知道错误的位置，
从而改正错误
采用纠错码，无需反向信道，无需重发
ARQ和 FEC结合常用的简单差错控制编码
奇偶校验码：增加冗余位使得码字中 ‘ 1’的个数为奇数或者偶数，检错码
垂直奇偶校验
水平奇偶校验
水平垂直奇偶校验
垂直奇偶校验：
发送的信息块分成定长为 p位的若干段（一列）。
每段增加一个（奇偶校验）冗余位 ri,
I 11 I 12 ··· I 1q
I 21 I 22 ··· I 2q
2
I p1 I p2 ··· I pq
···
···
···
r 1 r 2 ··· r q 冗余位信息位发送顺序垂直奇偶校验
q1,2,.,,,i 21 piiii IIIr?偶校验：
q1,2,.,,,i 121 piiii IIIr?奇校验：
奇偶校验（ 1）
垂直奇偶校验
编码效率：
能力：
检测出每列（段）中所有奇数（ 1,3… ）个错
突发错误的漏检率为 50%!!
在发送和接收的过程中进行编解码
水平奇偶校验：降低突发错误的漏检率
对各个信息段的相应位横向进行编码
1 p
pR
奇偶校验（ 2）
水平奇偶校验
编码效率：
能力：
各段同一位上的奇数个错
长度小于等于 p的突发差错
编码和检测相比垂直校验而言实现要复杂一些
I 11 I 12 ··· I 1q
I 21 I 22 ··· I 2q
2
I p1 I p2 ··· I pq
···
···
···
r 1
r 2
r p
冗余位 信息位发送顺序水平奇偶校验
···
p1,2,.,,,i 21 iqiii IIIr?偶校验：
p1,2,.,,,i 121 iqiii IIIr?奇校验：
1 q
qR
奇偶校验（ 3）
水平垂直奇偶校验
编码效率：
I 11 I 12 ··· I 1q
I 21 I 22 ··· I 2q
2
I p1 I p2 ··· I pq
···
···
···
r 1,q + 1
r 2 q + 1
r p q + 1
冗余位信息位发送顺序水平奇偶校验
···
r p + 1,1 r p + 1,2 ··· r p + 1,q r p + 1,q + 1
1,1,21,1
,12,11,11,1
21,1
211,
q1,2,.,,,j
p1,2,.,,,i
qpqq
qpppqp
pjjjjp
iqiiqi
rrr
rrrr
IIIr
IIIr
偶校验：
)1)(1( qp
pqR
奇偶校验（ 4）
水平垂直奇偶校验能力
检测出：所有 3位或 3位以下的错误、奇数位错
突发长度小于等于 p+1的突发差错
很大一部分偶数位错：差错分布以致于某一行或者某一列有奇数个差错
部分纠错功能：
可以纠正 1比特错
信息块中恰好只有某一行和某一列有奇数位错时，可确定为该行和该列的交叉处
纵向、横向、纵横奇偶校验定比码
基本思想：
码字中有相同数目的 ‘ 1’
N中取 m码,n位码字中 ‘ 1’的个数为 m
两种定比码：
国际无线电报中的 7中取 3码：
中国的传输汉字的电报码,5中取 3码
编码效率：
检测出全部奇数位错以及部分偶数位错
只有有限个码字,信源为随机二进制数字序列时会带来问题
3537?C
1035?C
nR C
m
n2log?
正反码（ 1）
基本思想：
冗余位的个数与信息位的个数 k相同，信息位中有奇数个 ‘ 1’时，冗余位和信息位相同，否则相反
接收端的校验方法（以 k=5为例）：
K位的合成码组：接收码字中信息位和冗余位按位半加
校验码组：如果接收码字中信息位有奇数个 ‘ 1’时，
等于合成码组，否则为合成码组的反码
根据校验码查看下表，判断是否有差错，并纠错正反码（ 2）
举例：
1、发送 01011，发送码字为 0101101011
2、接收码字为 0101101011，校验码字 00000
3、接收 1101101011，校验码字 01111
4、接收 1101111011，校验码字 11111
编码效率为 50%
纠正一位错，检测全部 2位错和大部分 2位以上的错校验码组 差错情况全,0”,00000 无差错
4个,1”,1个,0” 信息位中一位出错,其位置对应于校验码组中 0对应的位置
4个,0”,1个,1” 冗余位中一位出错,其位置对应于校验码组中 1对应的位置其他情况 差错在两位或两位以上海明码（ 1）
海明码是一种纠错码,1位错
回顾奇偶校验：
一个 k=n-1的信息位 an-1an-2 … a1加上一个偶校验位 a0（ an-1an-2 … a1a0）
接收端：利用监督关系式计算校正因子 S
S=0和 1，分别区分无错和有错的情况
0121 aaaaS nn
海明码（ 2）
信息位 k位，增加冗余位 r，码字 n=k+r。用 r个监督关系式产生 r个校正因子来区分无错和 n位的码字中一位错，要求：
假设信息位为 k=4，则 r?3。取 r=3,n=7，即
a6a5a4a3 +a2a1a0。 冗余位 a2,a1和 a0是信息位中的某几位半加得到。
三个监督关系式和校正因子 S2S1S0,某个冗余位
a2a1a0与编码时采用的信息位半加
S2S1S0区分无错和 7位码字中某一位有错的情况
12 rkr
海明码（ 3）
由表可以得到监督关系式：
编码时，冗余位的取值应该满足校正因子为 0
接收时，根据校正因子查表判断
S2S1S0 000 001 010 100 011 101 110 111
错码位置 无错 a0 a1 a2 a3 a4 a5 a6
64300
65311
65422
aaaaS
aaaaS
aaaaS
6430
6531
6542
aaaa
aaaa
aaaa
海明码（ 4）
例子中海明码的编码效率为 4/7
k=7，冗余位最少为 4，编码效率为 7/11
纠正突发错误：
连续 P个码字排成一个矩阵，每行一个码字，
从而可以纠正突发长度?P的突发错
0 0 0 1 0 1 1
1 0 1 0 0 1 0
1 0 1 1 0 0 1
0 1 0 0 1 1 0
0 1 0 0 1 1 0
1 1 0 1 0 1 0
1 1 1 1 1 1 1
0 1 1 0 0 1 1
信息位 冗余位发送顺序
P 个码字组成矩阵每行一个码字循环冗余码 CRC（ 1）
计算机网络中使用最为广泛的检错码：
纠错码的编码效率较低，差错控制经常采用检错码＋ ARQ
CRC又称为多项式码：
二进制比特串和一个只有 0和 1两个系数的多项式一一对应
k位信息位对应于一个 (k-1)次多项式 K(x)
r位冗余位对应于一个 (r-1)次多项式 R(x)
信息位＋冗余位（ k+r）对应于一个 (n-1)次多项式
T(x)=xrK(x)+R(x)
编码的基本思想是找一个生成多项式 G(x)（ r次多项式，最高位的系数为 1）,xrK(x)除以 G(x)得到的余式为冗余位 R(x)
接收方的码字除以 G(x)，如果余式为 0表示无错。
循环冗余码 CRC（ 2）
多项式运算：加减乘除都是模 2的，即没有进位和借位。
0 1 1 0 0 0 0 1
1 1 0 1 0 0 1 0
1 0 1 1 0 0 1 1
0 1 1 0 0 0 0 1
1 1 0 1 0 0 1 0
1 0 1 1 0 0 1 1
1 0 0 1 1 1 1
1 1 0 1
1 0 1 1 1
01 0 1 0 0 0 1 0 0 01 0 1 1 1
循环冗余码 CRC（ 3）
如果传输过程中出现差错：差错模式 E(x)＝发送码字和接收码字的半加，其中 1的位置对应变化了信息位的位置。
若 E(x)能被 G(x)整除，则不能检测这样的错误
E ( x ) /G ( x )E ( x ) /G ( x )T ( x ) /G ( x )E ( x ) ) /G ( x )( T ( x )
0)(/)()()()()()()()()()(
:
)()(/)()()()()(
有错时：
，即无错时
，记为
xGxTxQxGxRxRxQxGxRxKxxT
xRxGxKxxRxQxGxKx
r
rr
循环冗余码 CRC（ 4）
1、若 G(x)含有 (x+1)的因子，则能检测出所有奇数位错：
2、若 G(x)中不含 x的因子，即 G(x)中的常数项为 1，则能检测出所有突发长度?r的突发错：
3、若 G(x)中不含 x的因子，并且对任何 0<e?n-1，除不尽 xe+1，则能检测出所有的双错：
，矛盾表示奇数位错，而
，则若
1)1()(
0)1(
)()()1()()()(0)(/)(
)()1()(
`
`
ExE
E
xQxGxxQxGxExGxE
xGxxG
10)1()( rjixxxxxEr jijji,其中的差错多项式突发长度
10)1()( njixxxxxE jijji,其中双错对应的差错多项式循环冗余码 CRC（ 5）
4、若 G(x)中不含 x的因子，则对突发长度为 r+1的突发错误的漏检率为 2-(r-1)
5、若 G(x)中不含 x的因子，则对突发长度 b(b>r+1)的突发错误的漏检率为 2-r
11 2/12)1(
)1()(0)(/)(
)1()1()(
,1r
rrr
r
rjjijji
xr
xxGxGxE
xxxxxxxE
不出，所以漏检率个，其中只有一个检测有次多项式
，的唯一可能是为多项式的突发错误对应的差错突发长度为
rbrb
rb
b
bjjijji
xxQ
rbxQ
xxQxGxGxE
xxxxxxxE
b
22/2
1)(
1)(
)1()()(0)(/)(
)1()1()(
,1r
22
1
1
1
漏检率次多项式，即为
，则为多项式的突发错误对应的差错突发长度为
循环冗余码 CRC（ 6）
结论：若适当选取 r次多项式 G(x)，满足：
含有 x+1因子
常数项不为 0：不含 x的因子
周期大于等于 n：性质 3
检测出所有双错、奇数位错、突发长度小于等于 r的突发错
突发长度为 r+1的突发错误的漏检率为 2-(r-1),对突发长度
b(b>r+1)的突发错误的漏检率为 2-r
常用的 CRC多项式：
1
116
112
51216
21516
231112
xxxC C I T TC R C
xxxC R C
xxxxxC R C
循环冗余码 CRC（ 7）
除以 G(x)的运算可以通过移位寄存器和半加器来实现：
1)( 12211 xgxgxgxxG rrr?
R 1 R 4 R 3 R 2 R 0
输入
=1 比特移位寄存器
= 半加器
G ( x ) = x
5
+ x
4
+ x
2
+1
循环冗余码 CRC（ 8）
开始移位寄存器都为 ‘ 0’
信息位从高到低逐位输入，经过 k次移位后，
移位寄存器中得到的是 r位冗余位
当 R4移出的为 0时，下一个输入到来时相当于移位过程
当 R4移出的为 1时，下一个输入到来时相当于第 2、
4,6（输入）比特与 1半加。
接收端检验的过程也是除以 G(x)的过程，最后增加一个,与,门来判别余式是否为全 0。
数据链路层的功能（ 1）
数据链路层在物理层提供的服务的基础上向网络层提供服务
把网络层来的数据沿一条链路（ link）传递给相邻的节点
数据链路层提供的服务：
1、成帧（ Framing）、帧同步
比特流在传输过程中可能会出错
只需重传出错帧：帧中包含检验和字段
如何确定帧的边界？
数据链路层的功能（ 2）
1、成帧（ Framing）
字节计数法：特殊字符表示帧的开始，一个字段来给出帧的长度
字符填充的首尾定界符：特殊字符表示帧的开始，
信息位中的特殊字符前加一个转义字符 DLE
比特填充的首尾标志方法：特定的比特模式标志帧的起始，信息位中出线比特模式时，进行比特填充
违例编码法：采用不可能出线在信息位中的比特编码作为帧的起始边界。
曼彻斯特编码中电平的跳变表示 1（高 ->低）和 0（低 ->高）
高高和低低电平是违例编码数据链路层的功能（ 3）
2、链路访问（ link-access）
点到点的链路相对来说要简单些,PPP
多路访问：多个节点共享一条广播链路
硬件地址：标识给哪一个节点
3、差错检测和差错校正
4、可靠递交（差错控制）
确认和重传
超时和序号
5、流量控制：接收方的能力有限制
6、半双工和全双工：
习题
3.3
3.4
3.6
3.1 差错检测与校正
3.2 数据链路层的功能
什么是差错？
在通信中，由于线路本身电气特性的随机噪声、信号的衰减和畸变、相邻线路的窜扰或外界因素的影响，接收端收到的二进制数位（码元）和发送端实际发送的数据不一致。
差错检测与校正：把差错控制在允许的范围内。
差错检测与校正
有两种不同的差错：
随机差错：随机热噪声
随机热噪声是信道固有的、持续存在的
码元的差错是独立的，和前后的码元无关
随机错的概率很低，物理信道的设计保证相当大的信噪比
突发差错：冲击噪声
外界的因素，持续时间短，突发性
传输中产生差错的主要原因
突发长度：突发差错发生的第一个码元到有错的最后一个码元间所有码元的个数。比如 4800bps信道上的 10ms的冲击噪声的突发长度为 48比特传输差错的特性（ 1）
误码率：衡量物理信道的质量
差错控制编码：信息位 (k)＋冗余位 (r)
检错码和纠错码
检错码：自动发现差错
纠错码：不仅能发现差错而且能够自动纠正
编码效率 R：码字中信息位所占的比例
R=k/(k+r)
漏检率：信息位出错但是接收者无法了解到的概率传输差错的特性（ 2）
的负若干次方来表示常常用接收的总码元数发生差错的码元数 10?eP
差错控制的方式
差错控制,ARQ和 FEC
ARQ,Automatic Request for Repeat
接收方检测错误，通知发送方重传
双向信道，发送方缓存发送的数据
FEC,Forward Error Correction
接收方不仅可以检测错误，而且知道错误的位置，
从而改正错误
采用纠错码，无需反向信道，无需重发
ARQ和 FEC结合常用的简单差错控制编码
奇偶校验码：增加冗余位使得码字中 ‘ 1’的个数为奇数或者偶数，检错码
垂直奇偶校验
水平奇偶校验
水平垂直奇偶校验
垂直奇偶校验：
发送的信息块分成定长为 p位的若干段（一列）。
每段增加一个（奇偶校验）冗余位 ri,
I 11 I 12 ··· I 1q
I 21 I 22 ··· I 2q
2
I p1 I p2 ··· I pq
···
···
···
r 1 r 2 ··· r q 冗余位信息位发送顺序垂直奇偶校验
q1,2,.,,,i 21 piiii IIIr?偶校验：
q1,2,.,,,i 121 piiii IIIr?奇校验：
奇偶校验（ 1）
垂直奇偶校验
编码效率：
能力：
检测出每列（段）中所有奇数（ 1,3… ）个错
突发错误的漏检率为 50%!!
在发送和接收的过程中进行编解码
水平奇偶校验：降低突发错误的漏检率
对各个信息段的相应位横向进行编码
1 p
pR
奇偶校验（ 2）
水平奇偶校验
编码效率：
能力：
各段同一位上的奇数个错
长度小于等于 p的突发差错
编码和检测相比垂直校验而言实现要复杂一些
I 11 I 12 ··· I 1q
I 21 I 22 ··· I 2q
2
I p1 I p2 ··· I pq
···
···
···
r 1
r 2
r p
冗余位 信息位发送顺序水平奇偶校验
···
p1,2,.,,,i 21 iqiii IIIr?偶校验：
p1,2,.,,,i 121 iqiii IIIr?奇校验：
1 q
qR
奇偶校验（ 3）
水平垂直奇偶校验
编码效率：
I 11 I 12 ··· I 1q
I 21 I 22 ··· I 2q
2
I p1 I p2 ··· I pq
···
···
···
r 1,q + 1
r 2 q + 1
r p q + 1
冗余位信息位发送顺序水平奇偶校验
···
r p + 1,1 r p + 1,2 ··· r p + 1,q r p + 1,q + 1
1,1,21,1
,12,11,11,1
21,1
211,
q1,2,.,,,j
p1,2,.,,,i
qpqq
qpppqp
pjjjjp
iqiiqi
rrr
rrrr
IIIr
IIIr
偶校验：
)1)(1( qp
pqR
奇偶校验（ 4）
水平垂直奇偶校验能力
检测出：所有 3位或 3位以下的错误、奇数位错
突发长度小于等于 p+1的突发差错
很大一部分偶数位错：差错分布以致于某一行或者某一列有奇数个差错
部分纠错功能：
可以纠正 1比特错
信息块中恰好只有某一行和某一列有奇数位错时，可确定为该行和该列的交叉处
纵向、横向、纵横奇偶校验定比码
基本思想：
码字中有相同数目的 ‘ 1’
N中取 m码,n位码字中 ‘ 1’的个数为 m
两种定比码：
国际无线电报中的 7中取 3码：
中国的传输汉字的电报码,5中取 3码
编码效率：
检测出全部奇数位错以及部分偶数位错
只有有限个码字,信源为随机二进制数字序列时会带来问题
3537?C
1035?C
nR C
m
n2log?
正反码（ 1）
基本思想：
冗余位的个数与信息位的个数 k相同，信息位中有奇数个 ‘ 1’时，冗余位和信息位相同，否则相反
接收端的校验方法（以 k=5为例）：
K位的合成码组：接收码字中信息位和冗余位按位半加
校验码组：如果接收码字中信息位有奇数个 ‘ 1’时，
等于合成码组，否则为合成码组的反码
根据校验码查看下表，判断是否有差错，并纠错正反码（ 2）
举例：
1、发送 01011，发送码字为 0101101011
2、接收码字为 0101101011，校验码字 00000
3、接收 1101101011，校验码字 01111
4、接收 1101111011，校验码字 11111
编码效率为 50%
纠正一位错，检测全部 2位错和大部分 2位以上的错校验码组 差错情况全,0”,00000 无差错
4个,1”,1个,0” 信息位中一位出错,其位置对应于校验码组中 0对应的位置
4个,0”,1个,1” 冗余位中一位出错,其位置对应于校验码组中 1对应的位置其他情况 差错在两位或两位以上海明码（ 1）
海明码是一种纠错码,1位错
回顾奇偶校验：
一个 k=n-1的信息位 an-1an-2 … a1加上一个偶校验位 a0（ an-1an-2 … a1a0）
接收端：利用监督关系式计算校正因子 S
S=0和 1，分别区分无错和有错的情况
0121 aaaaS nn
海明码（ 2）
信息位 k位，增加冗余位 r，码字 n=k+r。用 r个监督关系式产生 r个校正因子来区分无错和 n位的码字中一位错，要求：
假设信息位为 k=4，则 r?3。取 r=3,n=7，即
a6a5a4a3 +a2a1a0。 冗余位 a2,a1和 a0是信息位中的某几位半加得到。
三个监督关系式和校正因子 S2S1S0,某个冗余位
a2a1a0与编码时采用的信息位半加
S2S1S0区分无错和 7位码字中某一位有错的情况
12 rkr
海明码（ 3）
由表可以得到监督关系式：
编码时，冗余位的取值应该满足校正因子为 0
接收时，根据校正因子查表判断
S2S1S0 000 001 010 100 011 101 110 111
错码位置 无错 a0 a1 a2 a3 a4 a5 a6
64300
65311
65422
aaaaS
aaaaS
aaaaS
6430
6531
6542
aaaa
aaaa
aaaa
海明码（ 4）
例子中海明码的编码效率为 4/7
k=7，冗余位最少为 4，编码效率为 7/11
纠正突发错误：
连续 P个码字排成一个矩阵，每行一个码字，
从而可以纠正突发长度?P的突发错
0 0 0 1 0 1 1
1 0 1 0 0 1 0
1 0 1 1 0 0 1
0 1 0 0 1 1 0
0 1 0 0 1 1 0
1 1 0 1 0 1 0
1 1 1 1 1 1 1
0 1 1 0 0 1 1
信息位 冗余位发送顺序
P 个码字组成矩阵每行一个码字循环冗余码 CRC（ 1）
计算机网络中使用最为广泛的检错码：
纠错码的编码效率较低，差错控制经常采用检错码＋ ARQ
CRC又称为多项式码：
二进制比特串和一个只有 0和 1两个系数的多项式一一对应
k位信息位对应于一个 (k-1)次多项式 K(x)
r位冗余位对应于一个 (r-1)次多项式 R(x)
信息位＋冗余位（ k+r）对应于一个 (n-1)次多项式
T(x)=xrK(x)+R(x)
编码的基本思想是找一个生成多项式 G(x)（ r次多项式，最高位的系数为 1）,xrK(x)除以 G(x)得到的余式为冗余位 R(x)
接收方的码字除以 G(x)，如果余式为 0表示无错。
循环冗余码 CRC（ 2）
多项式运算：加减乘除都是模 2的，即没有进位和借位。
0 1 1 0 0 0 0 1
1 1 0 1 0 0 1 0
1 0 1 1 0 0 1 1
0 1 1 0 0 0 0 1
1 1 0 1 0 0 1 0
1 0 1 1 0 0 1 1
1 0 0 1 1 1 1
1 1 0 1
1 0 1 1 1
01 0 1 0 0 0 1 0 0 01 0 1 1 1
循环冗余码 CRC（ 3）
如果传输过程中出现差错：差错模式 E(x)＝发送码字和接收码字的半加，其中 1的位置对应变化了信息位的位置。
若 E(x)能被 G(x)整除，则不能检测这样的错误
E ( x ) /G ( x )E ( x ) /G ( x )T ( x ) /G ( x )E ( x ) ) /G ( x )( T ( x )
0)(/)()()()()()()()()()(
:
)()(/)()()()()(
有错时：
，即无错时
，记为
xGxTxQxGxRxRxQxGxRxKxxT
xRxGxKxxRxQxGxKx
r
rr
循环冗余码 CRC（ 4）
1、若 G(x)含有 (x+1)的因子，则能检测出所有奇数位错：
2、若 G(x)中不含 x的因子，即 G(x)中的常数项为 1，则能检测出所有突发长度?r的突发错：
3、若 G(x)中不含 x的因子，并且对任何 0<e?n-1，除不尽 xe+1，则能检测出所有的双错：
，矛盾表示奇数位错，而
，则若
1)1()(
0)1(
)()()1()()()(0)(/)(
)()1()(
`
`
ExE
E
xQxGxxQxGxExGxE
xGxxG
10)1()( rjixxxxxEr jijji,其中的差错多项式突发长度
10)1()( njixxxxxE jijji,其中双错对应的差错多项式循环冗余码 CRC（ 5）
4、若 G(x)中不含 x的因子，则对突发长度为 r+1的突发错误的漏检率为 2-(r-1)
5、若 G(x)中不含 x的因子，则对突发长度 b(b>r+1)的突发错误的漏检率为 2-r
11 2/12)1(
)1()(0)(/)(
)1()1()(
,1r
rrr
r
rjjijji
xr
xxGxGxE
xxxxxxxE
不出，所以漏检率个，其中只有一个检测有次多项式
，的唯一可能是为多项式的突发错误对应的差错突发长度为
rbrb
rb
b
bjjijji
xxQ
rbxQ
xxQxGxGxE
xxxxxxxE
b
22/2
1)(
1)(
)1()()(0)(/)(
)1()1()(
,1r
22
1
1
1
漏检率次多项式，即为
，则为多项式的突发错误对应的差错突发长度为
循环冗余码 CRC（ 6）
结论：若适当选取 r次多项式 G(x)，满足：
含有 x+1因子
常数项不为 0：不含 x的因子
周期大于等于 n：性质 3
检测出所有双错、奇数位错、突发长度小于等于 r的突发错
突发长度为 r+1的突发错误的漏检率为 2-(r-1),对突发长度
b(b>r+1)的突发错误的漏检率为 2-r
常用的 CRC多项式：
1
116
112
51216
21516
231112
xxxC C I T TC R C
xxxC R C
xxxxxC R C
循环冗余码 CRC（ 7）
除以 G(x)的运算可以通过移位寄存器和半加器来实现：
1)( 12211 xgxgxgxxG rrr?
R 1 R 4 R 3 R 2 R 0
输入
=1 比特移位寄存器
= 半加器
G ( x ) = x
5
+ x
4
+ x
2
+1
循环冗余码 CRC（ 8）
开始移位寄存器都为 ‘ 0’
信息位从高到低逐位输入，经过 k次移位后，
移位寄存器中得到的是 r位冗余位
当 R4移出的为 0时，下一个输入到来时相当于移位过程
当 R4移出的为 1时，下一个输入到来时相当于第 2、
4,6（输入）比特与 1半加。
接收端检验的过程也是除以 G(x)的过程，最后增加一个,与,门来判别余式是否为全 0。
数据链路层的功能（ 1）
数据链路层在物理层提供的服务的基础上向网络层提供服务
把网络层来的数据沿一条链路（ link）传递给相邻的节点
数据链路层提供的服务：
1、成帧（ Framing）、帧同步
比特流在传输过程中可能会出错
只需重传出错帧：帧中包含检验和字段
如何确定帧的边界？
数据链路层的功能（ 2）
1、成帧（ Framing）
字节计数法：特殊字符表示帧的开始，一个字段来给出帧的长度
字符填充的首尾定界符：特殊字符表示帧的开始，
信息位中的特殊字符前加一个转义字符 DLE
比特填充的首尾标志方法：特定的比特模式标志帧的起始，信息位中出线比特模式时，进行比特填充
违例编码法：采用不可能出线在信息位中的比特编码作为帧的起始边界。
曼彻斯特编码中电平的跳变表示 1（高 ->低）和 0（低 ->高）
高高和低低电平是违例编码数据链路层的功能（ 3）
2、链路访问（ link-access）
点到点的链路相对来说要简单些,PPP
多路访问：多个节点共享一条广播链路
硬件地址：标识给哪一个节点
3、差错检测和差错校正
4、可靠递交（差错控制）
确认和重传
超时和序号
5、流量控制：接收方的能力有限制
6、半双工和全双工：
习题
3.3
3.4
3.6
