




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第2章数据表示2.4数据校验码2.4数据校验码在数据编码中,能够发现错误的编码叫做检错码;能够纠正错误的编码叫做纠错码。能够检测或纠正编码中错误的信息编码,称为数据校验码,可以提高计算机的可靠性。目前的数据校验法大多采用“冗余校验”的思想,即除原数据信息外,还增加若干位新编码,这些编码称为校验码。常用的数据校验码有奇偶校验码、海明校验码和循环冗余校验码等。2.4.1奇偶校验码奇偶校验法是在信息位中增加一位校验位代码,能够检测出代码中的奇数个位的错误,但不能纠正错误。常用于存储器读写检查或按字节传输数据过程中的数据校验。奇偶校验码包括奇校验码和偶校验码两种。(1)奇偶校验位生成过程数据在存储和传输时首先需要加上校验位P。奇(偶)校验位的生成过程如下:假设源数据为B=bn-1bn-2……b1b0。若采用奇校验位,则P=bn-1⊕bn-2⊕……b1⊕b0⊕1,即若源数据B有奇数个1,则P取0,否则取1,也就是保证加上校验位之后的数据编码中有奇数个1。若采用偶校验位,则P=bn-1⊕bn-2⊕…b1⊕b0,即若源数据B有偶数个1,则P取0,否则取1,也就是保证加上校验位之后的数据编码中有偶数个1。(1)奇偶校验位生成过程[例2-36]要从源部件发送数据01101010到终部件。请写出采用奇校验法的过程。解:P=0⊕1⊕1⊕0⊕1⊕0⊕1⊕0⊕1=1数据增加奇校验位后的编码为:011010101。(2)奇偶校验码的检错过程假设源数据信息和校验位经存储或传送后读出的新编码中数据部分为B’=bn-1’bn-2’…b1’b0’,校验位部分为P”。为了判断源数据B是否在存储和传送后发生了错误,在奇偶校验电路中进行检错。1)首先对B’求新校验码P’。若采用奇校验法:P’=bn-1’
⊕bn-2’⊕…b1’⊕b0’⊕1若采用偶校验法:P’=bn-1’⊕bn-2’⊕…b1’⊕b0’2)计算最终的校验位P*,根据其值判断有无奇偶错P*=P’⊕P”。若P*=1,则表示数据存在有奇数位错。若P*=0,则表示数据正确或有偶数个错。(2)奇偶校验码的检错过程[例2-37]在计算机中采用奇校验法,数据从源部件发送到终部件,校验位在新编码的最后一位。若终部件得到的编码分别为011010100、011010110、011010111,判断这3个数据是否发生了错误。解:①编码011010100检错过程:B’=01101010,P”=0。P’=0⊕1⊕1⊕0⊕1⊕0⊕1⊕0⊕1=1。P*=P’⊕P”=1。该编码有奇数位编码错。 ②编码011010110检错过程:B’=01101011,P”=0。P’=0⊕1⊕1⊕0⊕1⊕0⊕1⊕1⊕1=0。P*=P’⊕P”=0。该编码无错或有偶数个错。③编码011010111检错过程:B’=01101011,P”=1。P’=0⊕1⊕1⊕0⊕1⊕0⊕1⊕1⊕1=0。P*=P’⊕P”=1。该编码有奇数位编码错。2.4.2海明校验码奇偶校验码检错能力差,并且没有纠错能力。如果将数据按某种规律分成若干组,对每组进行相应的奇偶检测,就能提供多位检错信息,从而对错误位置进行定位,并对其进行纠正。海明校验码实质上是一种多重奇偶校验码,是目前广泛被采用的校验法,主要用于存储器中数据存取校验。(1)校验位的位数的确定海明校验码和奇偶校验码一样,都是通过对原校验码和新校验码进行异或操作生成的故障字来判断数据是否发生错误。要实现对某个数据发生的错误进行定位,则故障字应能体现数据可能出现的状态。假定数据位位数为n,校验位位数为k,则故障字位数也是k,k位故障字能够表示的状态有2k种,每种状态用来说明一种情况。数据会出现的状态有无错、n位数据中某一位出错、k位校验位中有一位出错的情况(只考虑干扰造成一位出错的情况),共有1+n+k种情况。所以,n和k必须满足下列关系:2k≥1+n+k(2)分组方式的确定数据位和校验位一起存储构成n+k位的码字。若将校验位穿插在数据位中,使得某位出错时得到的故障字和出错的位置之间存在一个确定的关系,就可以根据故障字直接确定出错的位置,并容易地进行纠正了。根据上述基本思想,我们按以下规则来解释各故障字的值:1)如果故障字各位全0,则表示没有发生错误。2)如果故障字中有且仅有一位为1,则表示校验位中有一位出错。校验位出错不需要纠正。3)如果故障字中有多位为1,则表示有一个数据位出错。出错数据位的位置,由故障字的数值确定。只需根据故障字的值找到出错位进行取反纠正就可以了。(2)分组方式的确定(3)校验位的生成根据故障字和出错情况对应关系表,对12位码字分成了4组,每组进行奇(偶)校验生成一位校验位。在上面的分组方式中,可以看到每个数据位至少参与两组奇(偶)校验位的生成。(3)校验位的生成[例2-39]对8位数据01101010,完成海明校验位生成过程,每组采用偶校验。解:采用前一例题的分组表,则得到校验位和数据位之间的关系,对每组数据进行偶校验运算。P1=M1⊕M2⊕M4⊕M5⊕M7=1P2=M1⊕M3⊕M4⊕M6⊕M7=1P3=M2⊕M3⊕M4⊕M8=0P4=M5⊕M6⊕M7⊕M8=0将数据位和校验位一起存储,得到的码字为M8M7M6M5P4M4M3M2P3M1P2P1=011001010011(4)海明校验码的检错和纠错数据位M和校验位P一起存储或传送后,读出的数据为M’,读出的校验位为P’’。对M’采用同样的分组校验,得到新校验位P’。将P’和P”进行异或得到故障字S。根据故障字可以确定码字是否发生错误,若发生错误,根据故障字确定的错误位置,若是数据位出错,则取反纠错,若是校验位出错可以不进行纠错。海明校验码具有发现两位错,纠正一位错的能力,又称为单纠错码。(4)海明校验码的检错和纠错[例2-40]在终部件处接收到(8,4)海明码数据011001010011,已知校验分组表如表2-4,完成该数据检错以及纠错过程。解:根据海明码字排列顺序,可知M’=01101010,P”=0011。对M’数据进行海明校验位生成过程,生成新校验位P’。P1’=M1’⊕M2’⊕M4’⊕M5’⊕M7’=1P2’=M1’⊕M3’⊕M4’⊕M6‘⊕M7’=1P3’=M2‘⊕M3’⊕M4’⊕M8’=0P4’=M5’⊕M6’⊕M7‘⊕M8’=0将P’和P”异或得到故障字S。S=P’⊕P’’=0011⊕0011=0000根据分组表,故障字为0000,表明所有位都无错。(4)海明校验码的检错和纠错[例2-41]在终部件处接收到(8,4)海明码数据011101010011,已知校验分组表如表2-4,完成该数据检错以及纠错过程。解:根据海明码字排列顺序,可知M’=01111010,P”=0011。对M’数据进行海明校验位生成过程,生成新校验位P’。P1’=M1’⊕M2’⊕M4’⊕M5’⊕M7’=0P2’=M1’⊕M3’⊕M4’⊕M6‘⊕M7’=1P3’=M2‘⊕M3’⊕M4’⊕M8’=0P4’=M5’⊕M6’⊕M7‘⊕M8’=1将P’和P”异或得到故障字S。S=P’⊕P’’=1010⊕0011=1001根据分组表,故障字为1001,表明第9位出错。第9位是数据位M5,所以只需将M5’取反纠正即可得到原正确数据01101010。2.4.3循环冗余校验码循环冗余校验码(CRC),简称循环码,是一种具有检错、纠错能力的校验码。循环冗余校验码常用于外存储器和计算机同步通信的数据校验。奇偶校验码和海明校验码都是采用奇偶检测为手段检错和纠错的,而循环冗余校验则是通过某种数学运算来建立数据位和校验位的约定关系的。(1)校验位的生成循环冗余校验码由信息码n位和校验码k位构成。K位校验位拼接在n位数据位后面,n+k为循环冗余校验码的字长,又称这个校验码(n+k,n)码。n位信息位可以表示成为一个报文多项式M(x),最高幂次是Xn-1。约定的生成多项式G(x)是一个k+1位的二进制数,最高幂次是Xk。将M(x)乘以Xk,即左移k位后,除以G(x),得到的k位余数就是校验位。这里的除法运算是模2除法,即上商的原则是当部分余数首位是1时商取1,反之商取0。然后每一位的减法运算是按位减,不产生借位。(1)校验位的生成(2)CRC检错和纠错CRC码存储或传送后,在接收方进行校验过程,以判断数据是否有错,若有错则进行纠错。一个CRC码一定能被生成多项式整除,所以在接收方对码字用同样的生成多项式相除,如果余数为0,则码字没有错误;若余数不为0,则说明某位出错,不同的出错位置余数不同。对(n,k)码制,在生成多项式确定时,出错位置和余数的对应关系是确定的。(2)CRC检错和纠错(2)CRC检错和纠错CRC码有以下特点:1)任何一个CRC码循环右移一位,仍是CRC码。校验码放在信息位的右边,形成信息码的多余部分,所以称为循环冗余校验码。2)将表中的CRC码按位异或,得到的结果依然是一个CRC码。(2)CRC检错和纠错[例2-44](7,4)循环码中,G(x)=1011时,码字中出错位和余数的对应关系是怎样的?若接收方的码字为1001000,完成数据检错和纠错过程。(2)CRC检错和纠错(3)生成多项式的选取并不是所有的k位多项式都能作为生成多项式。为了能够检错和纠错,选取的生成多项式应具备如下条件:1)当任何一位出错时,都能使余数不为02)不同的位发生错误,得到的余数互不相同3)对余数继续做模2除
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 法律法规汇编与解读行业跨境出海战略研究报告
- 移动语言学习终端行业深度调研及发展战略咨询报告
- 歌唱表演AI应用企业制定与实施新质生产力战略研究报告
- 公路自行车出行行业跨境出海战略研究报告
- 高纯度医药级碱类行业深度调研及发展战略咨询报告
- 2025年便携式有毒有害气体测定仪项目发展计划
- XX发电公司设备维护部管理制度
- 大学生社团活动规划与实施计划
- 数字化转型如何影响企业目标市场规模和绩效-全面剖析
- 广告摄影与视觉效果的融合趋势-全面剖析
- 初中九年级化学酸碱盐练习题
- 员工反腐败与合规培训制度
- 中国绝经管理与绝经激素治疗指南(2023版)解读
- NB∕T 47020~47027-2012 压力容器法兰
- 业主授权租户安装充电桩委托书
- 幼儿园厨房食品留样培训
- 城市道路照明设计标准 CJJ 45-2015
- 北师大版二年级下册数学第三单元测试卷及答案
- IABP操作幻灯-CS-100厂家培训
- 人教版数学四年级上册第五单元 《平行四边形和梯形》 大单元作业设计
- 仓储物流劳务分包合同
评论
0/150
提交评论