差错控制概述1. 差错的概念所谓差错，就是在通信接收端收到的数据与发送端实际发出的数据出现不一致的现象。

2. 差错类型通信信道的噪声分为热噪声和冲击噪声两种。

由这两种噪声分别产生两种类型的差错，随机差错和突发差错。

热噪声是由传输介质导体的电子热运动产生的，它的特点是：时刻存在，幅度较小且强度与频率无关，但频谱很宽，是一类随机噪声。

由热噪声引起的差错称随机差错。

此类差错的特点是：差错是孤立的，在计算机网络应用中是极个别的。

与热噪声相比，冲击噪声幅度较大，是引起传输差错的主要原因。

冲击噪声的持续时间要比数据传输中的每比特发送时间要长，因而冲击噪声会引起相邻多个数据位出错。

冲击噪声引起的传输差错称为突发差错。

常见的突发错是由冲击噪声（如电源开关的跳火、外界强电磁场的变换等）引起，它的特点是：差错呈突发状，影响一批连续的bit（突发长度）。

计算机网络中的差错主要是突发差错。

通信过程中产生的传输差错，是由随机差错和突发差错共同构成的。

3. 误码率数据传输过程中可用误码率Pe来衡量信道数据传输的质量，误码率是指二进制码元在数据传输系统中出现差错的概率，可用下式表达：4. 差错控制差错控制是指在数据通信过程中能发现或纠正差错，将差错限制在尽可能小的允许范围内。

差错检测是通过差错控制编码来实现的；而差错纠正是通过差错控制方法来实现的。

差错控制编码差错控制编码的原理是：发送方对准备传输的数据进行抗干扰编码，即按某种算法附加上一定的冗余位，构成一个码字后再发送。

接收方收到数据后进行校验，即检查信息位和附加的冗余位之间的关系，以检查传输过程中是否有差错发生。

差错控制编码分检错码和纠错码两种，检错码是能自动发现差错的编码，纠错码是不仅能发现差错而且能自动纠正差错的编码。

衡量编码性能好坏的一个重要参数是编码效率R：其中，n表示码字的位长，k表示数据信息的位长，r表示冗余位的位长。

计算机网络中常用的差错控制编码是奇偶校验码和循环冗余码。

1. 奇偶校验码奇偶校验码是一种最简单的检错码。

原理：通过增加冗余位来使得码字中"1"的个数保持为奇数（奇校验）或偶数（偶校验）。

例如，偶校验：110101000，011011011在实际使用时，奇偶校验可分为以下三种方式。

(1) 垂直奇偶校验原理：将要发送的整个数据分为定长p位的q段，每段的后面按"1"的个数为奇数或偶数的规律加上一位奇偶位：编码效率：R = P/（P+1）检错能力：能检出每列中的所有奇数个错，但检不出偶数个错。

对突发错，漏检率约为50%(2) 水平奇偶校验原理：将要发送的整个数据分为定长p位的q段，对各个数据段的相应位横向进行编码，产生一个奇偶校验冗余位：编码效率：R = Q/（Q+1）检错能力：能检出每行中的所有奇数个错，但检不出偶数个错。

对突发长度≤P的突发错都能检出。

(3) 水平垂直奇偶校验原理：能同时进行水平和垂直奇偶校验：编码效率：R = PQ / (P+1)(Q+1)检错能力：能检出所有3位或3位以下的错误，能检出所有奇数个错和很大一部分偶数个错，并对突发长度≤P+1的突发错都能检出。

2. 循环冗余码循环冗余码又称CRC码（Cyclic Redundancy Code），简称循环码。

CRC码检错能力强，且容易实现，是目前最广泛的检错码编码方法之一。

在计算机网络中，CRC被广泛采用。

CRC是一种检错码，其编码过程涉及多项式知识。

多项式和比特串有一定的对应关系，例如，比特串10010101110可被解释成发送端的编码步骤：(1) 将要发送的二进制数据（k位比特序列），对应一个（k-1）阶多项式K(x)；再选取一个收发双方预先约定的r阶生成码多项式G(x)(2) 在原数据尾添加r个0，即，x r K(x)。

(3) 进行x r K(x)/G(x)，求得余数R(x)。

R(x)即为校验序列.(4) 用R(x)替代x r K(x)最后的r个0（即x r K(x) - R(x)），得到待传送的CRC码多项式（数据位加校验位）T(x)。

[说明] CRC码字的总长（传送位）为n = k+r位，对应一个（n-1）阶多项式T(x)。

接收端的检验(1) 接收端收到的CRC码多项式T'(x)(2) 校验：进行T'(x)/G(x)，求得余数。

(3) 若余数为0，则正确（即，T'(x) / G(x) = K(x)）；若余数不为0，则出错。

[注意] 发送方和接收方使用的G(x)要一致。

G(x)的各种标准G(x)有各种标准，目前广泛使用的主要有以下四种：CRC12=CRC16=（IBM公司）CRC16=（CCITT）CRC32=结论根据CRC性质，若适当选取G(x)，使其含有(x+1)因子，常数项不为0，且周期大于n，则由此G(x)作为生成多项式产生的CRC码，可检测出：所有双位错、所有奇数位错、所有突发长度小于等于r的突发错、（1-2-(r-1)）的突发长度等于r+1的突发错以及（1-2-r）的突发长度大于r+1的突发错。

循环冗余码的产生与码字正确性检验例子。

例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)*Xr1 1 0 0 1 ，1 0 0 0 01 1 0 0 11 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 11 1 0 0 10←S(X)(余数)2)因r=4，所以冗余码是：11001，信息码是:1100113.循环冗余码的工作原理循环冗余码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)可检测出所有小于、等于校验位长度的突发错。

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+a6S1=a1+a3+a5+a6S0=a0+a3+a4+a6求：海明码码字。

解：1)由监督关系式知冗余码为a2a1a0。

2)冗余码与信息码合成的海明码是："0010a2a1a0"。

设S2=S1=S0=0,由监督关系式得：a2=a4+a5+a6=1a1=a3+a5+a6=0a0=a3+a4+a6=1因此，海明码码字为："0010101"2)海明码的接收。

例2.已知：海明码的监督关系式为：S2=a2+a4+a5+a6S1=a1+a3+a5+a6S0=a0+a3+a4+a6接收码字为："0011101"(n=7)求：发送端的信息码。

解：1)由海明码的监督关系式计算得S2S1S0=011。

2)由监督关系式可构造出下面错码位置关系表：S2S1S0 000 001 010 100 011 101 110 111错码位置无错 a0 a1 a2 a3 a4 a5 a63)由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)=1B=∑(0,1,0,0,1,0)=0C=∑(0,1,0,0,0)=1D=∑(0,1,1,0,0)=04)海明码为:"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)初值=02)求出冗余码的偶校验和，并按码位累加到err中：A=∑(1,0,1,0,1,0)=1 err=err+20=1B=∑(0,0,0,0,1,0)=1err=err+21=3C=∑(1,1,0,0,0)=0 err=err+0 =3D=∑(0,1,1,0,0)=0 err=err+0 =3由err≠0可知接收码字有错，3)码字的错误位置就是错误累加器(err)的值3。