申冠豪

郑州大学工学院，河南郑州 450000

1 相关背景介绍

1.1 海明码：（Hanming）

1）海明码的用途：在计算机计算过程中，由于种种原因致使数据在存储过程中出现差错。为了能及时发现错误并及时纠正错误，通常可将原数据配成海明码。

2）海明码的引入：海明码是由Richard Hanming 于1950年提出的，它具有一位纠错能力。由纠错编码理论得知，任何一种编码是否具有检错能力和纠错能力，都与编码的最小距离有关。所谓编码最小距离，是指编码系统中，任意两组合法代码之间的最小二进制位数的差异。

根据纠错理论得：

L-1=D+C 且 D＞=C

即编码的最小距离L越大，则其检测错误的位数越多、纠正错误的位数也越多，且纠错能力恒小于等于检错能力。

1.2 循环冗余校验码：（Cyclic Redundancy Check）

引入：磁表面存储器由于磁介质表面的缺陷、尘埃等原因，致使出现许多个错误位，循环冗余检验码可以发现和纠错数据在存储或传送过程中出现的多位错误代码，因此CRC码在磁介质存储器和计算机通信方面得到广泛应用。

2 例子精讲

2.1 设置一个信息流的海明码

2.1.1 题目设计：分别按“配偶原则”和“配奇原则”设置信息码1100101的海明校验码，要求能指出和纠正一位错。

【解析】

1）确定海明码的校验位的位数：设r为校验位的位数，则整个码字的位数应满足不等式：2r＞=k+r+1，其中k为信息位数，这里k=7，所以可计算出r＞=4，所以至少需要4位校验位。

2）确定校验位的位置：用位号（1-11）为2的权值的那些位，即20，21，22，23的位置作为校验位，分别记作P1,P2,P3,P4,余下的位有效信息位。

3）分组：有4个校验位，须将11位分成4组 ，第i位由校验位序号之和等于i的那些校验位所校验，如第11位D6由P1 (序号为1)，P2 (序号为2)，P4 (序号为8)校验，因为11=1+2+8。

同理D5由P4、P2校验，D4由P4、P1校验，D3由P1、P2、P3校验，D2由P3、P2校验，D1由P1、P3校验，D0由P1、P2校验。

4）校验位的形成（按配偶原则）：

综上题目中所给信息码的能检错一位并纠错一位的海明码为11000101100。

【注】上面第(4)步，如果按配奇原则，则只需将所得每个异或结果取反即可，具体过程如下：

从而得到相应的海明码是11010100111。

为了帮读者方便确定校验位的位数，以下给出了不同代码长度n所需检测位的位数k,如下表所示：

2.2 如何设置一个信息流的循环冗余校验码（CRC）及进行纠错

题目设计：已知有效信息为1101。试用生成多项式G(X)=1011将其编成循环冗余校验码（CRC）；

【解析】

由于生成多项式为4位，故根据题意，最终的CRC码由4位数据位加3位校验位组成。校验位的生成方式为：将数据位乘以2r（其中r的值由生成多项式的位数减1得到）,相当于将数据位右边添加3个0，即1101000，模2除以G（X）,得到的三位余数即为校验码，模2除的过程如下：

故生成的CRC码为1101001。

【注】题中用到了模2除和模2减，其运算规则如下：

模2减:不考虑借位，当两个相同的数相减得0，当两个相异的数相减得1；

模2除:按模2减来计算，每上商一次使余数减少一位。上商的原则是：当余数的首位是1时上1，当余数的首位是0时上0，当余数的位数小于除数时，预算结束。

2.3 已知给出接收到的海明码，若何确定欲传送的信息流

用海明码来发现并纠正一位错。当收到的海明码位010011011100时，试问欲传送的信息是什么？

解析:

首先，应判断接收到的海明码是否出现错误。结合上面的海明码编码过程，校验原理如下：

在接收端分别求：G1,G2,G3,G4.

按配偶原则，通过观察，G2和G3中特有的公共位D6出错，将其取反变为1，并去掉校验位便得到欲传送的信息流位01001111。

3 结论

以上介绍了三大校验码的计算及相关解题过程，该解题思路是比较详细的解题过程，对于考研学员及初学者能够掌握该方法去解题，就已经够用了。

[1]唐朔飞.计算机组成与原理.2版.高等教育出版社，2008，1.

[2]计算机专业基础知识综合复习指南.复旦大学出版社，2010，10.