版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、奇偶校验码,1.奇偶校验概念 奇偶校验码是一种最简单的数据校验码,它的码距等于2,可以检测出一位错误(或奇数位错误),但不能确定出错的位置,也不能检测出偶数位错误。 奇偶校验实现方法是:由若干位有效信息(如一个字节),再加上一个二进制位(校验位)组成校验码。 图2-1奇偶校验码,奇偶校验规律,校验位的取值(0或1)将使整个校验码中“1”的个数为奇数或偶数,所以有两种可供选择的校验规律: 奇校验整个校验码(有效信息位和校验位)中“1”的个数为奇数。 偶校验整个校验码中“1”的个数为偶数。,2.简单奇偶校验,简单奇偶校验仅实现横向的奇偶校验,下表给出几个字节的奇偶校验码的编码结果。最高一位为校验位
2、,其余8位为信息位。在实际应用中,多采用奇校验,因为奇校验中不存在全“0”代码,在某些场合下更便于判别。,2.简单奇偶校验(续), 校验位形成 当要把一个字节的代码D7D0写入主存时,就同时将它们送往奇偶校验逻辑电路,该电路产生的“奇形成”信号就是校验位。它将与8位代码一起作为奇校验码写入主存。 若D7D0中有偶数个“1”,则“奇形成”=1, 若D7D0中有奇数个“1”,则“奇形成”=0。,奇偶校验位的形成及校验电路,图2-2 奇偶校验位的形成及校验电路,2.简单奇偶校验(续),校验检测 读出时,将读出的9位代码(8位信息位和1位校验位)同时送入奇偶校验电路检测。若读出代码无错,则“奇校验出错
3、”=0;若读出代码中的某一位上出现错误,则“奇校验出错”=1,从而指示这个9位代码中一定有某一位出现了错误,但具体的错误位置是不能确定的。,3.交叉奇偶校验,计算机在进行大量字节(数据块)传送时,不仅每一个字节有一个奇偶校验位做横向校验,而且全部字节的同一位也设置一个奇偶校验位做纵向校验,这种横向、纵向同时校验的方法称为交叉校验。 第1字节 1 1 0 0 1 0 1 1 1 第2字节 0 1 0 1 1 1 0 0 0 第3字节 1 0 0 1 1 0 1 0 0 第4字节 1 0 0 1 0 1 0 1 0 1 0 0 1 1 0 0 0,3.交叉奇偶校验(续),交叉校验可以发现两位同时出
4、错的情况,假设第2字节的A6、A4两位均出错,横向校验位无法检出错误,但是第A6、A4位所在列的纵向校验位会显示出错,这与前述的简单奇偶校验相比要保险多了。,海明校验码,海明码是一种可以纠正一位差错的编码。它是利用在信息位为k位,增加r位冗余位,构成一个n=k+r位的码字,然后用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的一位错。它必需满足以下关系式: 2r k+r+1 或 2r n+1,海明校验码,海明码(Hamming Code )编码的关键是使用多余的奇偶校验位来识别一位错误。 码字(Code Word) 按如下方法构建: 1、把所有2的幂次方的数据位标记为奇偶校
5、验位(编号为1, 2, 4, 8, 16, 32, 64等的位置) 2、其他数据位用于待编码数据. (编号为3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17等的位置),海明校验码,3、每个奇偶校验位的值代表了代码字中部分数据位的奇偶性,其所在位置决定了要校验和跳过的比特位顺序。 位置1:校验1位,跳过1位,校验1位,跳过1位(1,3,5,7,9,11,13,15,) 位置2:校验2位,跳过2位,校验2位,跳过2位 (2,3,6,7,10,11,14,15,) 位置4:校验4位,跳过4位,校验4位,跳过4位 (4,5,6,7,12,13,14,15,20,21,
6、22,23,) 位置8:校验8位,跳过8位,校验8位,跳过8位(8-15,24-31,40-47,) ,海明校验码,采用偶校验,如果全部校验的位置中有奇数个1,把该奇偶校验位置为1;如果全部校验的位置中有偶数个1,把该奇偶校验位置为0.,海明校验码,举例说明: 一个字节的数据:10011010 构造数据字(Data Word),对应的校验位留空_ _ 1 _ 0 0 1 _ 1 0 1 0 计算每个校验位的奇偶性 ( ?代表要设置的比特位):,海明校验码,位置1检查1,3,5,7,9,11: ? _ 1 _ 0 0 1 _ 1 0 1 0. 偶数个1,因此位置1设为0,即: 0 _ 1 _ 0
7、 0 1 _ 1 0 1 0 位置2检查2,3,6,7,10,11: 0 ? 1 _ 0 0 1 _ 1 0 1 0. 奇数个1,因此位置2设为1,即: 0 1 1 _ 0 0 1 _ 1 0 1 0,海明校验码,位置4检查4,5,6,7,12: 0 1 1 ? 0 0 1 _ 1 0 1 0. 奇数个1,因此位置4设为1,即: 0 1 1 1 0 0 1 _ 1 0 1 0 位置8检查8,9,10,11,12: 0 1 1 1 0 0 1 ? 1 0 1 0. 偶数个1,因此位置8设为0,即: 0 1 1 1 0 0 1 0 1 0 1 0 因此码字为: 011100101010.,海明校验
8、码,上例中构建了一个码字 011100101010,假定实际接收到的数据 011100101110. 则接收方可以计算出哪一位出错并对其进行更正。方法就是验证每一个校验位。记下所有出错的校验位,可以发现校验位2和8的数据不正确. 错误校验位 2 + 8 = 10, 则位置10的数据出错。一般说来,对所有校验位进行检查, 将所有出错的校验位置相加, 得到的就是错误信息所在的位置.,海明校验码,例1.已知:信息码为: 1 1 0 0 1 1 0 0 (r=4代表冗余位数,即校验码位数) 求:海明码码字。,海明校验码,解:1)把冗余码A、B、C、,顺序插入信息码中,得海明码 码字: A B 1 C
9、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的线性码位是:(相当于监督关系式) 监督关系式的推导: D C B A 1 0 0 0 1 2 0 0 1 0 3 0 0 1 1 4 0 1 0 0 5 0 1 0 1 6 0 1 1 0 7 0 1 1 1 8 1 0 0 0 9 1 0 0 1 10 1 0 1 0 11 1 0 1 1 12 1 1 0 0 根据上面表格得到 A B C D,海明校验码,需要说明的是公式
10、中参与计算的是表格中出现1的那个位 右边是数据位的二进制数,公式中的+表示异或 故此有如下表达式: A-1,3,5,7,9,11;(这里的1 3 5 7 9 11均为A那一列出现1的位) 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)=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,海明校验码,例2.已知:接收的码字为: 1 0 0 1 1 0 0 0 1 1 0 0(r=4代表冗余位数,即校验码位数) 求:发送端的信息码。,海明校验码,解:1)设错误累加器(err)初值=0 2)求出冗余码的偶校验和,并按码位累加到err中: A=(1,0,1,0,1,0)=1 err=err+20=1 B=(0,0,0,0,1,0)=1 err=err+21=3 C=(1,1,0,0,0) =0 err=e
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 小学五年级科学《巧用斜面》教学设计:从现象探究到工程建模
- 高三化学教案:化学平衡常数综合计算的三阶突破
- 七年级语文下册《有为有不为》教学设计:义利抉择与君子养心
- 初中七年级英语 Unit 3 My School Section B 语音教学设计
- 小学五年级美术《色彩的色相》教学设计
- 高中二年级英语UNIT 6晨背Topic Talk主题语境词汇教学设计(北师大版选择性必修第二册)
- 2027届高三英语听力教学设计:语篇重构与策略迁移专题第四十三课时
- 2026事业单位工勤技能-新疆-新疆广播电视天线工三级(高级工)历年参考题库含答案详解
- CN119538150A 一种基于机器学习的大数据异常检测处理方法 (深圳市宝龙数据科技有限公司)
- 湖北省荆州市荆州区2026-2027学年上学期期中质量监测七年级语文试题(文字版含答案)
- 2025年石河子大学马克思主义基本原理概论期末考试真题汇编
- 2026年医疗保险审核部门面试题及应对策略
- 2026-2031中国法兰行业市场前景分析预测报告
- 施工便道临时方案
- 信息科技课程标准2025年版
- 眼科手术并发症处理规定
- 风机叶片覆冰安全培训课件
- 2025云南曲靖市人力资源和社会保障局招聘公益性岗位工作人员3人考试参考题库及答案解析
- 医院服务接待礼仪
- 《中职语文基础知识手册》全套教学课件
- 【MOOC】人工智能与信息社会-北京大学 中国大学慕课MOOC答案
评论
0/150
提交评论