计算机系统结构概述(第一节).ppt

《计算机系统结构概述(第一节).ppt》由会员分享，可在线阅读，更多相关《计算机系统结构概述(第一节).ppt（77页珍藏版）》请在金锄头文库上搜索。

1、计算机组成原理计算机组成原理 杨 健【课程说明课程说明】q课程性质：专业必修课。知识面广、内容多、难度大而且更新快，在计算机科学中占重要地位。q内容：全面介绍计算机单处理机系统的组成和工作原理。q先行课：电子技术、数字逻辑。q建议教材：张基温 计算机组成原理教程清华大学出版社q参考教材：白中英 计算机组成原理科学出版社【课程安排课程安排】q学分：3学分q课时：54学时，根据2009年的教学计划进行课堂讲授。q成绩计算方法考勤：占总成绩10(抽查35次考勤)平时作业：占总成绩20期末笔试：占总成绩70【各章节课时安排各章节课时安排】q课程讲授第1章 计算机系统结构概述10学时第2章 存储系统12

2、学时第3章 输入输出及其控制10学时第4章 总线系统5学时第5章 处理器12学时第6章 计算机系统的发展5学时q实验环节： 结合“信息管理与信息系统”专业的实际要求，本课程原则上无实验，但可跟据实际情况安排少量实验。第1章 计算机系统结构概述1.1 元器件级的计算机结构-开关逻辑1.2 功能模块级的计算机组成1.3 指令系统级的 CPU界面1.4 操作系统级的计算机系统界面1.5 计算机系统评价与发展习题 1.1 元器件级的计算机结构-开关逻辑1.1.1 数据的开关表示1.1.2 逻辑运算的开关电路1.1.3 算术运算的逻辑电路基础 1.1.1 数据的开关表示 一只开关只有“开”和“关”两种状

3、态。通常把这两种状态分别用符号“0”和“1”表示。计算机工作中所需要的一切数据信息，都是用开关状态的组合表示的，或称为用“0”和“1”编码表示的。 1. 数值数据的0、1编码 通常人们使用的是十进制计数法。十进制计数法有两个主要特点：q采用0，1，2，3，4，5，6，7，8，9十个符号表示数字；q十进制的位权是10的幂，即10i, 10i-1, , 103, 102, 101, 100, 10-1, 10-2, 10-3, 位位权权即位置本身所具有的数量级别。它使一个表数符号在不同的位置上，所代表的数值不同。 与之对应，用电子开关表示数值，只能使用两个符号：0和1，所采用的进位计数法称为二进制

4、。二进制的位权是2的幂幂，即 2i, 2i-1, , 23, 22, 21, 20, 2-1, 2-2, 2-3, 表1.1为几个十进制数与二进制数之间的对应关系。 显然，与十进制的“逢十进一”相似，二进制也具有“逢二进一”的特征。 下面介绍十进制数与二进制数之间的一般转换关系。 （1）二十 (BD) 进制转换 规则：各位对应的十进制值之和；各位对应的十进各位对应的十进制值之和；各位对应的十进制值为系数与其位权之积制值为系数与其位权之积。 例1.1.1 101.11101B ? D 解：位 权：22 21 20 2-1 2-2 2-3 2-4 2-5 二进制数：1 0 1 . 1 1 1 0

5、1计算：4 +0 +1+0.5+0.25+0.125+0+0.03125=5.90625D (2) 整数十二转换 规则：连续连续“（向左）除（向左）除2 2取余，直到取余，直到0”0” 例1.1.2 29D ? B 解： (3) 小数十二进制转换 规则：连续连续“（向右）乘（向右）乘2 2取整，直到取整，直到0”0” 连续连续“除除2取余取余”0 1 3 7 14 29结束结束 1 1 1 0 1十进制余数序列即对应的二进制数十进制余数序列即对应的二进制数所以所以 29D = 11101B 有时，小数十二转换，会出现转换不完的情况。这时可按“舍0取1”（相当于四舍五入）的原则，取到所需的位数。

6、 例例1.1.3 0.375D= ? B解解:小数部分连续小数部分连续“乘乘2 2取整取整”0.3750.751.501.00结束结束0.011所以所以 0.375D=0.011B 注意：第一个注意：第一个0与小数点要照写。与小数点要照写。 例1.1.4 0.24D?B 解： 连乘 0.24 0.48 0.96 1.92 1.84 1.68 1.36 0.72 1 .44 取整 0. 0 0 1 1 1 1 0 1 结果 0. 0 0 1 1 1 1 1 舍入 (4) 整数小数混合十二进制转换 规则：从小数点向左、右，分别按整数、小数规则进行从小数点向左、右，分别按整数、小数规则进行。 例1.

7、1.5 29.375D?B 解： 连续“除取余” 连续取小数部分“乘取整” 0 1 3 7 14 29 . 375 0 .75 1.50 1.00 1 1 1 0 1 . 0 1 1 所以 29.375D11101.011B 2. 二进制运算法则 （1）加法规则：“逢逢2 2进进1 1” 0 + 0 = 0 1 + 0 = 0 + 1 = 1 1 + 1 = 10 例1.1.6 101.01+110.11? 解： 1 0 1 . 0 1 + 1 1 0 . 1 1 1 1 0 0 . 0 0 所以 101.01+110.111100.00 （2）减法规则：“借借1 1当当2 2” 0 0 =

8、0 1 0 = 1 1 1 = 0 10 1 = 1 例1.1.7 1100.00-110.11? 解： 1 1 0 0 . 0 0 1 1 0 . 1 1 1 0 1 . 0 1 所以 1100.00-110.11101.01 （3）乘法规则 0 0 = 0 1 0 = 0 1 = 0 1 1 = 1 显然，二进制数乘法比十进制数乘法比简单多了。 例1.1.8 10.101101? 解： 1 0 . 1 0 1 被乘数 1 0 1 乘数 1 0 . 1 0 1 0 0 0 . 0 0 部分积 1 0 1 0 . 1 1 1 0 1 . 0 0 1 积 所以 10.1011011101.001

9、 在二进数运算过程中，由于乘数的每一位只有两种可能情况，要么是0，要么是 1。因此部分积也只有两种情况，要么是被乘数本身，要么是0。 根据这一特点，我们可以把二进制数的乘乘法法归结为移移位位和加加法法运运算算。即通过测试乘数的每一位是0还是1，来决定部分积是加被乘数还是加零。 除除法法是乘法的逆运算，可以归结为与乘法相反方向的移移位位和减减法法运算。因此，在计算机中，只要具有移位功能的加法减法运算器，便可以完成四则运算。 3. 八进制（Octal）、十六进制（Hexadecimal）和二-十进制（1）八进制和十六进制 二进制数书写太长，难认、难记。为了给程序员提供速记形式，使用中常用八进制和十

10、六进制作为二进制的助记符形式。 八进制记数符：0，1，2，3，4，5，6，7 十六进制记数符：0，1，2，3，4，5，6，7，8，9，A(a)，B(b)，C(c)，D(d)，E(e)，F(f) 将二进制数由由小小数数点点起起，向向两两侧侧分别以以每每3 3位位划划一一组组（最最高高位位与与最最低低位位不不足足3 3位位以以0 0补补）。每一组便为一个八进制数。同理以4位为一组，每一组便为一个十六进制数。 例1.1.9 10110 1110.1111B ?H 解：补零 0001 0110 1110 . 1111 1 6 E F 所以 10110 1110.1111B16E.FH 从根本上来说，计

11、算机内部进行的运算，实际上是二进制运算二进制运算。但是，把十进制数转换为二进制数，并使用二进数计算的结果，转换为十进制数，在许多小型计算机中所花费的时间是很长的。在计算的工作量不大时，数制转换所用时间会远远超过计算所需的时间。在这种情况下，常常采用二-十进制数。 （2）二-十进制（BCD）码 二-十进制（BCD）码也称为二进制编码形式的十进制数，即用4位二进制数来表示一位十进制数，这种编码形式可以有多种，其中最自然、最简单的一种方式为 8-4-2-1码，也称压缩的压缩的BCDBCD码码。即这4位二进制数的权，从左往右分别为8，4，2， 1。 例1.1.10 3579 D? BCD 解： 3 5

12、 7 9 0011 0101 0111 1001 所以 3579D 0011 0101 0111 1001 BCD 4位二进制数可以表示16种状态，而每位十进数只可能有10种状态。因此用4位二进制数表示一位十进制数时有6种状态是多余的，称为非法码。因此使用BCD码的运算过程中，要用状态寄存器中的有关位表示产生的进位或借位（称半进位），通过对半进位的测试，决定是否需要对运算结果加以调整。 相对于压缩的BCD码，把用8位二进制数表示的一位十进制数的编码称为非非压压缩缩的的BCDBCD码码，这时高4位无意义，低4位是一个BCD码。数字的ASCII码中的高4位是0011(3)，低4位正好是一个BCD码

13、。所以，数字的ASCII码也是一种非压缩的BCD码。4. 机器数 在计算机中不仅要用0，1编码的形式表示一个数的数值部分，正、负号也要用0，1编码来表示。一般用数的最高位（最左边一位）（MSB，Most Significant Bit）表示数的正负，如： MSB0 表示正数，如+1011表示为01011； MSB1 表示负数，如-1011表示为11011。 一个数在机器内的表示形式称为机机器器数数。它把一个数连同它的符号在机器中被0，1编码化了。这个数本身的值称为该机器数的真真值值。上边的“01011”和“11011”就是两个机器数。它们的真值分别为+1011和-1011。 当然，在不需要考虑

14、数的正、负时，是不需要用一位来表示符号的。这种没有符号位的数，称为无符号数无符号数。由于符号位要占用一位，所以用同样字长，无符号数的最大值比有符号数要大一倍。如字长为4位时，能表示的无符号数的最大值为1111，即15，而表示的无符号数的最大值为111，即7。 直接用一位用0，1码表示正、负，而数值部分不变，在运算时带来一些新的问题： （1） 两个正数相加时，符号位可以同时相加：0 + 00，即和仍然为正数，没有影响运算的正确性。 （2） 一个正数与一个负数相加，和的符号位不是两符号位直接运算的值：0 + 11，而由两数的大小决定。即和的符号位是由两数中绝对值大的一个数所决定的。 （3） 两个负

15、数相加时，由于1 + 110，因此和的符号也不是由两符号位直接运算的结果所决定。 简单地说，用这样一种直接的形式进行加运算时，负负数数的的符符号号位位不不能能与与其其数数值值部部分分一一道道参参加加运运算算，而必须利用单独的线路确定和的符号位。这样使计算机的结构变得复杂化了。为了解决机器内负数的符号位参加运算的问题，引入了反码和补码两种机器数形式，而把前边的直接形式称为原码原码。 （1）反码 对正数来说，其反码和原码的形式是相同的对正数来说，其反码和原码的形式是相同的。即 X原X反 对负数来说，反码为其原码的数值部分的各位变反对负数来说，反码为其原码的数值部分的各位变反 比如： X X原 X反

16、 +1101 01101 01101 -1101 11101 10010 取反 反码运算要注意3个问题：q反码运算时，其符号位与数值一起参加运算。q反码的符号位相加后，如果有进位出现，则要把它送回到最低位去相加。这叫做循环进位。q反码运算有如右性质：X反 + Y反X + Y反。 例1.1.11 已知： X0.1101 Y-0.0001 求： X + Y? 解： X反0.1101 正数的反码与原码相同 + Y反1.1110 10.1011 +循环进位 1 X + Y反0.1100 所以 X + Y0.1100 例 1.1.12 已知：X-0.1101 Y-0.0001 求： X + Y ? 解：

17、 X反1.0010 + Y反1.1110 11.0000 +循环进位 1 X + Y反1.0001 所以 X + Y -0.1110 （2）补码 对对正正数数来来说说，其其补补码码和和原原码码的的形形式式是是相相同同的的:X原X补；对对负负数数来来说说，补补码码为为其其反反码码( (数数值值部部分分各各位位变反变反) )的末位补加的末位补加1 1。例如 X X原 X反 X补 +1101 01101 01101 01101 -1101 11101 10010 10011 取反 补1 这种求负数的补码的方法，在逻辑电路中实现起来是很容易的。 不论对正数，还是对负数，反码与补码具有下列相似的性质：X

18、反反X原 X补补X原 例1.1.13 原码、补码的性质举例： 变反 X反反 X X原 变反 X反 加1 X补 变反 XX补 反 加1 X补补 +1101 01101 01101 01101 01101 01101 -1101 11101 10010 10011 11100 11101 采用补码运算也要注意3个问题 补码运算时，其符号位也要与数值部分一样参加运算。补码运算时，其符号位也要与数值部分一样参加运算。 符号运算后如有进位出现，则把这个进位舍去不要。符号运算后如有进位出现，则把这个进位舍去不要。 补码运算有如右性质：补码运算有如右性质： XX补补 + + YY补补 X + YX + Y补

19、补 例 1.1.14 已知：X0.1101 Y-0.0001 求：X + Y ? 解： X补0.1101 + Y补1.1111 X +Y补10.1100 舍去不要 所以 X + Y0.1100 例 1.1.15 已知：X-0.1101 Y-0.0001 求： X + Y ? 解： X补1.0011 + Y补1.1111 X+Y补11.0010 舍去不要 所以 X + Y-0.1110 采用反码和补码，就可以基本上解决负数在机器内部数值连同符号位一起参加运算的问题。 (3) 移码 移码是在补码的最高位加移码是在补码的最高位加1 1，故又称增码，故又称增码。 例1.1.16 几个数的4位二进制补码

20、和移码 真值 补码 移码 +3 0011 1011 0 0000 1000 -3 1101 0101 显然，补码和移码的数值部分相同，而符号位相反。 例1.1.17 几个典型数的原码、反码、补码和移码表示。 由表1.2可见，字长为8位时，原码、反码的表数范围为+127-127，而补码的表数范围为+127-128。这是因为负数的补码是在其反码上加1的缘故。 从表中还看到： 反码有反码有+0+0与与-0-0之分。之分。 从从+128+128到到-128-128，数数字字是是从从大大到到小小排排列列的的。只只有有移移码码能能直直接接反反映映出出这这一一大大小小关关系系。因因而而移移码码能能像像无无符

21、符号号数数一一样样直直接接进进行大小比较行大小比较。 5. 机器数的浮点与定点表示法 （1）机器数的浮点表示法 一个十进制数可以表示为： N13.141590.3141591010.0314159102 同样，一个二进制数可以表示为： N20.011B0.110B2-10.0011B21 一般地说，一个任意二进制数N可以表示为： N2EM 式中： E数N的阶码； M数N的有效数字，称为尾数。 当E变化时，数N的尾数M中的小数点位置也随之向左或向右浮动。因此将这种表示法称为数的浮点表示法。对于这样一个式子，在计算机中用约定的4部分表示，如图1.1所示。其中，Ef，S分别称为阶码E和尾数M的符号位

22、。 由于不同的机器的字长不同，采用浮点表示法时，要预先对上述4部分所占的二进制位数加以约定，机器才可以自动识别。按照IEEE 754:1985标准，常用的浮点数的格式如图1.2所示。 它把尾数的符号位安排在最高一位。阶阶符符采采用用隐隐含含形形式式，即即采采用用移移码码方方法法来来表表示示正正负负指指数数。移码方法对两个指数大小的比较和对阶操作都比较方便，因为阶码域值大者其指数值也大。采用这种方式时，将浮点数的指数真值e变成 阶 码 E时 ， 应 将 指 数 e加 上 一 个 固 定 的 偏 移 量127(01111111),即E=e+127. 对32位的浮点数（即单精度格式），S占1位，E占

23、8位，M占23位；对64位的浮点数（即双精度格式），S占1位，E占11位，M占52位。 在尾数一般为小数。为了提高表数精度，充分利用尾数的有效位数，在浮点机中常采用数的规格化表示法。即当尾数不为当尾数不为0 0时，其绝对值应时，其绝对值应 0.50.5，否则应修改阶码，否则应修改阶码。使非规格化数变为规格化数的过程，称为数的规格化处理数的规格化处理。 IEEE754标准约定，在小数点的左边有一隐含位M0。因而，单精度浮点数尾数部分实际上是24位，双精度浮点数尾数部分实际上是53位，S的值只取0或1。下面为真值以及E，M，M0之间的关系。E=0且M=0，则N=0，即M0=0E=0且 M0， 为

24、非 规 格 化 数 ， N=(-1)S2-126(0.M)，即M0=01 E 254，为规格化数，N=(-1)S2E-127(1.M)，即M0=1E=255且M=0，则为无穷大数，N=(-1)SE=255且M0，则为非数值数 采采用用浮浮点点法法进进行行数数的的乘乘法法运运算算时时，其其尾尾数数相相乘乘除除，其其阶阶码码相相加加减减；进进行行加加减减运运算算时时，必必须须使使参参加加运运算算的的数数的的阶阶码码相相同同，即即必必须须进进行行对对阶阶处处理理，然然后后进行尾数的加减运算进行尾数的加减运算。 （2）机器数的定点表示法 如果让机器中所有的数都采用同样的阶码aj，就有可能将此固定的aj

25、略去不表示出来。这种表数方式称为数数的的定定点点表表示示法法。其中所略去的aj称为定定点点数数的的比比例例因因子子。因此一个定点数便简化为由如下两部分来表示：Sf与S。 从理论上讲，比例因子的选择是任意的，也就是说尾数中的小数点位置可以是任意的。但是为了方便，一般都将尾数表示成纯小数或纯整数的形式。另外，对比例因子的选择还有一些以下技术上的要求。 (1) 比例因子的选择不能太大。比例因子选择太大，将会使某些数丢掉过多的有效数字，影响运算精度。如数N0.11，机器字长4位，则： 当比例因子为2时，S0.011； 当比例因子为22时，S0.001； 当比例因子为23时，S0.000。 (2) 比例

26、因子也不可选得太小。太小了就有可能使数超过了机器允许的范围，即尾数部分的运算所产生的进位影响了符号位的正确性。如0111+01011100，正数相加的结果变成了负数。 当字长一定时，浮点表示法能表示的数的范围比定点数大，而且阶码部分占的位数越多，能表示的数的范围就越大。但是，由于浮点数的阶码部分占用了一些位数，使尾数部分的有效位数减少，数的精度亦降低。为了提高浮点数的精度，就要采用多字节形式。 6. 非数值数据的0、1编码 计算机不仅能够对数值数据进行处理，还能够对文本和其它非数值数据信息进行处理。非数值数据是指不能进行算术运算的数据，包括文字、图形、图象和声音等。 为了处理文本，需要一个完整

27、而足够的字符集，这个字符集最少应包括： 26个小写字母； 26个大写字母； 约25个特殊字符，如：，+，-，|，# 等； 10个数字码：0，1，2，3，4，5，6，7，8，9。 共计87个字符。这87个字符须用7位“0”，“1”进行编码。常用的编码形式有两种：美国信息交换标准代码（ASCII）和扩展二十进制交换代码（EBCDIC），所有小型计算机和微型计算机都采用ASCII码。 表1.3为ASCII码字符表，它用8位来表示字符代码。其基本代码占7位，第8位用作奇偶校验位，通过对奇偶校验位设置“1”或“0”状态，保持8位字节中的“1”的个数总是奇数（称奇校验）或偶数（称为偶校验），用以检测字符在

28、传送（写入或读出）过程中是否出错（丢失1）。 ENQ（查询）、ACK（肯定回答）、NAK（否定回答）等，是专门用于串行通信的控制字符。 在码表中查找一个字符所对应的ASCII码的方法是：向上找b6b5b4向左找b3b2b1b0。例如，字母J的ASCII码 中 的 b6b5b4为 100B(5H)， b3b2b1b0为1010B(AH)。因此，J的ASCII码为1001010B(5AH)。 7. 数据传输中的差错校验 计算机系统工作过程中，由于脉冲噪声、串音、传输质量等原因，有时在信息的形成、存取、传送中会造成错误。为减少和避免这些错误，一方面要提高硬件的质量，另一方面可以采用抗干扰码，其基本思

29、想是按按一一定定的的规规律律在在有有用用信信息息的的基基础础上上再再附附加加上上一一些些冗冗余余信信息息，使使编编码码在在简简单单线线路路的的配配合合下下能能发发现现错错误误、确确定定错错误误位位置置甚甚至至自自动动纠纠正正错错误误。通常，一个k位的信息码组应加上r位的校验码组(奇偶校验码的r=1)，组成n位抗干扰码字(在通信系统中称为一帧)。例如，奇偶校验码是在信息码之外再加上一位校验位，借奇偶校验线路来检测码字是否合法。 抗抗干干扰扰码码可可分分为为检检错错码码和和纠纠错错码码。所谓检检错错码码是是指指能能自自动动发发现现差差错错的的码码。所谓纠纠错错码码是是指指不不仅仅能能发发现现差差错

30、错而而且且能能自自动动纠纠正正差差错错的的码码。不过应该指出，这两类码之间并没有明显的界限。纠错码也可用来检错，而有的检错码可以用来纠错。抗干扰码的编码原则是在不增加硬件开销的情况下，用最小的校验码组，发现、纠正更多的错误。一般说来，校验码组越长，其发现、纠正错误的能力越强。 （1）奇偶校验码 通常奇偶校验以字符为单位进行分组。如传送ASCII码时，每传送7位的信息码组，都要传送一位附加的冗余校验位；该校验位可以作为码字的最高位，也可以作为码字的最低位，使得整个字符码组（共8位）中1或0的数目为奇数或偶数。对对于于奇奇校校验验，1(1(或或0)0)的的数数目目为为奇奇数数为为合合法法码码；为为

31、偶偶数数，便便是是非非法法码码。对对于于偶偶校校验验，1(1(或或0)0)的的数数目目为为偶偶数数为为合合法法码码；为为奇奇数数，便是非法码便是非法码。 由此，可以设计出校验逻辑(偶校验)： P= C6 C5 C4 C3 C2 C1 C0P （ P为校验位值） P=0，无错；P=1，有错。 奇偶校验能检测出传输中任意奇数个错误，但不能检测出偶数个错误。 （2）海明码 由前面的讨论可以发现，ASCII码是没有检错能力的。因为一个ASCII码出现一位错时，就变成了另一个合法的ASCII码。我们称ASCII码的码距为1。而对于横向奇偶校验或纵向奇偶校验码来说，由任意一个码字变为另一个码字，至少要变化

32、两位，我们称其码距为2。码距为2只能检测出代码中的一位错。码距，就是一种编码系统中两个任意合法码之间的最少二进制位数差异。 纠错理论证明：码距越大，检错和纠错能力越强，并且有关系 L - 1 = D + C 其中，L为码距，D为可以检出的错误位数，C可以纠正的错误位数，并且有 DC。显然，如果能在数据码中增加几个校验位，将数据代码的码距均匀地拉大，并且把数据的每一二进制位分配在几个奇偶校验组中。当某一位出错后，会引起几个校验位的值的变化。这样，不但能够检测出错误，而且能够为进一步纠错提供依据。海明码就是根据这一理论，由Richad Hamming于1950年提出的一种很有效的校验方法。 假设校

33、验码组的为r位，则它共有2r个状态，用其中一个状态指出“无错”，其余的2r-1个状态便可用于错误定位。设有效信息码组为k位，并考虑到错误也可能发生在校验位，则须定位状态共有k+r个。也就是说，要能充分地进行错误定位，应有关系： 2r-1k+r 由此，可以计算出表1.4中的值。 若编成的海明码为HmHm-1H2H1，则海明码的编码规律为： (a) 校验位分布：在m位的海明码中，各校验位分布在位号为21的位置，即校验位的位置分别为1,2,4,8,，其余为数据位。数据位按原来的顺序关系排列。如有效信息码为D5D4D3D2D1，则编成的海明码为D5P4D4D3D2P3D1P2P1，其中Pi-为第 i个

34、校验位。 (b) 校验关系：海明码的每一位Hi要有多个校验位校验。校验关系是被校验位的位号为校验位的位号之和。如D1(位号为3)要由P2与P1两个校验位校验，D2(位号为5)要由P3(位号为4)与P1两个校验位校验，D3(位号为6)要由P2与P3两个校验位校验，D4(位号为7)要由P1、P2、P3三个校验位校验。 （3）循环冗余校验码（CRC） 循环冗余校验码(Cyclic Redudancy Check)简称CRC(循环码)，是一种能力相当强的检错、纠错码，并且实现编码和检码的电路比较简单，常用于串行传送(二进制位串沿一条信号线逐位传送)的辅助存储器与主机的数据通信和计算机网络中。循环冗余校

35、验码是一种基于模2运算建立编码规律的校验码。它可以通过模2运算来建立有效信息和校验位之间的约定关系，即要求k=n+r位的某数能被一个约定的数除尽，其中n是待编码的有效信息，r是校验位设待编码的有效信息以多项式M(x)表示，用约定的一个多项式G(x)去除，一般情况下得到一个商Q(x)和余数R(x)： M(x)=Q(x)G(x)+R(x) M(x)-R(x)=Q(x)G(x)显然，将M(x)减去余数R(x)就必定能G(x)所除尽。因而可以设想让M(x)-R(x)作为编好的校验码送往目标部件，当从目标部件取得校验码时，仍用约定的多项式G(x)去除，若余数为0，表明该校验码正确；若余数不为0，表面有错

36、，再进一步由余数值确定出哪一位出错，从而加以纠正。 循循环环码码是是指指通通过过某某种种数数学学运运算算实实现现有有效效信信息息与与校验位之间的循环校验校验位之间的循环校验( (而海明码是一种多重校验而海明码是一种多重校验) ) （a）编码步骤 步步骤骤1 1：将待编码的n位信息码组Cn-1Cn-2CiC2C1C0表达为一个n-1阶的多项式M(x) M(x)=Cn-1xn-1+Cn-2xn-1+Cixi+C1x1+C0x0 步步骤骤2 2：将信息码组左移k位，成M(x)xk，即成n+k位的信息码组 Cn-1+ kCn-2+ kCi+ kC2+ kC1+ kCk0000。 步步骤骤3 3：用k+

37、1位的生成多项式G(x)对M(x)xk作模2除，得到一个商Q(x)和一个余数R(x)。显然，有 M(x)xk=Q(x)G(x)+R(x) 生成多项式G(x)是预先选定的。关于它，稍后再进行介绍。这里先介绍一下模2除。 模模2 2运运算算是是指指依依按按位位模模2 2加加减减为为基基础础的的四四则则运运算算，运运算算时时不不考考虑虑进进位位和和借借位位。模2加减的规则为：两数相同为0，两数相异为1。 模2除，就是求用2整除所得到的余数。每求一位商应使部分余数减少一位。上商的原则是：当部分余数最高位为1时，商取1；当部分余数最高位为0时，商取0。如 101 .商商 101 10000 部分余数最高

38、位为部分余数最高位为1 101 010 部分余数最高位为部分余数最高位为0000 100 部分余数最高位为部分余数最高位为1 101 01 余数余数 步骤步骤4 4：将将左移k位的待编码有效信息与余数R(x)作模2加，即形成循环冗余校验码。 例1.1.18 对四位有效信息1100作循环冗余校验码，选择生成多项式G(x)为1011(k=3)。 步骤1：M(x)=x3+x2=1100 步骤2：M(x)x3=x6+x5=1100000 (k=3，即加了3个0) 步骤3：模2除， M(x)xk/G(x)=1100000/1011=1110+010/1011，即R(x)=010 步骤4：模2加，得到循环

39、冗余校验码 Q(x)G(x)=M(x)x3 +R(x)=110000+010=1100010 （b）纠错原理 由于M(x)xk=Q(x)G(x)+R(x)，根据模2加的规则 M(x)xk+R(x)=M(x)xk-R(x)=Q(x)G(x) 所以合法的循环冗余校验码应当能被生成多项式整除。如如果循环冗余校验码不能被生成多项式整除，就说明出现了信息果循环冗余校验码不能被生成多项式整除，就说明出现了信息差错。并且，有信息差错时，循环冗余校验码被生成多项式整差错。并且，有信息差错时，循环冗余校验码被生成多项式整除所得到的余数与出错位有对应关系，因而能确定出错位置除所得到的余数与出错位有对应关系，因而能

40、确定出错位置。表1.5为例2.3.1所得到的循环冗余校验码的出错模式。 进一步分析还会发现，当循环冗余校验码有一位出错时，用生成多项式作模2除将得到一个不为0的余数，将余数补0继续作模2除又得到一个不为0的余数，再补0再作模2除，于是余数形成循环。对上例，形成001,010,100,011,110,111,101；001,010,100,的余数循环。这也就是“循环码”的来历。 （c）关于生成多项式 并不是任何一个多项式都可以作为生成多项式。从检错和纠错的要求出发，生成多项式应能满足下列要求： 任何一位发生错误都应使余数不为任何一位发生错误都应使余数不为0 0。 不同位发生错误应使余数不同。不同

41、位发生错误应使余数不同。 对余数继续作模对余数继续作模2 2运算，应使余数循环运算，应使余数循环。 生成多项式的选择主要靠经验。有三种多项式已经成为标准，具有极高的检错率。它们是： CRC-12= x12+x11+x3+x2+x+1 CRC-16= x16+x15+x2+1 CRC-CCITT= x16+x12+x5+11.1.2 逻辑运算的开关电路 1. 用开关实现门电路 传统的逻辑学是二值逻辑学，它研究命题在“真”、“假”两个值中取值的规律。0，1码只有两个码，因此特别适合用做逻辑的表达符号。通常用用“1”“1”表示表示“真真”，用，用“0”“0”表示表示“假假”。 逻辑代数是表达语言和思

42、维逻辑性的符号系统。逻辑代数中最基本的运算是“与”、“或”、“非”。 （1）“与”运算和“与门” 观察图1.3(a)所示的电路可以看出，只有开关A与B都闭合时，X才是高电位。这种逻辑关系称之为逻辑“与”，可以表达为： XA and B 或 XA B实现“与”逻辑功能的电路单元叫“与门”，在电路中用图1.3(b)所示的符号表示。其真值表见图 1.3(c) 。 所谓真值表，是指由自变量的各种取值组合而成与函数值之间的对应关系表格。函数取值为“1”的项数，表明函数运算多项式中的项数。如“与”的运算多项式中只含1项。它反映了函数逻辑“与”有如下一些特点： 111 100 010 000 它与“乘”相似

43、，所以也称“逻辑乘”，相应地也可以记为： XAB = A B （2）“或”运算和“或门” 观察图1.4(a)所示的电路可以看出，只要开关A或B闭合，X便是高电位。这种逻辑关系称为逻辑“或”，表示为： XA or B XAB 能实现“或”逻辑功能的电路单元叫“或门”，在电路中用图1.4(b)所示的符号表示。其真值表见图1.4(c)。 由逻辑“或”的真值表可以看出，逻辑“或”有如下一些特点 111 101 011 000 这与“加”相似，所以也称“逻辑加”，有时也记为： XA+B （3）“非”运算和“非门” 观察图1.5(a)所示的电路可以看出，只有当开关A打开时，灯泡L才亮，这种逻辑关系称为逻辑

44、“非”，可以表示为： Xnot A 能实现“非”逻辑功能的电路单元叫“非门”，在电路中用图1.5(b)所示的符号表示。其真值表见图1.5(c)。逻辑“非”有如下一些特点： not 10 not 01所以“非”逻辑也称逻辑反，有时也可写成： XA（4）组合逻辑电路 正如复杂问题的解法可以通过相应的算法，最终化为四则运算等初等数学方法进行运算一样，任任何何复复杂杂的的逻逻辑辑问问题题，最最终终可可用用“与与”、“或或”、“非非”这这3 3种种基基本本逻逻辑辑运运算算的的组组合合加加以以描描述述。常用的组合逻辑电路单元有“与非门”、“或非门”、“异或门”、“同或门”等，它们都是计算机中广泛应用的基本

45、组合逻辑电路单元。表1.6出了几种组合逻辑电路单元的符号，逻辑表达式及其真值表。 “与非门”、“或非门”都是先“与”、“或”再“非”；“异或门”是输入相同则为0，输入不同则为1；反之，“同或门”是输入相同则为1，输入不同则为0。2. 逻辑代数的基本定律根据逻辑加、乘、反的3种基本运算法则，可推导出逻辑运算的一些基本定律。其中最常用的有以下7种。 (1) 关于变量与常量的关系 A + 0A A + 11 A + A1 A00 A1A AA0(2) 重复律 AAA A + AA (3) 吸收律 A + ABA A(A + B)A (4) 分配律A(B + C) AB + AC A + BC(A +

46、 B)( A + C) (5) 交换律 A + BB + A ABBA (6) 结合律 (A + B) + CA + (B + C) (AB)CA(BC) (7) 反演律 ABCA + B + C + A + B + C + ABC1.1.3 算术运算的逻辑电路基础 1. 一位加法电路全加器 运算器是计算机中直接执行各种操作的装置，其核心部件是加法电路。观察图1.6所示的算式(0.111 + 0.011)中对应的第i位相加过程可以看出，加法运算时某一位相加需要有下列5个变量： 输入：被加数Xi、加数Yi、低位进位Ci-1 输出：本位进位Ci、本位全和Si因此一个全加器应有五个端口：三个输入端，

47、两个输出端。它的真值表如表1.7所示。 在真值表中，将函数值为1的项相“或”，就组成了与该函数的逻辑表达式。如全加器的本位和有4项，全加器的本位进位也有4项，即有Si=XiYiCi-1+XiYiCi-1+XiYiCi-1+XiYiCi-1=Xi Yi Ci-1Ci=XiYiCi-1+XiYiCi-1+XiYiCi-1+XiYiCi-1=XiYi+(Xi Yi)Ci-1 由这两个表达式很容易得到相应的组合逻辑电路，如图1.7 实质上，全加器是完成3个1位数相加、具有两个输出端的逻辑电路。对应于输入端的不同值，将在两个输出端上输出相应的值。2. 串行加法电路串行运算加法器如图1.8所示。它是由两个

48、n位的移位寄存器，一个全加器和一个（由D触发器组成的）进位触发器所组成。寄存器寄存器A A，B B每接收一次移位脉冲，被每接收一次移位脉冲，被加数和加数同时各右移一位，使得进位触发器中的前位加数和加数同时各右移一位，使得进位触发器中的前位进位和进位和A1A1及及B1B1中的当前位在中的当前位在中相加中相加。每次相加之后得Si计入A寄存器最左端，本位进位送给进位触发器C的输入端D。下一次移位脉冲到来时，进位触发器送给一个进位。这样经过n次移位脉冲后，就完成了两个n位二进制数相加，最后结果存放在寄存器A中。 3. 并行加法电路两个n位二进制数各位同时相加称为并行加法。图1.9为n位并行加法电路。它

49、由n个全加器所组成。运算时由由两两个个寄寄存存器器送送来来的的n n位位数数据据，分分别别在在n n个个全全加加器器中中按按位位对对应应相相加加；每每个个全全加加器器得得出出的的进进位位依依次次向向高高一一位位传传送送，从从而而得得出出每每位位的的全全加加和和。最后1个进位Cn为计算机工作进行判断提供了一个测试标态，在某些情况下（如多字节运算）还可以作为运算的一个数据。其中的逻辑表达式描述了它们用3种基本的逻辑电路实现的方法，如“异或门”可以由两个“非门”、两个“与门”、一个“或门”组成。进一步又可以用基本组合逻辑电路组成更复杂的逻辑电路。如在并行加法器前加一级“异或门”就可以组成“加减法运算

50、器”，如图1.10所示。 这样，当SUB0时，有 BiBiSUB + BiSUBBi0 + Bi1Bi 进行的是A + B； 当SUB1时，有 BiBiSUB + BiSUBBi1 + Bi0Bi 进行的是A - B。十进制数0123456789101632二进制数01101110010111011110001001101010000100000表表1.1 1.1 几个十进制数与二进制数之间的对应关系几个十进制数与二进制数之间的对应关系返回 真值原 码 反 码 补 码 移 码 +127 0111 1111 0111 1111 0111 1111 1111 1111 +1 0000 0001 0

51、000 0001 0000 0001 1000 0001 +0 0000 0000 0000 0000 0000 0000 1000 0000 -0 1000 0000 1111 1111 0000 0000 1000 0000 -1 1000 0001 1111 1110 1111 1111 0111 1111 -127 1111 1111 1000 0000 1000 0001 0000 0001 -128 不能表示 不能表示 1000 0000 0000 0000 表表1.2 1.2 几个典型数据的编码几个典型数据的编码返回Ef E S M 图图1.1 浮点数的机内表示浮点数的机内表示 S E M图图1.2 IEEE 754 格式的浮点数格式的浮点数1位位m位位n位位返回返回返回返回返回返回图图 1.5 逻辑逻辑“非非”返回返回返回返回(a)全加器的逻辑组合电路全加器的逻辑组合电路(b)全加器的逻辑符号全加器的逻辑符号图图1.7 全加器的逻辑组合电路及其符号全加器的逻辑组合电路及其符号返回返回返回返回