计算机51-60复习进程.doc

《计算机51-60复习进程.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、计算机51-60精品文档51-60（2）确定校验位的位置设添加校验码后的海明码为HmHm-1…H2H1，其中m=k+r，以位号为、、、…、的位置作为校验位，记作P1、P2、…、Pr，即Hj=Pi（j=），余下的为原数据位，即H1、H2、H4…等为校验位。（3）分组海明码的每一位码Hi（包括数据位和校验位本身）有多个校验位校验，其关系是被校验的每一位的位号等于校验它的校验位的位号之和。这样安排的目的是希望校验的结果能正确反映出出错位的位号。因此，将m位分为r组，第i（1≤i≤m）位由校验位号之和等于i的那些校验位所校验。如i=3时，由于3=1+2，

2、所以H3由校验位1和校验位2来校验。（4）校验位的形成P1=第一组中的所有位求异或P2=第二组中的所有位求异或…Pr=第r组中的所有位求异或为了能检测两个错误，可增加一位校验pr+1放在最高位。Pr+1=所有位（包括P1、P2、…、Pr）共m位求异或。2）校验原理在接收端分别求S1、S2、S3、…、Sr；S1=P1与第一组中的所有位求异或S2=P2与第一组中的所有位求异或…收集于网络，如有侵权请联系管理员删除精品文档Sr=Pr与第一组中的所有位（包括Pr）求异或Sr+1=Pr+1所有位(包括P1、P2、…、Pr)求异或当Sr+1=1时有一位错，由

3、Sr…S3S2S1的二进制编码找到出错位号，将其取反，即可校正。当Sr+1=0时无错或有偶数个错（两个错的可能性比较大），即当Sr…S3S2S1=0…000时，接收的数据无错，否则有两个错。海明校验码特点：能检测出2位错误，并能纠正1位错误。推广：如果要用海明码检测d位错误，则需要一个码距为d+1的编码方案，如果要纠出d位错误，需要一个码距为2d+1的编码方案。海明码的纠错能力小于等于纠错能力。【例2.5】给出编码1001的海明码。解：这里k=4，被校验码字为d4d3d2d1（1001）共4位，由m=k+r≤-1条件求得最小r为3，则校验位为P3

4、P2P1，m=7，设对应的海明码为H7H6H5H4H0H2H1。①校验位的分布规定校验位Pi放在海明码位号为的位置上，因此：P1（i=1）的海明码位号为==1，即H1为P1。P2（i=2）的海明码位号为==2，即H2为P2。P3（i=3）的海明码位号为==4，即H4为P3。②数据位的分布数据位按原来的顺序，插入排列如下：H7H6H5H4H3H2H1D4d3d2P3d1P2P1③校验关系数据位用多个校验位进行校验，但要求满足被校数据位的海明码位号等于校验数据位的个校验位海明码位号之和。另外校验位不需要再被校验。收集于网络，如有侵权请联系管理员删除精

5、品文档各数据位与校验位的关系如下。P1P2P3D1放在H3上，由P2P1校验：3=1+2D2放在H5上，由P3P1校验：5=1+4D3放在H6上，由P3P2校验：6=2+4D4放在H7上，由P3P2P1校验：7=1+2+4①校验位取值根据上述校验关系有：P1=d1+d2+d4=1+0+1=0P2=d1+d3+d4=1+0+1=0P3=d2+d3+d4=0+0+1=1所以，编码1001的海明码为1001100②海明校验值在接收方的每个校验组内，利用校验位和参与校验位形成的信息进行奇偶校验检查，就构成了检验方程：S1=P1+d1+d2+d4S2=P2

6、+d1+d3+d4S3=P3+d2+d3+d4校验方程得知就构成一个二进制数S3S2S1，利用这个结果就可可以判定海明码的正确与否。若这个数为“000”，则说明码没有错误；否则说明码发生错误，并且这个数就是错误位的位号，如S3S2S1=001，说明第1位出错。当发现错误位后，对改位取反，就达到了校正错误的目的。4.循环冗余校验（CRC）码收集于网络，如有侵权请联系管理员删除精品文档CRC码的基本思想是：在k为信息码后在拼接r位检验吗，整个编码长度为n=k+r位，因此，这种编码又称为（n，k）码。可以证明存在一个最高幂次为r=n-k的生成多项式G（

7、x），根据G（x）可以生成k位信号的校验码。G（x）称为这个CRC码的生成多项式。1）CRC校验码生成过程假设发送信息用信息多项式G（x）表示，该多项式和二进制数有直接对应关系：x的最高幂次对应二进制数的最高位，以下各位对应多项式的各幂次，有此幂次项对应1，无此幂次项对应0，即：C（x）=Ck-1+Ck-2+…+Ci+C1x+C0其中Ci为0或1将C（x）左移r位，移空处补0，则可表示成C（x），这样C（x）的右边就会空出r位，这就是校验码的位置。通过C（x）除以生成多项式G（x）得到的余数就是校验码。G（x）最高幂次为r，转换成对应的二进制数有

8、r+1位。例如，生成多项式G（x）=++x+1，可转化为二进制码11011；发送信息为1111，可转换为数据多项式G（x）=++x+1。