奇偶校验crc校验和海明码

第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.垂直奇偶校验的特点及编码规则

发送顺序	↑ │ │ │ │	I11 I12 ... I1q	┐ │ │ │ ┘	信 息 位
		I21 I22 ... I2q
		......
		Ip1 Ip2 ... Ipq
		r1  r2  ... rq	冗余位

　　1)编码规则：
　　偶校验：r_i=I_1i+I_2i+...+I_pi　(i=1,2,...,q)
　　奇校验：r_i=I_1i+I_2i+...+I_pi+1(i=1,2,...,q)
　　式中 p为码字的定长位数
　　　　 q为码字的个数
　　垂直奇偶校验的编码效率为R=p/(p+1)。

　　2)特点：垂直奇偶校验又称纵向奇偶校验，它能检测出每列中所有奇数个错，但检测不出偶数个的错。因而对差错的漏检率接近1/2。

位\数字		0 1 2 3 4 5 6 7 8 9
C1		0 1 0 1 0 1 0 1 0 1
C2		0 0 1 1 0 0 1 1 0 0
C3		0 0 0 0 1 1 1 1 0 0
C4		0 0 0 0 0 0 0 0 1 1
C5		1 1 1 1 1 1 1 1 1 1
C6		1 1 1 1 1 1 1 1 1 1
C7		0 0 0 0 0 0 0 0 0 0
偶	C0	0 1 1 0 1 0 0 1 1 0
奇		1 0 0 1 0 1 1 0 0 1

　2.水平奇偶校验的特点及编码规则
　　1)编码规则：

发送顺序	↑ │ │ │ │	I11 I12 ... I1q	r1 r2 .... rp
		I21 I22 ... I2q
		......
		Ip1 Ip2 ... Ipq
		└──────┘	↑
		信息位	冗余位

　　偶校验：r_i=I_i1+I_i2+...+I_iq　(i=1,2,...,p)
　　奇校验：r_i=I_i1+I_i2+...+I_iq+1(i=1,2,...,p)
　　式中 p为码字的定长位数
　　　　 q为码字的个数
　　水平奇偶校验的编码效率为R=q/(q+1)。

　　2)特点：水平奇偶校验又称横向奇偶校验，它不但能检测出各段同一位上的奇数个错，而且还能检测出突发长度<=p的所有突发错误。其漏检率要比垂直奇偶校验方法低，但实现水平奇偶校验时，一定要使用数据缓冲器。

位\数字	0 1 2 3 4 5 6 7 8 9	偶校验
C1	0 1 0 1 0 1 0 1 0 1	1
C2	0 0 1 1 0 0 1 1 0 0	0
C3	0 0 0 0 1 1 1 1 0 0	0
C4	0 0 0 0 0 0 0 0 1 1	0
C5	1 1 1 1 1 1 1 1 1 1	1
C6	1 1 1 1 1 1 1 1 1 1	1
C7	0 0 0 0 0 0 0 0 0 0	0

　3.水平垂直奇偶校验的特点及编码规则
　　1)编码规则：

发送顺序	↑ │ │ │ │	I11	I12	...	I1q	r1,q+1
		I21	I22	...	I2q	r2,q+1
		......				...
		Ip1	Ip2	...	Ipq	rp,q+1
		rp+1,1	rp+1,2	...	rp+1,q	rp+1,q+1

　　若水平垂直都用偶校验，则　
　　　　　　r_i,q+1=I_i1+I_i2+...+I_iq (i=1,2,...,p)

　　　　　　r_p+1,j=I_1j+I_2j+...+I_pj (j=1,2,...,q)

　　　　　　r_p+1,q+1=r_p+1,1+r_p+1,2+...+r<sub>p+1,q

　　　　　　　　　　　</sub>=r_1,q+1+r_2,q+1+...+r_p,q+1

　　水平垂直奇偶校验的编码效率为R=pq/[(p+1)(q+1)]。

　　2)特点：水平垂直奇偶校验又称纵横奇偶校验。它能检测出所有3位或3位以下的错误、奇数个错、大部分偶数个错以及突发长度<=p+1的突发 错。可使误码率降至原误码率的百分之一到万分之一。还可以用来纠正部分差错。有部分偶数个错不能测出。适用于中、低速传输系统和反馈重传系统。

位\数字	0 1 2 3 4 5 6 7 8 9	校验码字
C1	0 1 0 1 0 1 0 1 0 1	1
C2	0 0 1 1 0 0 1 1 0 0	0
C3	0 0 0 0 1 1 1 1 0 0	0
C4	0 0 0 0 0 0 0 0 1 1	0
C5	1 1 1 1 1 1 1 1 1 1	1
C6	1 1 1 1 1 1 1 1 1 1	1
C7	0 0 0 0 0 0 0 0 0 0	0
C8	0 1 1 0 1 0 0 1 1 0	1

　2.5.3 循环冗余码（CRC）
　1.CRC的工作方法
　　在发送端产生一个循环冗余码，附加在信息位后面一起发送到接收端，接收端收到的信息按发送端形成循环冗余码同样的算法进行校验，若有错，需重发。
　2.循环冗余码的产生与码字正确性检验例子。
　例1.已知：信息码:110011　信息多项式:K(X)=X⁵+X⁴+X+1
　　　　　　生成码:11001   　生成多项式:G(X)=X⁴+X³+1(r=4)
　　　　求：循环冗余码和码字。
　　解：1)(X⁵+X⁴+X+1)*X⁴的积是 X⁹+X⁸+X⁵+X⁴ 对应的码是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)*X^r　
　　　　　　　　　　 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)=X⁹+X⁸+X⁵+X⁴+X³+1
　　　　　　生成码　:　　11001    生成多项式:G(X)=X⁴+X³+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)*X^r＋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  或  2^r>=k+r+1
　　海明码的编码效率为：
　　　　　　　　　　　　R=k/(k+r)
　　式中 k为信息位位数
　　　　 r为增加冗余位位数

　2.海明码的生成与接收

　方法一：（按教科书）

　1)海明码的生成。

　例1.已知：信息码为："0010"。海明码的监督关系式为：
　　　　　　　　S₂=a₂+a₄+a₅+a₆
　　　　　　　　S₁=a₁+a₃+a₅+a₆
　　　　　　　　S₀=a₀+a₃+a₄+a₆
　　　　求：海明码码字。

　　解：1)由监督关系式知冗余码为a₂a₁a₀。
　　　　2)冗余码与信息码合成的海明码是："0010a₂a₁a₀"。
　　　　　设S₂=S₁=S₀=0,由监督关系式得：
　　　　　　　　a₂=a₄+a₅+a₆=1
　　　　　　　　a₁=a₃+a₅+a₆=0
　　　　　　　　a₀=a₃+a₄+a₆=1
　因此，海明码码字为："0010101"
　　　　
　2)海明码的接收。

　例2.已知：海明码的监督关系式为：
　　　　　　　　S₂=a₂+a₄+a₅+a₆
　　　　　　　　S₁=a₁+a₃+a₅+a₆
　　　　　　　　S₀=a₀+a₃+a₄+a₆
　　　　　　接收码字为："0011101"(n=7)

　　　　求：发送端的信息码。

　　解：1)由海明码的监督关系式计算得S₂S₁S₀=011。
　　　　2)由监督关系式可构造出下面错码位置关系表：

S2S1S0	000	001	010	100	011	101	110	111
错码位置	无错	a0	a1	a2	a3	a4	a5	a6

　　　　3)由S₂S₁S₀=011查表得知错码位置是a₃。
　　　　4)纠错--对码字的a₃位取反得正确码字："0 0 1 0 1 0 1"
　　　　5)把冗余码a₂a₁a₀删除得发送端的信息码："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分别插于2^k位(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+2⁰=1
　　　　　　B=∑(0,0,0,0,1,0)=1　err=err+2¹=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)把位于2^k位的冗余码删除得信息码："1 1 0 0 1 1 0 0"