海明校验码-软考在线

海明校验码


知识路径： > 计算机科学基础 > 数据的表示 > 校验方法和校验码 > 校验方法和校验码 >
被考次数：1次被考频率：低频率总体答错率：38% 知识难度系数：	由软考在线用户真实做题大数据统计生成
考试要求：熟悉相关知识点：3个

在数据中多加入几个校验位，把数据的每一个二进制位分配在几个奇偶校验组中，当某一位出错后，就会引起有关的几个校验位的值发生变化，这不但可以发现错误，还能指出哪一位出错。

首先要确定校验位的个数。假设校验位个数为r，则它能表示2^r个信息，用其中一个信息表示没有错误，其余2^r^-1个信息指出哪一位错，而错误也可能发生在校验位，因此只有k=2^r-1-r个信息能用于纠正被传送数据的位数。也就是说要满足关系

2^r≥k+r+1

注意：如要能检测与自动校正一位错，并发现两位错，那么还要加一位总校验位，则码距为4，此时应满足

2^r-1≥k+r

按上述不等式计算，可计算出数据位k与校验位r的对应关系，如下表所示。

k与r的对应关系

设海明编码为H_mH_m_-1…H₂H₁，则此海明码的编码规则是：校验位与数据位之和为m，每个校验位P_i在海明码中被分配在位号为2ⁱ^-1的位置，其余各位为数据位依次排列；海明码的每一位码H_i由多个校验位校验，其关系是被校验的每一位的位号等于校验它的各校验位之和。

可以看一个例子。现在要传送一个字节的数据，则k=8，那么r=4，所以海明码的总位数为12，可表示为

H₁₂H₁₁…H₃H₂H₁

4个校验位P₄~P₁对应的编号是H₈、H₄、H₂、H₁。其余为数据位D_i，则有以下排列：

D₈D₇D₆D₅P₄D₄D₃D₂P₃D₁P₂P₁

那么可以知道，D₈处在H₁₂的位置，12=4+8，所以由处在H₄的P₃和处在H₈的P₄检测，这样依次类推，可以得到由P₁检测的数值位有D₁、D₂、D₄、D₅和D₇，若用偶校验，其结果为

P₁=D₁⊕D₂⊕D₄⊕D₅⊕D₇

P₂=D₁⊕D₃⊕D₄⊕D₆⊕D₇

P₃=D₂⊕D₃⊕D₄⊕D₈

P₄=D₅⊕D₆⊕D₇⊕D₈

然后按下面关系对所得的关系实现偶校验，即

S₁=P₁⊕D₁⊕D₂⊕D₄⊕D₅⊕D₇

S₂=P₂⊕D₁⊕D₃⊕D₄⊕D₆⊕D₇

S₃=P₃⊕D₂⊕D₃⊕D₄⊕D₈

S₄=P₄⊕D₅⊕D₆⊕D₇⊕D₈

则校验得到的结果值S₄~S₁能反映海明码出错情况。按S₄S₃S₂S₁的顺序排列形成一个二进制数，转换为十进制数为j，表示H_j出错。

本知识点历年真题：

隶属试卷

题号/题型

题干

难度系数/错误率

   2017年下半年
   网络管理员
   上午试卷综合知识

38%

旗下网站群

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

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

客服

商务合作

客服邮箱service@rkpass.cn