计算机网络技术第六讲计算机网络技术.ppt

计算机网络技术
第六讲
差错检测与控制
例子：对四位有效信息1100做循环冗余校验码，选择生成多项式G(x)为1011（k=3）
(1) M(x)=x3+x2 (=C3x3+C2x2+C１x+C０)
(2) M(x)×x3=x6+x5=1100000(k=3,左移三位)
(3) 模2除， M(x)×xk/ G(x)=1100000/1011
=1110+010/1011，即余数R(x)=010
1 1 1 0 商
1 0 1 1 1 1 0 0 0 0 0
1 0 1 1
1 1 1 0
1 0 1 1
1 0 1 0
1 0 1 1
0 0 1 0
0 0 0 0
0 1 0
余数
(4) 模2加，得到T(x)= M(x)×x3+R(x)
=1100000+010=1100010。
§ 传输技术
差错检测与控制
CRC循环码的出错模式（G（x） =1011）
D7
D6
D5
D4
D3
D2
D1
余数
出错位
正确
1
1
0
0
0
1
0
0
0
0
—
错误
1
1
0
0
0
1
1
0
0
1
1
1
1
0
0
0
0
0
0
1
0
2
1
1
0
0
1
1
0
1
0
0
3
1
1
0
1
0
1
0
0
1
1
4
1
1
1
0
0
1
0
1
1
0
5
1
0
0
0
0
1
0
1
1
1
6
0
1
0
0
0
1
0
1
0
1
7
§ 传输技术
差错检测与控制
“循环码”的来历。
【例】G(x)＝1011，M(x)＝1100，若接收端收到的码字为1100110，用G(x)＝1011做模2除得到一个不为0的余数100，说明D3位传输有错。将此余数继续补0用G(x)＝1011作模2除，同时让码字循环左移。做了4次后，得到余数为101，这时码字也循环左移4位。说明出错位已移到最高位D7位，将最高位1取反后再将它循环左移3位，补足7次，出错位回到D3位，就成为一个正确的码字1100010。
§ 传输技术
差错检测与控制
生成多项式G(x)应满足的要求：
最高位和最低位同时为1；
任何一位发生错误都应使余数不为0；
不同位发生错误应使余数不同；
对余数继续做模2除运算应使余数循环。
§ 传输技术
差错检测与控制
常用的标准生成多项式有以下几种：
CRC-ITU-T: G(x)=x16+x12+x５+1
CRC-12: G(x)=x12+x11+x３+x２+x+1
CRC-16: G(x)=x16+x15+x２+1
CRC-32:
G(x)=x32+x26+x23+x22+x16+x12+x11+x10+x８+x７+x５+x４+x２+x+1
§ 传输技术
差错检测与控制
3. 差错控制协议
在计算机通信中，一般都要求有极低的比特差错率。为此广泛地使用了编码技术，主要有两大类：
前向纠错：开销较大，不适合于计算机通信。
检错重发：在计算机通信中是最常用的。
由于发送方对出错的数据帧进行重复是自动进行的，所以这种差错控制体制常简称为ARQ（Automatic Repeat reQuest），直译是自动重复请求，意思是自动请求重发。
差错检测与控制
（1）停等ARQ协议
基本原理是发送方根据应答信号来确定接下来发送数据帧的情况。
DATA0
ACK
ACK
ACK
DATA2
DATA1
出错
a) 正常情况
b) 数据帧出错
送主机
A
B
送主机
送主机
DATA0
ACK
NAK
ACK
DATA1
DATA1
送主机
A
B
送主机
重传
差错检测与控制
DATA0
ACK
ACK
DATA1
DATA1
丢失
DATA0
ACK
ACK
ACK
DA