2008年下半年计算机软件设计师考试考前指点(3)

    3.海明码

　　计算机体系结构中的海明码也是大家的一大难点。什么是海明码距?

　　事实上，海明码距就是码距，码距就是指两个码字C1与C2之间不同的比特数。

　　例如： 1100与1010的码距为2，具体的对应比较关系如下表所示。

码距求解示意表

　　因为两个码字在D1和D2两位上编码不同，所以码距为2。

　　同理，1111与0000的码距为4。

　　一个编码系统的码距就是整个编码系统中任意两个码字的的最小距离就是该编码系统的码距，例如，一个编码系统只有四个编码分别为：0000，0011，1100，1111。此编码系统中0000与0011的码距为2，是此编码系统的最小码距，所以此编码系统的码距为2。

　　有些书上称码距为海明码距或汉明距，这让一些同学产生了误解，误认为海明码距就是海明编码的码距，这种概念是错误的。海明码距就是码距，它和海明编码没有必然联系。

　　来看一道模拟试题!

　　●在海明码编码方法，若冗余位(检错位)为3位且与错码位置的对应关系为：

　　则冗余位a0的计算公式为__(7)___。

    供选择的答案：

A. a0= a2  a4 a6 

B. a0= a1 a3 a4

C. a0= a4 a5 a3

D. a0= a3 a4 a6

　　该题应该选哪个?

　　大家第一眼看到这个题目时，肯定会有这种疑问，是不是题目出错了，a3和a2的编码弄反了，其实没有弄反，这种写法是允许的。出这个题的原因也就是想让大家清楚一个概念，即海明码的较验位不一定要在1,2,4,8...这些位置上。比如说我们这题中的较验位就放在了最低的三位：a2,a1,a0，而不是a3,a1,a0。　

　　这一点从哪里可以看出呢，从题中给出的表就可以看出来。这里告诉大家一个规则：出错位置码中只有一个”1”的，就是较验码，他的计算公式就是把含有对应位置”1”的信息位进行异或运算。如a2的出错码为100。我们就把出错码包含1**的信息码选出，这样的信息码有：a6,a5,a4，所以a2= a6 + a5 + a4，同样，a0的出错码是：001，我们则把含**1的信息码找出，有a3,a4,a6，所以a0= a3 + a4 + a6。答案选D。

　　在这里，我重点指出该分析中的一句话“出这个题的原因也就是想让大家清楚一个概念，即海明码的较验位不一定要在1,2,4,8...这些位置上。”，可见出题者的初衷就是破除你的定势思维。

　　4.自动机和正规式

　　编译原理中的自动机和正规式等价转化的问题，是历年常考的知识点。下面以软设2005年11月试题28为例来讲解。

　　●某一确定有限自动机(DFA)的状态转换图如下图所示，该DFA接受的字符串集是____(28)___，与之等价的正规式是___(29)___。