差错控制方法(奇偶校验码、循环冗余码、海明码).doc

差错控制方法差错控制方法差错控制在数据通信过程中能发现或纠正差错，把差错限制在尽可能小的允许范围内的技术和方法。1.差错的控制方法最常用的差错控制方法是差错控制编码。数据信息位在向信道发送之前，先按照某种关系附加上一定的冗余位，构成一个码字后再发送，这个过程称为差错控制编码过程。接收端收到该码字后，检查信息位和附加的冗余位之间的关系，以检查传输过程中是否有差错发生，这个过程称为检验过程。差错控制编码可分为检错码和纠错码。检错码能自动发现差错的编码；纠错码不仅能发现差错而且能自动纠正差错的编码。差错控制方法分两类，一类是自动请求重发ARQ，另一类是前向纠错FEC。在ARQ方式中，当接收端发现差错时，就设法通知发送端重发，直到收到正确的码字为止。ARQ方式只使用检错码。在FEC方式中，接收端不但能发现差错，而且能确定二进制码元发生错误的位置，从而加以纠正。FEC方式必须使用纠错码。2.编码效率衡量编码性能好坏的一个重要参数是编码效率R，它是码字中信息位所占的比例。编码效率越高，即R越大，信道中用来传送信息码元的有效利用率就越高。编码效率计算公式为：R=k/n=k/(k+r)式中k为码字中的信息位位数r为编码时外加冗余位位数n为编码后的码字长度2.5.2奇偶校验码奇偶校验码是一种通过增加冗余位使得码字中“”的个数为奇数或偶数的编码方法，它是一种检错码。1.垂直奇偶校验的特点及编码规则 发送顺序I11 I12 . I1q信息位I21 I22 . I2q.Ip1 Ip2 . Ipqr1 r2 . rq冗余位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。 位数字0 1 2 3 4 5 6 7 8 9C10 1 0 1 0 1 0 1 0 1C20 0 1 1 0 0 1 1 0 0C30 0 0 0 1 1 1 1 0 0C40 0 0 0 0 0 0 0 1 1C51 1 1 1 1 1 1 1 1 1C61 1 1 1 1 1 1 1 1 1C7 0 0 0 0 0 0 0 0 0 0 偶C00 1 1 0 1 0 0 1 1 0奇1 0 0 1 0 1 1 0 0 12.水平奇偶校验的特点及编码规则1)编码规则： 发送顺序I11 I12 . I1qr1r2.rpI21 I22 . I2q.Ip1 Ip2 . Ipq信息位冗余位偶校验：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的所有突发错误。其漏检率要比垂直奇偶校验方法低，但实现水平奇偶校验时，一定要使用数据缓冲器。 位数字0 1 2 3 4 5 6 7 8 9偶校验C10 1 0 1 0 1 0 1 0 11C20 0 1 1 0 0 1 1 0 00C30 0 0 0 1 1 1 1 0 00C40 0 0 0 0 0 0 0 1 10C51 1 1 1 1 1 1 1 1 11C61 1 1 1 1 1 1 1 1 11C7 0 0 0 0 0 0 0 0 0 0 0 3.水平垂直奇偶校验的特点及编码规则1)编码规则： 发送顺序I11I12.I1qr1,q+1I21I22.I2qr2,q+1.Ip1Ip2.Ipqrp,q+1rp+1,1rp+1,2.rp+1,qrp+1,q+1若水平垂直都用偶校验，则 ri,q+1=Ii1+Ii2+.+Iiq (i=1,2,.,p)rp+1,j=I1j+I2j+.+Ipj (j=1,2,.,q)rp+1,q+1=rp+1,1+rp+1,2+.+rp+1,q=r1,q+1+r2,q+1+.+rp,q+1水平垂直奇偶校验的编码效率为R=pq/(p+1)(q+1)。2)特点：水平垂直奇偶校验又称纵横奇偶校验。它能检测出所有3位或3位以下的错误、奇数个错、大部分偶数个错以及突发长度=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因此，海明码码字为：00101012)海明码的接收。例2.已知：海明码的监督关系式为：S2=a2+a4+a5+a6S1=a1+a3+a5+a6S0=a0+a3+a4+a6接收码字为：0011101(n=7)求：发送端的信息码。解：1)由海明码的监督关系式计算得S2S1S0=011。2)由监督关系式可构造出下面错码位置关系表： S2S1S0000001010100011101110111错码位置无错a0a1a2a3a4a5a63)由S2S1S0=011查表得知错码位置是a3。4)纠错-对码字的a3位取反得正确码字：0 0 1 0 1 0 15)把冗余码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 02)海明码的接收。例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)=1err=err+20=1B=(0,0,0,0,1,0)=1err=err+21=3C=(1,1,0,0,0)=0err=err+0 =3D=(0,1,1,0,0)=0err=err+0 =3由err0可知接收码字有错，3)码字的错误位置就是错误累加器(err)的值3。4)纠错-对码字的第3位值取反得正确码字：1 0 1 1 1 0 0 0 1 1 0 05)把位于2k位的冗余码删除得信息码：1 1 0 0 1 1 0 0 1、 如果电缆调制解调器使用8MHZ的带宽,利用64QAM,可以提供的速率为多少.是如何做的?解析：CABLE MODEM使用的是一种称为QAM(Quadrature Amplitude Modulation正交幅度调制)的传输方式。QAM前面的数字代表在转换群组(所谓转换群组，就是相位及振幅的特殊组合)中的点数。也就是值或等级。计算公式为：速度=log2QAM值Iog22(bitHzs)频带宽度。根据此公式计算速率为Iog264log22(bit/Hz/s)8MHz=48Mbps。各种QAM被表示为mQAM，其中m是一个指出每赫兹的状态数目的整数。每一码元时间的编码位数目是k，那么2km。例如，如果以4 bHz编码，结果为16 QAM；6 bHz产生64QAM。2、 在一个带宽为3KHZ,没有噪声的信道,传输二进制信号时能够达到的极限数据传输率为_.一个带宽为3KHZ,信噪比为30dB的信道,能够达到的极限数据传输率为_,上述结果表明_.根据奈奎斯特第一定理,为了保证传输质量,为达到3KHbps的数据传输率要的带宽为_,在一个无限带宽的无噪声信道上,传输二进制信号,当信号的带宽为3KHZ时,能达到的极限数据率为_Kbps.解析：.（1） 根据奈奎斯特第一定理，理想低通信道传输二进制信号时能够达到的数据传输率为2B（带宽）。（2） 一个带宽为3KHZ、信噪比为30dB的信道，能够达到的极限数据传输率为3KHZ*log2(1+1000)=29.9Kbit/s（3） 香农公式是针对有噪声的信道而言的。（4） 根据奈奎斯特第一定理，数字信号数据率为W，传输系统带宽为2W,则可提供满意的服务。（5） 在一个无限带宽的无噪声信道上，传输二进制信号，当信号的带宽为 3KHz 时，能达到的极限数据传输率6Kbps 。信号的数据率与频宽有着直接的关系，信号的数率越高，所需要的有效频宽越宽。也就是说，传输系统所提供的带宽越宽，则系统能传输的信号数据率越高。设数据为W，通常按照2W来选择传输系统的带宽，则可提供满意的通信服务，3KbpS 的数据传输率需要的带宽为2*3=6HZ。二进制的信号是离散的脉冲，每个脉冲可表示一个二进制位，时间宽度相同，时间的宽度T=1/f,该时间的倒数为数据传输率(1/T),根据奈奎斯特定理，当信号的带宽为 3KHz 时，能达到的极限数据传输率C=2(1/T)= 6Kbps3、 设有3路模拟信号，带宽分别为2khz.4khz,2khz,8路数字信号，数据率都为7200bps，当采用TDM方式将其复用到一条通信线路上，假定复用后为数字传输，对模拟信号采用PCM方式量化级数为16级，则复用线路需要的最小通信能力为？解析：对3路模拟信号采用pcm方式变为数字信号，采样频率分别为4KHZ,8KHZ,4KHZ, 对模拟信号采用PCM方式量化级数为16级,需要的数据率分别为16kbps,32kbps 16kbps对8路数字信号，8720057.6kbps 答案为 128KPS4、 某循环冗余码（CRC）的生成多项式 G(x)x3+x2+1，用此生成多项式产生的冗余位，加在信息位后形成 CRC 码。若发送信息位 1111 和 1100 则它的 CRC 码分别为A和B。A： lllll00 1111101 1111110 1111111B： 1100100 1100101 1100110 1100111解析：A：G(x)1101，C(x)1111 C(x)*23G(x)111100011011011余111得到的CRC码为1111111B：G(x)1101，C(x)1100 C(x)*23G(x)110000011011001余101得到的CRC码为11001015.使用海明码进行前向纠错，如果冗余位为4位，那么信息位最多可以用到（1）位，假定码字为a6a5a4a3a2alao，并且有下面的监督关系式：S2=a2+a4+a5+a6S1=a1+a3+a5+a6S0=a0+a3+a4+a6若S2S1S0=110，则表示出错位是（2）。(1)A6 B8 C11 D16(2)Aa3 Ba4 Ca5 Da6解析：C C。（1）由公式2km+k+1;可以得出信息位最多可以为11。（2）由海明码的