首页 > 知识点讲解
       校验方法和校验码
知识路径: > 计算机科学基础 > 数据的表示 > 校验方法和校验码 > 
被考次数:7次     被考频率:中频率     总体答错率:40%     知识难度系数:     
考试要求:熟悉      相关知识点:7个      
        数据在形成、存取和传送的过程中可能产生错误,为减少和避免这类错误,一方面提高计算机硬件本身的可靠性,另一方面在数据编码上找出路,设计出可靠性编码,比如前面说的格雷码。而数据校验码是一种常用的带有发现某些错误或带有自动改错能力的数据编码方法。常用的有奇偶校验码、海明校验码、循环冗余码。一个编码系统中任意两个合法编码(码字)之间不同的二进制数位(bit)数叫这两个码字的码距,而整个编码系统中任意两个码字的最小距离就是该编码系统的码距。为了使一个系统能检查和纠正一个差错,码间最小距离必须至少是3。下表概括了最小距离为1~7的码的纠错和检错能力。
        
        码距与纠错能力
        
               奇偶校验码
               奇偶校验码就是将要传输的数据加一位校验位,下一次读取时验证其合法性。这种方案只能发现一位错或奇数个位错,但不能确定是哪一位错。
               奇偶校验分为奇校验和偶校验两种,假设一个二进制数为a0,a1,a2, …, an-1,则偶校验位an=a0a1a2⊕…⊕an-1,奇校验位
               在实际工作中,还经常采用纵横都加奇偶校验位的编码系统——分组奇偶校验码。
               现在考虑一个系统,它传输若干个长度为m位的信息。如果把这些信息都编成每组n个信息的分组,则在这些不同的信息间,也如对单个信息一样,能够作奇偶校验,n个信息的一个分组排列成矩形式样,并以横向奇偶(HP)及纵向奇偶(VP)的形式编出奇偶校验位。分组奇偶校验码不仅能检测许多形式的错误,并且在给定的行或列中产生孤立的错误时还可对该错误进行纠正。
               海明校验码
               在数据中多加入几个校验位,把数据的每一个二进制位分配在几个奇偶校验组中,当某一位出错后,就会引起有关的几个校验位的值发生变化,这不但可以发现错误,还能指出哪一位出错。
               首先要确定校验位的个数。假设校验位个数为r,则它能表示2r个信息,用其中一个信息表示没有错误,其余2r-1个信息指出哪一位错,而错误也可能发生在校验位,因此只有k=2r-1-r个信息能用于纠正被传送数据的位数。也就是说要满足关系
               2rk+r+1
               注意:如要能检测与自动校正一位错,并发现两位错,那么还要加一位总校验位,则码距为4,此时应满足
               2r-1≥k+r
               按上述不等式计算,可计算出数据位k与校验位r的对应关系,如下表所示。
               kr的对应关系
               设海明编码为HmHm-1H2H1,则此海明码的编码规则是:校验位与数据位之和为m,每个校验位Pi在海明码中被分配在位号为2i-1的位置,其余各位为数据位依次排列;海明码的每一位码Hi由多个校验位校验,其关系是被校验的每一位的位号等于校验它的各校验位之和。
               可以看一个例子。现在要传送一个字节的数据,则k=8,那么r=4,所以海明码的总位数为12,可表示为
               H12H11H3H2H1
               4个校验位P4~P1对应的编号是H8H4H2H1。其余为数据位Di,则有以下排列:
               D8D7D6D5P4D4D3D2P3D1P2P1
               那么可以知道,D8处在H12的位置,12=4+8,所以由处在H4P3和处在H8P4检测,这样依次类推,可以得到由P1检测的数值位有D1D2、D4D5D7,若用偶校验,其结果为
               P1=D1D2D4D5D7
               P2=D1D3D4D6D7
               P3=D2⊕D3⊕D4D8
               P4=D5D6D7D8
               然后按下面关系对所得的关系实现偶校验,即
               S1=P1D1D2D4D5D7
               S2=P2D1D3D4D6D7
               S3=P3D2D3D4D8
               S4=P4D5D6D7D8
               则校验得到的结果值S4~S1能反映海明码出错情况。按S4S3S2S1的顺序排列形成一个二进制数,转换为十进制数为j,表示Hj出错。
               循环冗余校验码
               在串行传送(磁盘、通信)中,广泛采用循环冗余校验码(CRC码)。
               循环冗余校验码的基本原理是:在K位信息码后再拼接R位的校验码,整个编码长度为N位,因此,这种编码又叫(N,K)码。对于一个给定的(N,K)码,可以证明存在一个最高次幂为N-K=R的多项式Gx)。根据G(x)可以生成K位信息的校验码,而Gx)叫作这个CRC码的生成多项式。
               常用的生成多项式如下表所示。
               
               生成多项式
               
               校验码的具体生成过程为:假设发送信息用信息多项式Cx)表示,将Cx)左移R位,则可表示成Cx)×2R,这样Cx)的右边就会空出R位,这就是校验码的位置。通过对多项式Cx)×2R用模2除法除以生成多项式Gx)得到的余数就是校验码。
               模2除法是指在进行除法运算的过程中进行减法运算时不考虑借位的问题,也就是0-0=0,0-1=1, 1-0=1, 1-1=0。
               下表给出了(7, 4)循环码的出错模式。
               
               (7, 4)循环码的出错模式
               如果循环码有一位出错,用Gx)做模2除将得到一个不为0的余数。如果对余数补0继续除下去,将发现一个有趣的结果:各次余数将按顺序循环。例如,第7位出错,余数将为001,补0后再除(补0后若最高位为1,则用除数做模2除取余;若最高位为0,则其最低3位就是余数),得到第二次余数为010。以后继续补0作模2除,依次得到余数为100,011,反复循环,这就是"循环码"名称的由来。这是一个有价值的特点。如果在求出余数不为0后,一边对余数补0继续做模2除,同时让被检测的校验码字循环左移,当出现余数101时,出错位也移到A1位置,可通过异或门将它纠正后在下一次移位时送回A7。这样就不必像海明校验那样用译码电路对每一位提供纠正条件。当位数增多时,循环码校验能有效地降低硬件代价,这是它得以广泛应用的主要原因。
 
本知识点历年真题:
隶属试卷 题号/题型 题干 难度系数/错误率
   2009年上半年
   网络管理员
   上午试卷 综合知识
第4题
选择题
(4)既具有检错功能又具有纠错功能。

40%
 
 相关知识点:
 
软考在线指南
优惠劵及余额
在线支付
修改密码
下载及使用
购买流程
取消订单
联系我们
关于我们
联系我们
商务合作
旗下网站群
高级资格科目
信息系统项目管理师 系统分析师
系统架构设计师 网络规划设计师
系统规划与管理师
初级资格科目
程序员 网络管理员
信息处理技术员 信息系统运行管理员
中级资格科目
系统集成项目管理工程师 网络工程师
软件设计师 信息系统监理师
信息系统管理工程师 数据库系统工程师
多媒体应用设计师 软件评测师
嵌入式系统设计师 电子商务设计师
信息安全工程师
 

本网站所有产品设计(包括造型,颜色,图案,观感,文字,产品,内容),功能及其展示形式,均已受版权或产权保护。
任何公司及个人不得以任何方式复制部分或全部,违者将依法追究责任,特此声明。
本站部分内容来自互联网或由会员上传,版权归原作者所有。如有问题,请及时联系我们。


工作时间:9:00-20:00

客服

点击这里给我发消息 点击这里给我发消息 点击这里给我发消息

商务合作

点击这里给我发消息

客服邮箱service@rkpass.cn


京B2-20210865 | 京ICP备2020040059号-5 |京公网安备 11010502032051号 | 营业执照 | Copyright ©2000-2023 All Rights Reserved 软考在线版权所有