“计算机组成原理”中信息校验码的探讨

刘 昆

（曲靖师范学院计算机科学与工程学院 云南 曲靖 655011）

0 引言

“计算机组成原理”是计算机相关专业的一门核心专业基础课，主要讨论计算机基本的部件构成和组成方式,也包括基本的运算操作原理和单元设计思想、操作方式及其实现，“模拟电子技术”、“数字逻辑”是它的先导课程，它的后继课程如“操作系统”、“编译原理”、“汇编语言程序设计”等，它学好与否直接影响着后继课程的学习，“计算机组成原理”在这些课程之间起着承上启下的作用[1-4]。学习过程中学生普遍感到“计算机组成原理”课程涉及的内容多、抽象、难度大、难学、难懂，“教师难教,学生怕学”的现象在各高校普遍存在，如何把握课程的主线和重点培养学生的学习兴趣、提高教学效果,是从事本课程教学的教师在不断探讨的问题[1]；结合多年“计算机组成原理”的教学经验，对学生难理解的信息校验问题提出实例教学法。

1 信息校验问题

信息校验问题95%的学生对奇偶校验是能正确理解，但是对海明码校验只有50%的学生能正确理解，如何让更多学生顺利理解海明校验码以及其他校验方法，是一直上课教师思考的问题。结合遇到的一个问题，通过这个问题的解决，可以让同学们更好的理解海明校验码。

1.1 问题的提出

问题如下，有1000瓶一模一样的药，其中至多有一瓶是毒药或者没有毒药，任何喝下毒药的生物都会在一星期之后死亡。现在，有10只小白鼠和一星期的时间，如何检验出哪瓶瓶子里有毒药或者证明没有毒药？

1.2 解决问题算法

小白鼠喝了药后，有中毒和不中毒2种情况，一个星期后，有死亡和未死亡2种情况，符合二进制的特征。在二进制中，10位二进制数可以表示的范围为0000000000至1111111111，转换为十进制为0～1023。用10只小白鼠，能表示1000瓶药，通过10只小白鼠喝这1000瓶药，根据小白鼠的死亡情况，能找出哪瓶药是毒药或者能证明没有毒药。具体检测算法如下。

算法：

S1：对1000瓶药，按二进制进行编号，编号为D9D8D7D6D5D4D3D2D1D0，如第1瓶，编号为0000000001，第300瓶，标号为0100101100，第1000瓶，编号为1111101000。

S2：对10只小白鼠进行排序，按排位M9M8M7M6M5M4M3M2M1M0，称为小白鼠序列，Mi表示在排位中的从右向左数过来的第i+1只小白鼠。

S3：小白鼠喝药的方法，用每瓶药编号与小白鼠序列对应，找出药编号中为1的位与该位对应的小白鼠序列中的白鼠，找出来的小白鼠喝该瓶药，如：第1瓶，编号为0000000001，则编号为M0的小白鼠喝第 1 瓶药；第 300 瓶，标号为 0100101100，则编号为 M2，M3，M5，M8的小白鼠喝第300瓶药，同理，第1000瓶，编号为1111101000；为编号M3，M5，M6，M7，M8，M9的小白鼠喝第 1000 瓶药。

S4：一个星期后，看10只编了号的小白鼠的死亡情况。如果一只小白鼠都没有死亡，证明没有毒药，否则，毒药的编号就为小白鼠死亡情况的编号，喝了毒药的小白鼠全都死亡，未喝的就未死亡，即M9M8M7M6M5M4M3M2M1M0中死亡的小白鼠M为1，未死亡小白鼠M的为0，得到的二进制编码即为毒药编号。

1.3 算法分析

算法的每一步是正确的，每一步是可行的，算法是完全正确的。下面思考这样一个问题，如果N瓶药中至多有1瓶毒药或者没有毒药，要找出该瓶毒药或者证明没有毒药，需要多少只小白鼠？根据上面的算法可知，设需要的R只小白鼠，R与N之间必须存在下面的关系式：2R＞＝N（关系式2.1）。只有当R只白鼠所能表示的数大于或等于药的瓶数，才能用小白鼠序列与药的编号对应，否则，小白鼠序列不够对应药的编号。

小白鼠R多大最为合适，如上面算法，如果选取20只小白鼠也一定能找出毒药来，但造成了不必须的浪费，很显然按上面的算法进行，小白鼠编号＞9的小白鼠都不用喝药。所以R与N之间满足下面的关系式也一定能让问题解决：(log2N)+1＞＝R （关系式 2.2）。

R的大小由关系式2.1和关系式2.2决定。

药的编号与十进制的关系是：D9D8D7D6D5D4D3D2D1D0对应的十进制数＝D9×29+D8×28+D7×27+D6×26+D5×25+D4×24+D3×23+D2×22+D1×21+D0×20。 （关系式 2.3）

小白鼠Mi喝的药是药编号中所有的Di位有关，当Di为1时，Mi喝该瓶药，当Di为0时，不喝该瓶药，一只小白鼠大约要喝N/2瓶药，1瓶药最多被R只小白鼠喝，最少被1只小白鼠喝。

1.4 算法转换为信息校验

把1000瓶药转换为计算机中的1000位信息位，在传输过程中至多有1位或者没有信息出错，需要多少位校验位来校验出出错的信息位或者证明信息没有出错，可以使用算法1.1的思想。但是，算法1.1中的S3如何在信息校验中实现，信息位和校验位又如何对应起来呢？Mi和Di通过什么建立起关系呢？解决这个问题的关键是正确理解校验的过程，校验的过程是首先，通过正确的信息位构建校验位，从而得到校验码，其次，传输的过程中，可能某位信息位受到干扰发生错误，通过校验位纠出出错的信息位或者证明在传输过程中没有出错。

根据小白鼠检测毒药的问题，可以知道一只小白鼠Mi是用来检测药品中编号中的Di位，在信息校验中，有奇偶校验能实现生产校验位。奇偶校验是一种校验代码传输正确性的方法。根据被传输的一组二进制代码的数位中“1”的个数是奇数或偶数来进行校验。采用奇数的称为奇校验，反之，称为偶校验。采用何种校验是事先规定好的。通常专门设置一个奇偶校验位，用它使这组代码中“1”的个数为奇数或偶数。若用奇校验，则当接收端收到这组代码时，校验“1”的个数是否为奇数，从而确定传输代码的正确性[1-3]。奇偶校验可以通过异或运算（⊕）实现。

2 结束语

通过这个例子的理解，对海明码校验能进一步理解，能深入的理解，校验是怎么回事，纠错是怎么回事。希望能对信息校验理解有困难的人有一定的帮助。

［1］唐朔飞.计算机组成原理[M].高等教育出版社,2008,1.

［2］徐昆良.《计算机组成原理》课程教学方法探讨[J].中国科技信息,2009.5.1

［3］蒋本珊.计算机组成原理[M].清华大学出版社,2004,3.

［4］王爱英.计算机组成与结构[M].清华大学出版社,2007,7.