计算机组成原理 第2章 计算机中数据信息的表示.ppt

* * (2) 把M(x)左移k位，得到M(x)? Xk。然后按模2除法，用M(x)? Xk除以G(x)得到k位余数R(x)。即： (3)将M(x)? Xk与余数R(x)作模2相加，即形成循环冗余校验码。 M(x)? Xk＋R(x)＝Q(x)? G(x)＋R(x)＋R(x) ＝ Q(x)? G(x) （模2加） 在模2加的条件下，R(x)＋R(x)＝0。 * * 由于M(x)? Xk＋R(x)可被G(x)整除，所以可作为循环冗余码。 因为M(x)左移k位后空出k位，所以与R(x)的模2加可由简单的拼装来实现。 * * 2.6.1 奇偶校验码 奇偶校验码是一种最简单、最常用的校验码，广泛用于主存的读写校验或ASCII码字符传送过程中的检查。 基本原理：在n位有效信息位上增加一个二进制位作为校验位，构成n十1位的奇偶校验码。校验位P的取值（0或1）使n＋l位的奇偶校验码中“1”的个数为奇数（称为奇校验Odd）或为偶数（称为偶校验Even）。 校验位的位置在有效信息位的最高位之前或者在最低位之后。 * * 例：A6A5A4A3A2A1A0为7位有效信息，加一个校验位P，构成8位的奇偶校验码为 A6A5A4A3A2A1A0P 或 PA6A5A4A3A2A1A0 若采用偶校验，则： Peven＝A6⊕A5⊕A4⊕A3⊕A2⊕A1⊕A0 若采用奇校验，则 Podd ＝ Peven 奇偶校验码的形成 * * 例：求7位信息码1100111的奇校验码和偶校验码（设校验位在最低位）。 解： (1)1100111的奇校验码 因为1100111中“1”的个数为奇，所以奇校验位P＝0，1100111的奇校验码 (2)1100111的偶校验码 因为1100111中“1”的个数为奇，所以偶校验位P＝1，1100111的偶校验码 * * 奇偶校验码的校验方法 若接到一奇校验码中“1”的个数为偶数，或接到一偶校验码中“1”的个数为奇数，则表示有一位出错。 以上面的七位有效信息的奇偶校验码为例： 偶校验错： E＝A6⊕A5⊕A4⊕A3⊕A2⊕A1⊕A0⊕Peven 奇校验错： E＝A6⊕A5⊕A4⊕A3⊕A2⊕A1⊕A0⊕Podd E＝0，表示无错； E＝1，表示校验出错 * * 奇偶校验码的形成电路 * * 奇偶校验码的校验电路 * * 奇偶校验码的校错能力 奇偶校验码只能发现奇数位个错误，而无法发现偶数位个错误，而且即使发现奇数位个错误也无法确定出错的位置；因而无法自动纠正错误。 但由于现代计算机可靠性比较高，出错概率很低，而出错中只有一位出错的概率最高，因此用奇偶校验检测一位出错，能够满足一般可靠性要求。 在CPU与主存的信息传送过程中，奇偶校验被广泛应用。 * * 课堂练习 （1）假定下列字符码中有奇偶校验位，但没有数据错误，采用偶校验的字符码是 。 A. B. C. D. （2）设在7位字符码的最高位加1位奇偶校验位，则下列的奇校验码，出错的是 。 A. B. C. D. 答案: （1）D；（2）D * * 延展：屠夫砍人游戏 有一个屠夫抓了100人，让他们面朝一个方向排成一坚列，然后给这100人分别戴上帽子,帽子只有黑和白两种颜色，屠夫是随机给他们带上的，且自己看不见自己帽子的颜色，也不能回头，只能看到自己前面人的颜色。 他们的视力很好，排最后的那个人(100号)可以看见前面所有人的帽子颜色，他们的听力都很好，最前面的那个人(1号)，可以听见后面所有人说的话。屠夫会从100号开始要他猜自己帽子的颜色，如果猜中，则生；否，则死。然后又问99号，以此类推。这些人只能回答“黑”或“白”两种答案，如果说这两个字以外的字，所有人都得死。他们都很团结，为了能让最多的人生存,他们愿意牺牲。 问题： 为了能让尽量多的人生存，请你帮他们事先想一个方法。 * * 2.6.2 海明校验码 海明校验码的实质 在奇偶校验的基础上，增加校验位的位数，构成多组奇偶校验，以便发现错误并自动纠正错误。 海明校验码校验位数的选择 设有效信息位的位数为n，校验位数为k，则能够检测一位出错并能自动纠正一位错误的海明校验码应满足下面关系： 2k≥n+k+1 由此式可计算出具有检1纠1错能力的海明校验码中n与k的关系，如表2.6所示。 *