单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,*,课 题：错误检测与纠正,,目的要求：掌握差错检测与纠正的方法CRC码、海明码,,教学重点：CRC码求法,,教学难点：海明码,,教学课时：2,,教学方法：讲授、演示,1,,奇偶校验码,,奇偶校验码是一种通过增加冗余位使得码字中“１”的个数为奇数或偶数的编码方法，它是一种检错码一个二进制码字，如果它的码元有奇数个1，就称之为具有奇性对于一个n位字，奇性=a0⊕a1⊕a2⊕…⊕an很明显，用同样的方式，也能够根据每一个码字的零的个数来构成奇偶校验单个的奇偶校验码可描述为：给每一个码字加一个校验位，用它来构成奇性或偶性校验因此，若有一个码元是错的，就可以分辨得出在一个传输系统里，传输以前，由奇偶发生器把奇偶校验位加到每个字中原有信息中的数字在接收机中被检测，如果没有出现正确的奇、偶性，这个信息标定为错误的，这个系统将把错误的字抛掉或者请求重发注意，用单个的奇偶校验码仅能检出奇数个码元的错误奇偶校验可以用在数字系统的主要接口设备中，由于在每个信息中增加了冗余度，仅当出现错误的概率和错误的危害足够大时，才采用奇偶校验码。
在实际的应用中，按码字的形成方向可以分为垂直奇偶校验、水平奇偶校验和垂直水平奇偶校验三种奇偶校验方式2,,垂直奇偶校验,,垂直奇偶校验又称纵向奇偶校验，它能检测出每列中所有奇数个错，但检测不出偶数个的错，如图2-23所示，因而对差错的漏检率接近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-23 垂直奇偶校验方式,3,,水平奇偶校验,,水平奇偶校验又称横向奇偶校验，它不但能检测出各段同一位上的奇数个错，而且还能检测出突发长度<=p的所有突发错误，如图2-24所示其漏检率要比垂直奇偶校验方法低，但实现水平奇偶校验时，一定要使用数据缓冲器位\数字,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,图2-24 水平奇偶校验方式,4,,水平垂直校验,,水平垂直校验(LRC)又叫报文校验、方块校验。
这种方法是在奇偶校验的基础上，为了提高奇偶校验码对突发错误的检测能力，将若干奇偶校验码排成若干行，然后对每列进行奇偶校验，放在最后一行，该检验字符的编码方法是使每一位纵向代码中1的个数成为奇数(或偶数)传输时按照列顺序进行传输，在一批字符传送之后，另外增加一个检验字符，在接收端又按照行的顺序检验是否存在差错由于突发错误是成串发生的，经过这样的传输后错误被分散了它能检测出所有3位或3位以下的错误、奇数个错、大部分偶数个错以及突发长度<=p+1的突发错，如图2-25所示可使误码率降至原误码率的百分之一到万分之一，还可以用来纠正部分差错，有部分偶数个错不能测出它适用于中、低速传输系统和反馈重传系统图2-25 水平垂直奇偶校验方式,5,,恒比码,,码字中1的数目与0的数目保持恒定比例的码称为恒比码恒比码”仅是单个奇偶校验的推广五中取三的恒比码常常用于传输二进形式的十进数如我国邮电部门使用的五单位数字保护电报码，就是一种五中取三的恒比码，编码方式见图2-26所示在这种表示方法中采用8-4-2-1的权数来表示十进数，然后选择所增加的恒比位使每个字恰好有两个0和三个1当接收到的任何信息其1的个数少于三或多于三，就可以知道这个信息是错误的。
恒比码能够检测出全部的单一错误和40%的两个错误数字,编码,数字,编码,1,01011,6,10101,2,11001,7,11100,3,10110,8,01110,4,11010,9,10011,5,00111,0,01101,图2-26 五中取三恒比码,6,,循环冗余检验的原理,在数据链路层传送的帧中，广泛使用了循环冗余检验 CRC 的检错技术假设待传送的数据,M,= 1010001101（共,k,bit）我们在,M,的后面再添加供差错检测用的,n,bit 冗余码一起发送7,,冗余码的计算,用二进制的模,,2,,运算进行 2,n,乘,M,的运算，这相当于在,M,后面添加,n,个 0得到的 (,k,+,n,) bit 的数除以事先选定好的长度为 (,n,+ 1) bit 的数,P,，得出商是,Q,而余数是,R,，余数,R,比除数,P,至少要少1 个比特8,,冗余码的计算举例,设,n,= 5,,P,= 110101，模 2 运算的结果是：商,Q,= 1101010110，,,余数,R,= 01110将余数,R,作为冗余码添加在数据,M,的后面发送出去，即发送的数据是1110，或 2,n,M,+,R,。
9,,,1101010110,,←,,Q,,商,,,除数,,P,→,,110101 1000,,←,,2,n,M,被除数,,,,,,110101,,,111011,,,,110101,,,,111010,,,,110101,,,111110,,,110101,,,,,101100,,,,,,110101,,,,,110010,,,110101,,,,,01110,,←,,R,,余数,循环冗余检验的原理说明,10,,帧检验序列 FCS,在数据后面添加上的冗余码称为帧检验序列 FCS (Frame Check Sequence)循环冗余检验 CRC 和帧检验序列 FCS并不等同CRC 是一种常用的检错方法，而 FCS 是添加在数据后面的冗余码FCS 可以用 CRC 这种方法得出，但 CRC 并非用来获得 FCS 的惟一方法11,,检测出差错,只要得出的余数,R,不为 0，就表示检测到了差错但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错一旦检测出差错，就丢弃这个出现差错的帧只要经过严格的挑选，并使用位数足够多的除数,P,，那么出现检测不到的差错的概率就很小很小12,,应当注意,仅用循环冗余检验 CRC 差错检测技术只能做到无差错接受(accept)。
无差错接受”是指：“凡是接受的帧（即不包括丢弃的帧），我们都能以非常接近于,,1,,的概率认为这些帧在传输过程中没有产生差错”也就是说：“凡是接受的帧都没有传输差错”（有差错的帧就丢弃而不接受）要做到“可靠传输”（即发送什么就收到什么）就必须再加上确认和重传机制13,,海明码的实现和特点,海明码,：,海明码是一种可以纠正一位差错的编码它是利用在信息位为,k,位，增加,r,位冗余位，构成一个,n=k+r,位的码字，然后用,r,个监督关系式产生的,r,个校正因子来区分无错和在码字中的,n,个不同位置的一位错它必需满足以下关系式：,,２,r,>=n+1,或,2,r,>=k+r+1,海明码的编码效率为：,,,R=k/(k+r),式中,k,为信息位位数，,r,为增加冗余位位数,,14,,Use of a Hamming code to correct burst errors,15,,已知：信息码为："0010"海明码的监督关系式为： S,2,=a,2,+a,4,+a,5,+a,6,S,1,=a,1,+a,3,+a,5,+a,6,S,0,=a,0,+a,3,+a,4,+a,6,求：海明码码字。
1)由监督关系式知冗余码为a,2,a,1,a,0, 2)冗余码与信息码合成的海明码是："0010a,2,a,1,a,0," 设S,2,=S,1,=S,0,=0,由监督关系式得： a,2,=a,4,+a,5,+a,6,=1 a,1,=a,3,+a,5,+a,6,=0,,a,0,=a,3,+a,4,+a,6,=1,,因此，海明码码字为："0010101",16,,已知：海明码的监督关系式为： S,2,=a,2,+a,4,+a,5,+a,6,S,1,=a,1,+a,3,+a,5,+a,6,S,0,=a,0,+a,3,+a,4,+a,6,接收码字为：“0011101”(n=7) 求：发送端的信息码 1)由海明码的监督关系式计算得S,2,S,1,S,0,=011 2)由监督关系式可构造出下面错码位置关系表：,,,,3),由,S,2,S,1,S,0,=011,查表得知错码位置是,a,3,4),纠错,--,对码字的,a,3,位取反得正确码字：,"0 0 1 0 1 0 1" 5),把冗余码,a,2,a,1,a,0,删除得发送端的信息码：,"0010",,17,,已知：信息码为：,“ 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,18,,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",19,,已知：接收的码字为：,“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,0,=1 B=∑(0,0,0,0,1,0)=1 err=err+2,1,=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",20,,作业：生成多项式为G(x)=x,4,+x+1，若接收方接收到的二进制流为1100110，请问传输过程是否出错？,21,,教学总结：本讲讲解错误检测与纠正下一讲讲解滑动窗口协议22,,。