第2章 计算机网络基础知识
2.5 差错控制方法
2.5.1 差错的产生原因及其控制方法
差错控制在数据通信过程中能发现或纠正差错，把差错限制在尽可能小的允许范围内的技术和方法。
信号在物理信道中传输时，线路本身电器特性造成的随机噪声、信号幅度的衰减、频率和相位的畸变、电器信号在线路上产生反射造成的回音效应、相邻线路间的串扰以及各种外界因素（如大气中的闪电、开关的跳火、外界强电流磁场的变化、电源的波动等）都会造成信号的失真。在数据通信中，将会使接受端收到的二进制数位和发送端实际发送的二进制数位不一致，从而造成由“0”变成“1”或由“1”变成“0”的差错。
1.热噪声和冲击噪声
传输中的差错都是由噪声引起的。噪声有两大类，一类是信道固有的、持续存在的随机热噪声；另一类是由外界特定的短暂原因所造成的冲击噪声。
热噪声引起的差错称为随机差错所引起的某位码元的差错是孤立的，与前后码元没有关系。它导致的随机错通常较少。
冲击噪声呈突发状，由其引起的差错称为突发错。冲击噪声幅度可能相当大，无法靠提高幅度来避免冲击噪声造成的差错，它是传输中产生差错的主要原因。冲击噪声虽然持续时间较短，但在一定的数据速率条件下，仍然会影响到一串码元。
2.差错的控制方法
最常用的差错控制方法是差错控制编码。数据信息位在向信道发送之前，先按照某种关系附加上一定的冗余位，构成一个码字后再发送，这个过程称为差错控制编码过程。接收端收到该码字后，检查信息位和附加的冗余位之间的关系，以检查传输过程中是否有差错发生，这个过程称为检验过程。
差错控制编码可分为检错码和纠错码。
①检错码－－能自动发现差错的编码；
②纠错码－－不仅能发现差错而且能自动纠正差错的编码。
差错控制方法分两类，一类是自动请求重发arq，另一类是前向纠错fec。
在arq方式中，当接收端发现差错时，就设法通知发送端重发，直到收到正确的码字为止。arq方式只使用检错码。
在fec方式中，接收端不但能发现差错，而且能确定二进制码元发生错误的位置，从而加以纠正。fec方式必须使用纠错码。
3.编码效率
衡量编码性能好坏的一个重要参数是编码效率r，它是码字中信息位所占的比例。编码效率越高，即r越大，信道中用来传送信息码元的有效利用率就越高。编码效率计算公式为：
r=k/n=k/(k+r)
式中 k为码字中的信息位位数
r为编码时外加冗余位位数
n为编码后的码字长度
2.5.2 奇偶校验码
奇偶校验码是一种通过增加冗余位使得码字中“１”的个数为奇数或偶数的编码方法，它是一种检错码。
1.垂直奇偶校验的特点及编码规则
1)编码规则：
偶校验：ri=i1i+i2i+...+ipi (i=1,2,...,q)
奇校验：ri=i1i+i2i+...+ipi+1(i=1,2,...,q)
式中 p为码字的定长位数
q为码字的个数
垂直奇偶校验的编码效率为r=p/(p+1)。
2)特点：垂直奇偶校验又称纵向奇偶校验，它能检测出每列中所有奇数个错，但检测不出偶数个的错。因而对差错的漏检率接近1/2。
偶校验：ri=ii1+ii2+...+iiq (i=1,2,...,p)
奇校验：ri=ii1+ii2+...+iiq+1(i=1,2,...,p)
式中 p为码字的定长位数
q为码字的个数
水平奇偶校验的编码效率为r=q/(q+1)。
2)特点：水平奇偶校验又称横向奇偶校验，它不但能检测出各段同一位上的奇数个错，而且还能检测出突发长度<=p的所有突发错误。其漏检率要比垂直奇偶校验方法低，但实现水平奇偶校验时，一定要使用数据缓冲器。
2.5.3 循环冗余码（crc）
1.crc的工作方法
在发送端产生一个循环冗余码，附加在信息位后面一起发送到接收端，接收端收到的信息按发送端形成循环冗余码同样的算法进行校验，若有错，需重发。
2.循环冗余码的产生与码字正确性检验例子。
例1.已知：信息码:110011 信息多项式:k(x)=x5+x4+x+1
生成码:11001 生成多项式:g(x)=x4+x3+1(r=4)
求：循环冗余码和码字。
解：1)(x5+x4+x+1)*x4的积是 x9+x8+x5+x4 对应的码是1100110000。
2)积／g(x)(按模二算法)。
由计算结果知冗余码是1001，码字就是1100111001。
1 0 0 0 0 1←q(x)
g(x)→1 1 0 0 1 )1 1 0 0 1 1 0 0 0 0←f(x)*xr
1 1 0 0 1 ，
1 0 0 0 0
1 1 0 0 1
1 0 0 1←r(x)(冗余码)
例2.已知：接收码字:1100111001 多项式:t(x)=x9+x8+x5+x4+x3+1
生成码 : 11001 生成多项式:g(x)=x4+x3+1(r=4)
求：码字的正确性。若正确，则指出冗余码和信息码。
解：1)用字码除以生成码，余数为0，所以码字正确。
1 0 0 0 0 1←q(x)
g(x)→1 1 0 0 1 )1 1 0 0 1 1 1 0 0 1←f(x)*xr＋r(x)
1 1 0 0 1 ，
1 1 0 0 1
1 1 0 0 1
0←s(x)(余数)
2)因r=4，所以冗余码是：11001，信息码是:110011
3.循环冗余码的工作原理
循环冗余码crc在发送端编码和接收端校验时，都可以利用事先约定的生成多项式g(x)来得到，k位要发送的信息位可对应于一个(k-1)次多项式k(x),r位冗余位则对应于一个(r-1)次多项式r(x)，由r位冗余位组成的n=k+r位码字则对应于一个(n-1)次多项式t(x)=xr*k(x)+r(x)。
4.循环冗余校验码的特点
1)可检测出所有奇数位错；
2)可检测出所有双比特的错；
3)可检测出所有小于、等于校验位长度的突发错。
5.4种生成码(p44)
2.5.4 海明码
1.海明码的概念
海明码是一种可以纠正一位差错的编码。它是利用在信息位为k位，增加r位冗余位，构成一个n=k+r位的码字，然后用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的一位错。它必需满足以下关系式：
２r>=n+1 或 2r>=k+r+1
海明码的编码效率为：
r=k/(k+r)
式中 k为信息位位数
r为增加冗余位位数
2.海明码的生成与接收
方法一：（按教科书）
1)海明码的生成。
例1.已知：信息码为："0010"。海明码的监督关系式为：
s2=a2+a4+a5+a6
s1=a1+a3+a5+a6
s0=a0+a3+a4+a6
求：海明码码字。
解：1)由监督关系式知冗余码为a2a1a0。
2)冗余码与信息码合成的海明码是："0010a2a1a0"。
设s2=s1=s0=0,由监督关系式得：
a2=a4+a5+a6=1
a1=a3+a5+a6=0
a0=a3+a4+a6=1
因此，海明码码字为："0010101"
2)海明码的接收。
例2.已知：海明码的监督关系式为：
s2=a2+a4+a5+a6
s1=a1+a3+a5+a6
s0=a0+a3+a4+a6
接收码字为："0011101"(n=7)
求：发送端的信息码。
解：1)由海明码的监督关系式计算得s2s1s0=011。
2)由监督关系式可构造出下面错码位置关系表：
3)由s2s1s0=011查表得知错码位置是a3。
4)纠错--对码字的a3位取反得正确码字："0 0 1 0 1 0 1"
5)把冗余码a2a1a0删除得发送端的信息码："0010"
方法二：(不用查表，方便编程)
1)海明码的生成（顺序生成法）。
例3.已知：信息码为：" 1 1 0 0 1 1 0 0 " (k=8)
求：海明码码字。
解：1)把冗余码a、b、c、…，顺序插入信息码中，得海明码
码字:" a b 1 c 1 0 0 d 1 1 0 0 "
码位: 1 2 3 4 5 6 7 8 9 10 11 12
其中a,b,c,d分别插于2k位(k=0,1,2,3)。码位分别为1,2,4,8。
2)冗余码a,b,c,d的线性码位是：(相当于监督关系式)
a->1,3,5,7,9,11；
b->2,3,6,7,10,11；
c->4,5,6,7,12；(注 5=4+1；6=4+2；7=4+2+1；12=8+4)
d->8,9,10,11,12。
3)把线性码位的值的偶校验作为冗余码的值(设冗余码初值为0)：
a=∑(0,1,1,0,1,0)=1
b=∑(0,1,0,0,1,0)=0
c=∑(0,1,0,0,0) =1
d=∑(0,1,1,0,0) =0
4)海明码为:"1 0 1 1 1 0 0 0 1 1 0 0"
2)海明码的接收。
例4.已知：接收的码字为："1 0 0 1 1 0 0 0 1 1 0 0"(k=8)
求：发送端的信息码。
解：1)设错误累加器(err)初值=0
2)求出冗余码的偶校验和，并按码位累加到err中：
a=∑(1,0,1,0,1,0)=1 err=err+20=1
b=∑(0,0,0,0,1,0)=1 err=err+21=3
c=∑(1,1,0,0,0) =0 err=err+0 =3
d=∑(0,1,1,0,0) =0 err=err+0 =3
由err≠0可知接收码字有错，
3)码字的错误位置就是错误累加器(err)的值3。
4)纠错--对码字的第3位值取反得正确码字：
"1 0 1 1 1 0 0 0 1 1 0 0"
5)把位于2k位的冗余码删除得信息码："1 1 0 0 1 1 0 0"
作业二：
目 录 下一页