计算机是一种能对数字化信息进行自动高速运算的通用处....ppt

1、第一章 概述,计算机是一种能对数字化信息进行自动高速运算的通用处理装置。,11 计算机的定义和特性,信息 运算 处理,1.1.1 什么是计算机,1.1.2 计算机的特性,计算机的特性可以归纳为高速、通用、准确、 智能四大特性。,12 计算机的发展历程,1.2.1 电子计算机的诞生,第一台电子计算机ENIAC（Electronic Numerical Integrator and Computer）于1946年在美国诞生。,每秒5000次加法运算； 每秒50次乘法运算； 平方和立方计算； Sin和Cos函数数值运算； 其它更复杂的计算。,1.2.2 第一代计算机 （20世纪40年代中到50年代末

2、）,第一代计算机为电子管计算机，其逻辑元件采用电子 管，存储器件为声延迟线或磁鼓，典型逻辑结构为定 点运算。计算机“软件”一词尚未出现，编制程序所用 工具为低级语言。,1.2.3 第二代计算机（50年代中后期到60年代中）,第二代计算机为晶体管计算机。这一代计算机除了逻 辑元件采用晶体管以外，其内存储器由磁芯构成，磁 鼓与磁带成为外存储器。,计算机典型逻辑结构实现了浮点运算， 并提出了变址、中断、I/O处理等新概念。 计算机软件也得到了发展，出现了多种 高级语言及其编译程序。,1.2.4 第三代计算机（60年代中到70年代中）,第三代计算机为集成电路计算机，其逻辑元件与存储器 均由集成电路实现

3、，这是微电子与计算机技术相结合的 一大突破。微程序控制、高速缓存、虚拟存储器、流水 线等先进计算机技术开始使用。另一大特点是大型/巨 型机与小型机同时发展。,1.2.5 第四代计算机（70年代中期开始）,大规模（LSI）和超大规模（VLSI）集成电路 及微处理器为这一代计算机的典型特征。,并行处理技术的研究与应用以及众多巨型机的产生也成 为这一时期计算机发展的特点。,四代机时期的一个重要特点是计算机网络的发展与广泛 应用。,1.2.6 新一代计算机,新器件和非冯诺依曼结构已成为新一代计算机的公认标志。,13 计算机的组成与结构,1.3.1 计算机系统的层次结构,1.3.2 计算机硬件,计算机硬

4、件是指构成计算机的元器件、 部件、设备、以及它们的设计与实现技术。,冯诺依曼计算机的主要特点：,1）计算机由运算器、存储器、控制器和输入/输出五个 部件组成。,本书讨论的范围涉及第0、1、2共3层， 主要内容如下： 1. 高速的算术、逻辑运算方法及ALU的 逻辑设计； 2. 高速的指令执行过程及指令部件的设计与实现， 是采用组合逻辑技术、或微程序设计技术，还是 PLA技术；是复杂指令集计算机（CISC），还是 精简指令集计算机（RISC）； 3. 提高存储器容量与速度的方法，以及如何解决 “CPU-Cache-MM-外存”之间的匹配问题； 4. 高效率的输入/输出方法、组织，以及它们之间的 互

5、联技术； 5. 计算机五大部件（运算器、控制器、存储器、输入 和输出）之间的相互作用、高效接口（总线）；,2）存储器以二进制形式存储指令和数据；,3）存储程序工作方式；,4）五部件以运算器为中心进行组织；,1.3.3 计算机软件,1. 软件的作用,一般来说，计算机的工作总是由存储程序来控制的。,软件的具体作用为：,在计算机系统中起着指挥和管理的作用。,是计算机用户和硬件的接口界面。,是计算机体系结构设计的主要依据。,2. 软件的发展过程,三个阶段：,1)从第一台计算机上的第一个程序出现到 实用的高级语言出现为第一阶段（1946-1956年）。,2)从实用的高级程序设计语言出现到软件工程出现 以

6、前为第二阶段（1956-1968年）。,3)软件工程出现以后迄今一直为第三阶段（1965）。,3. 软件的分类, 系统软件：操作系统、编译程序。, 支撑软件：数据库、各类接口软件和工具组。, 应用软件：,14 计算机的分类与应用,1.4.1 计算机的分类,按计算机所处理对象的表示形式不同可以 分成模拟计算机与数字计算机两类。,计算机按其用途来分可以分成专用机和通用机两类。其中，通用计算机按其规模、性能和价格来分，又可分为巨型机、大型机、小型机、工作站、微型机等多种类型。,1.4.2 计算机应用,计算机信息处理技术包括了对各种信息媒体的获取、 表示、加工与表现方法和技术，大致有以下几个方 面内容

7、：,1语言与文字的处理。,2计算机图形学与数字图象处理。,3多媒体技术。,4计算机辅助技术。,5计算机信息系统。,6计算机控制。,计算机应用技术的发展方向为集成化、网络化、智能化,第2章 数据的表示,本章讨论在计算机内部各类基本数据 的表示方法及其相互间的等值转换。,21 数据、信息和媒体,数据是对事实、概念或指令的一种特殊表达形式，这种特殊的表达形式可以用人工的方式或者用自动化的装置进行通信、翻译转换或者进行加工处理 。,在计算机系统中所指的数据均是以二进制编码形式出现的。,计算机内部由硬件实现的基本数据区分为数值型数据和非数值型数据。,2.1.1 数据,信息是对人有用的数据，这些数据可能影

8、响到人们的行为和决策。,媒体又称媒介、媒质，是指承载信息的载体。,2.1.2 信息,计算机信息处理，实质上就是由计算机进行数据处理的过程。,信息是对数据的解释，数据是信息的载体。,2.1.3 媒体,与计算机信息处理有关的媒体有5种：,感觉媒体 表示媒体 存储媒体 表现媒体 传输媒体,图 2.1 计算机外部信息与内部数据的转换,22 数字化信息编码,所谓编码，就是用少量简单的基本符号，对 大量复杂多样的信息进行一定规律的组合。,在计算机系统中，凡是要进行处理（包括计算、查找、排序、分类、统计、合并等）、存储和传输的信息，都是用二进制进行编码的。,计算机内部采用二进制表示的原因： 1）二进制只有两

9、种状态，在数字电路中很容易实现。 2）二进制编码、运算规则非常简单。 3）二进制的“0”、“1”与二值逻辑一致，很容易实现 逻辑运算。,2.3 数值数据的编码表示,数值数据是表示数量多少和数值大小的数据。,在计算机内部，数值数据的表示方法有两大类：第一 种是直接用二进制数表示；另一种是采用二进制编码的 十进制数（Binary Coded Decimal Number，简称BCD） 表示。,表示一个数值数据要确定三个要素：进位计数制、 定浮点表示和数的编码表示。,2.3.1 进位计数制及其各进位制数之间的转换,在某个数字系统中，若采用R个基本符号（0，1， 2，R-1）表示各位上的数字，则称其为

10、基R 数制，或称R进制数字系统，R被称为该数字系统的基， 采用“逢R进一”的运算规则，对于每一个数位i，其该 位上的权为R i。,在计算机系统中，常用的几种进位计数制 有下列几种： 二进制 R=2, 基本符号为 0和1 八进制 R=8, 基本符号为 0,1,2,3,4,5,6,7 十六进制 R=16, 基本符号为 0,1,2,3,4,5,6,7,8,9, A,B,C,D,E,F 十进制 R=10, 基本符号为 0,1,2,3,4,5,6,7,8,9,例：十进制数2585.62代表的实际值是 2x103+5x102+8x101+5x100+6x10-1+2x10-2,例：二进制数(100101.

11、01)2代表的实际值是： (100101.01)2 = 1x25 + 0 x24+ 0 x23 + 1x22 + 0 x21 + 1x20+ 0 x2-1 + 1x2-2=(37.25)10,1.R进制数转换成十进制数,任何一个R进制数转换成十进制数时，只要 “按权展开”即可。,例1 二进制数转换成十进制数。 (10101.01)2=(124+023+122+021+120+ 0 2-1+12-2)10=(21.25)10,例2 八进制数转换成十进制数。 (307.6)8=(382+780+68-1) 10=(199.75) 10,例3 十六进制数转换成十进制数。 (3A.C)=(3161+1

12、0160+1216-1) 10 =(58.75) 10,2. 十进制数转换成R进制数,任何一个十进制数转换成R进制数时，要将 整数和小数部分分别进行转换。,（1）整数部分的转换 整数部分的转换方法是“除基取余，上右下左”。,例1 将十进制整数835分别转换成二、八进制数。,0,余数 低位,3,0,5,1,(835) 10=(1503) 8,高位,(835) 10=(1101000011) 2,（2）小数部分的转换,小数部分的转换方法是 “乘基取整，上左下右”。,例2 将十进制小数0.6875分别转换成二、八进制数。,0.68752=1.375 1,整数部分,0.3752=0.75 0,0.75

13、2=1.5 1,0.52=1.0 1,(0.6875) 10=(0.1011) 2,整数部分,0.68758=5.5 5,0.58=4.0 4,(0.6875) 10=(0.54) 8,例3 将十进制小数0.63转换成二进制数。,整数部分,0.632=1.26 1,0.262=0.52 0,0.522=1.04 1,0.042=0.08 0,(0.63) 10=(0.1010) 2 (近似值),（3）含整数、小数部分的数的转换,只要将整数、小数部分分别进行转换，得 到转换后的整数和小数部分，然后再这两 部分组合起来得到一个完整的数。,例 4 将十进制数835.6875转换成二、八进制数。 (8

14、35.6875) 10=(1101000011.1011) 2=(1503.54) 8,3. 二、八、十六进制数的相互转换,（1）八进制数转换成二进制数,例1 将(13.724) 8转换成二进制数 (13.724) 8=( 001 011 . 111 010 100 )2 =(1011.1110101) 2,（2）十六进制数转换成二进制数,例2 将十六进制数2B.5E转换成二进制数 (2B.5E)16 = ( 0010 1011 . 0101 1110 ) 2 = (101011.0101111) 2,（3）二进制数转换成八进制数,(10011.01) 2 = ( 010 011 . 010

15、) 2 = (23.2) 8,（4）二进制数转换成十六进制数,(11001.11) 2 = ( 0001 1001 . 1100 ) 2 = ( 19.C ) 16,2.3.2 定点与浮点表示,1定点表示,所谓定点表示是约定计算机中所有数据的小数点 位置是固定不变的。该位置在计算机设计时已被隐含地 规定，因此勿需再用任何硬件设备状态来明显表示小数点。,利用定点表示进行计算，须将所有数据之 值按一定比例予以缩小（或放大）后送入 计算机，同时须将计算结果以同一比例增 大（或缩小）后才能得正确结果值。,由于采用定点数表示数的范围较小，因此运算很容易 产生溢出，另外选择适当的比例因子有时也很困难。,2

16、浮点表示,在计算机中所表示的数，其小数点位置是可变的，这 种数称为浮点数。,对于任意一个二进制数X，可以表示成 如下形式： X= MRE 其中：M为尾数，常用定点纯小数表示；E为阶，一般 用定点整数表示；R为基数，隐含为2，也可以为2q， q可取2，3，4等正整数。,浮点表示法的最大特点是它可以表示 很大的数据范围以及较高的数据精度。,2.3.3 编码系统,确定一个数值数据的三要素是：进位计数制、 定点/浮点表示和编码表示。它们分别用来解决数值 数据的基本表示符号、小数点位置和数的正负号表示。,符号数字化：0表示正号，1表示负号。,机器数：数值数据在计算机内部编码表示的数。 真值：机器数真正的

17、值（即：原来带有正负号的数）。,机器数X的真值为： XT = X1Xn2X1X0 （当X为定点整数时） XT = 0 . X1X 2X(n 1)X n （当X为定点小数时） 数字化编码后的机器数X表示为： X = Xn X n -1 X n -2 X 1 X 0,常用的编码表示方式有三种：原码、补码和反码。 对于这三种编码：正数的所有编码表示都是相同的。 其结果总是：符号位取值为0，数值部分保持不变。 负数的所有编码表示，其符号位总是为1，而数值 部分对于不同的编码则有不同的取值。,1原码表示法,原码表示的机器数由符号位后直接跟上 真值的数值构成。,定点整数：,例： +1101原=01101

18、-1101原=11101,原码表示的优点是与真值的对应关系直观、方便， 因此与真值的转换简单，并且用原码实现乘除运算 比较简便，但其加/减法运算规则复杂。,2补码表示法,(1) 模运算,“对一个多于n位的数丢弃高位而保留低n位数” 这样一种处理，实际上等价于“将这个多于n位的数去 除以2n，然后丢去商保留其余数”的操作。这样一种操 作运算就是“模运算”。,在模运算中，若A，B，M满足下列关系：A=B+KM （K为整数）， 则记为： AB（mod M）。 即：A、B各除以M后的余数相同，故称B和为模同 余。,假定现在钟表时针指向10点，要将它拨向 点，则有两种拨法：, 倒拨4格：10-4=6 顺

19、拨8格：10+8186（mod 12）,所以在模12系统中：10-410+8(mod 12) 即： -48 (mod 12) 我们称8是-4对模12的补码。同样有 -39（mod 12）；-57（mod 12）等等。,结论： “对于某一确定的模，某数减去小于模的另一 数，总可以用该数加上模与另一数绝对值之差来代替”。 因此，补码可以用加法实现减法运算。,例1“钟表”模运算系统 10-410+(12-4) 10+86 （mod 12）,例2“4位十进制数” 模运算系统（相当于只 有四档的算盘） 9828-19289828+(104-1928) 9828+8072 7900 （mod 104 ）,

20、（2）补码的定义,定点整数：,补码0的表示是唯一的： +0补=0 0.0 -0补= 2 n -0=1 00.0=0 0.0 (mod 2 n),对于整数补码有：-1补= 2 n 1=11.1 (n个1) 对于小数补码有：-1补=2-1=1.00.0 (n-1个0),例设补码的位数为6，求负数-0.10110 的补码表示。 -0.10110补=2-0.10110 =10.00000-0.10110 =1.01010,求负数补码的简单方法：“符号位固定为1，其余各位 由真值中相应各位取反后，末尾加1所得。”,由补码求真值的简便方法：“若符号位为1，则真值的符 号为负，其数值部分的各位由补码中相应各

21、位取反后， 末尾加1所得。”,求一个补码“取负”后的补码表示方法： “只要对该已知补码各位取反，末尾加1即可。”,由x求 x的方法：将xn的符号位和数值位 一起向右移动一位，符号位移走后还保持原来的值不变。,例1已知：XT =-0.1011010，求XT补 。 XT补=1. 0100101+0. 0000001 =1. 0100110,例2已知：XT补 = 1 011010，求XT 。 XT = -100101+1= -100110,例3已知：XT补=1 011010，求-XT补 -XT补=0 100101+1=0 100110,例4.设x补=1.0101000，则,补=1.1010100,补

22、=1.1110101,补=1.1101010,第3章 运算器与运算方法, 运算器部件是计算机中的执行部件，它可以对二进制数据进行各种算术和逻辑运算； 运算器也是计算机内部数据信息的重要通路。, 本章重点介绍运算器的核心部件算术逻辑运算单元ALU的组成与工作原理，以及数据在运算器的基本运算方法。,3.1 基本组成,1. 算术逻辑运算单元ALU, 运算器实现了对计算机中数据的加工处理；包括数值数据的算术运算和逻辑数据的逻辑操作。, 运算器中完成数据算术与逻辑运算的部件称之为算术与逻辑运算单元（Arithmetic and Logic Unit，简称ALU）。ALU是运算器的核心。, ALU通常表示

23、为两个输入端口，一个输出端口和多个功能控制信号端的这样的一个逻辑符号。,图3.1 ALU的逻辑符号表示与多路开关,2. 通用寄存器组, 运算器内设有若干通用寄存器，构成通用寄存器组；用于暂时存放参加运算的数据和某些中间结果。, 在运算器中用来提供一个操作数并存放运算结果的通用寄存器称作为累加器。, 通用寄存器的数量越多，对提高运算器性能和程序执行速度越有利。, 通用寄存器组是对用户开放的，用户可以通过指令去使用这些寄存器。, 如：ADD A, Rj,3.专用寄存器, 运算器需要记录下指令执行过程中的重要状态标记，以及提供运算前后数据的暂存缓冲等，这通过在运算器中设置若干专用寄存器来实现。, 循

24、环计数器对程序员是透明的。, 程序状态字PSW(Program Status Word)，它存放着指令执行结果的某些状态；如是否溢出、是否为零、是否有进位/借位、是否为负等。它对程序员是开放的。, 堆栈指针SP(Stack Pointer)，它指示了堆栈的使用情况。,4. 附加的控制线路, 在运算器中附加一些控制线路；以达到运算速度快，运算精度高的目的，。, 如：运算器中的乘除运算和某些逻辑运算是通过移位操作来实现的。在ALU的输出端设置移位线路来实现左移、右移和直送。, 移位线路是一个多路选择器。, 图3.2 实现移位功能的多路选择器,3.2 算术与逻辑单元 3.2.1 半加器与全加器, 运

25、算器中各种运算都是分解成加法运算进行的，因此加法器是计算机中最基本的运算单元。,1.半加器, 两个一位二进制数相加(不考虑低位的进位)，称为半加。实现半加操作的电路，称为半加器。,Xi Yi Hi Ci,0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1,表3.1 半加运算的真值表, 表3.1 是两个一位二进制数Xi、Yi相加的真值表， Hi和Ci的逻辑表达式如下：,2. 全加器, 考虑低位进位的加法运算就是全加运算，实现全加运算的电路称为全加器。, 根据真值表表3.2可写出Fi和Ci的逻辑表达式：,表 3.2 全加运算的真值表,图 3.4 全加器的逻辑图和符号表示, 实现逻辑表达

26、式的全加器逻辑图和全加器的符号表示,3.2.2 串行进位与并行进位, n个全加器相连可得n位的加法器；图 3.5是串行进位或行波进位加法器。,图3.5 n位加法器, 先行进位或并行进位加法器, 预先形成各位进位，将进位信号同时送到各位全加器的进位输入端。, 就4位加法器，讨论一下其进位C1、C2、C3和C4的产生条件：, 下述条件中任一条满足就可生成C1=1： 1) X1、Y1均为“1”; 2) X1、Y1任一个为“1”，且进位C0为“1”。, 可得C1的表达式为： C1=X1Y1+（X1+Y1）C0, 下述条件中任一条满足，就可生成C2=1。 1) X2、Y2均为“1”； 2) X2、Y2任

27、一个为“1”， 且进位C1为“1”。, 可得C2的表达式为： C2=X2Y2+(X2+Y2)C1 =X2Y2+(X2+Y2)X1Y1+(X2+Y2)(X1+Y1)C0, 同理，可得C3的表达式为： C3=X3Y3+(X3+Y3)C2 =X3Y3+(X3+Y3)X2Y2+(X2+Y2)X1Y1+ (X2+Y2)(X1+Y1)C0,= X3Y3+(X3+Y3)X2Y2+(X3+Y3) (X2+Y2)X1Y1+ (X3+Y3) (X2+Y2)(X1+Y1)C0, 同理,可得C4的表达式为： C4=X4Y4+(X4+Y4)C3,=X4Y4+(X4+Y4)X3Y3+(X3+Y3)X2Y2+ (X3+Y3

28、)(X2+Y2)X1Y1+(X3+Y3) (X2+Y2)(X1+Y1)C0,=X4Y4+(X4+Y4)X3Y3+(X4+Y4)(X3+Y3)X2Y2+ (X4+Y4)(X3+Y3)(X2+Y2)X1Y1+ (X4+Y4) (X3+Y3) (X2+Y2)(X1+Y1)C0, 定义两个辅助函数： Pi= Xi+Yi Gi= XiYi, Pi表示进位传递函数，当Xi、Yi中有一个为“1”时，若有低位进位输入，则本位向高位传送进位。, Gi表示进位产生函数，当Xi、Yi均为“1”时，不管有无低位进位输入，本位一定向高位产生进位输出。, 将Pi、Gi代入前面的C1C4式，可得： C1=G1+P1C0 C

29、2=G2+P2 G1+ P2P1C0 C3=G3+P3 G2+ P3 P2 G1+ P3 P2P1C0 C4=G4+P4 G3+ P4P3 G2+ P4P3 P2 G1 +P4P3 P2P1C0, “先行进位产生电路” （图 3.6 (a)）及“4位先行进位加法器”的逻辑图（图 3.6 (b)）,图3.6 (a) 先行进位产生电路,图3.6 (b) 4位先行进位加法器, 四个4位先行进位加法器串接起来构成16位加法器, 在各加法单元之间，进位信号是串行传送的，而在加法单元内，进位信号是并行传送的。,图3.7 组间为串行进位构成的16位加法器, 并行进位的概念可用于16位加法器；进一步提高16位

30、加法器的运算速度。, Cm表示4位加法器的进位输出，Pm表示4位加法器的进位传递输出，Gm表示4位加法器的进位产生输出。, Cm=Gm+PmC0, Pm 和Gm分别为： Pm= P4P3P2P1 Gm= G4 +P4 G3 + P4P3G2 +P4P3P2G1, 应用于四个4位先行进位加法器，则有： Cm1=Gm1+Pm1C0,Cm2=Gm2+Pm2Cm1 = Gm2+ Pm2Gm1 + Pm2 Pm1C0,Cm3=Gm3+Pm3Cm2 = Gm3+ Pm3Gm2 + Pm3Pm2Gm1+ Pm3 Pm2 Pm1C0,Cm4=Gm4+Pm4Cm3 = Gm4+ Pm4Gm3 + Pm4Pm3G

31、m2+ Pm4Pm3Pm2 Gm1+ Pm4Pm3Pm2P m1C0,图3.8 组间由先行进位链构成的16位加法器, 可将并行进位的概念用于更大位数的加法器上，随着加法器位数的增加，加法电路变得越来越复杂。,33 定点加、减法运算, 计算机的一个重要特点是它只能用有限的 数码位数来表示操作数和操作结果。, 制定用来表示正、负数的各种码制；通过数据编码来简化数据的运算，特别是补码，把加法和减法巧妙地结合起来。, 定点加、减法运算只有在遵守模运算规则的限制条件下其结果才是正确的，否则就会出现结果“溢出”。,3.3.1 补码定点加、减法, 补码制的加、减法运算公式： X+Y补= (X补+Y 补) M

32、OD 2n X-Y补= (X补+-Y 补) MOD 2n, 在补码制方法下，无论X、Y是正数还是负数，加、减法运算统一采用加法来处理；, X补和Y补的符号位和数值位一起参与求和运算，加、减运算结果的符号位也在求和运算中直接得出。, 例1：已知X补=01001，Y补=11100 ； 求X+Y补， X-Y补。, 则-Y补=00100, X+Y补= (X补+Y补) MOD 2 5 =(01001+11100) MOD 2 5 =00101, X-Y补= (X补+-Y补) MOD 2 5 =(01001+00100) MOD 2 5 =01101, 若结果超过了允许表示的最小负数时，产生的溢出称为下溢

33、。, 当算术运算的结果超出了数码位数允许的数据范围时，就产生溢出。, 对于n位的二进制码表示的补码整数（符号位占一位），它可表示的数据范围为-2n-12n-1-1。, 若结果超过了允许表示的最大正数时，产生的溢出称为上溢；, 在运算器中应设有溢出判别线路和溢出标志位。, 例2：已知X补=01010，Y补=01010 X+Y补=(01010+01010) MOD 2 5 = 10100 溢出, 例3：已知X补=10010，Y补=00100 X-Y补=(10010+11100) MOD 2 5 = 01110 溢出, 1010 + 1010= 201015 产生上溢, -1410 - 410= -

34、1810-16 产生下溢, 溢出常用的判别方法：, 两个补码数实现加、减运算时，若最高数值位向符号位的进位值Cn-1与符号位产生的进位输出值Cn不相同，表明加减运算产生了溢出OVR；, 可以表示为： OVR= Cn-1Cn OVR=1表示结果有溢出，OVR=0表示结果正确。,在例1中，求X+Y补时：OVR= Cn-1Cn =11=0，结果正确。,在例2中，求X+Y补时：OVR= Cn-1Cn =10=1，结果溢出。,在例3中，求X -Y补时：OVR= Cn-1Cn =01=1，结果溢出。, 常用双符号位方法来判别加、减法运算是否有溢出，正数的双符号位是00，负数的双符号位是11。, 两个正数双

35、符号位的运算为00+00=00时，结果不溢出；, 两个正数双符号位的运算为00+00+1=01时，结果上溢。, 两个负数的双符号位运算为（11+11+1）MOD 4 =11时，结果不溢出；, 两个负数的双符号位的运算为（11+11）MOD 4=10时，结果下溢。, 采用模4补码运算，其运算结果的两个符号位不一致时，产生溢出。, 实现补码加、减法运算的逻辑电路(图3.15),图3.15 实现补码加减法运算的逻辑电路, 它的核心部件是二进制并行加法器F，它接收来自寄存器X和寄存器Y的两个操作数。, 用图3.15 来实现加法X+Y补的逻辑操作步骤如下：, X补寄存器X，Y补寄存器Y。, 给出控制信号

36、：X F=1，YF=1，且1F =0 。X补和Y补送入加法器F的两个输入端。, 并行加法器F接收X补和Y 补，完成X补+Y 补的加法过程，输出X+Y补，并置溢出、进位等信号到标志寄存器。, 给出控制信号：FX=1，加法器F的输出结果送入寄存器X。加法运算结束。, 用图3.15 来实现减法X-Y补的逻辑操作步骤如下： X补寄存器X，Y补寄存器Y。, 给出控制信号：XF=1，YF=1。X补和Y补=yn-1yn-2y0送入加法器F的两个输入端。, 给出控制信号：1F=1，并行加法器F接收X补 、Y 补和进位信号1，完成X补+ yn-1yn-2 y0+1= X补+-Y 补的加法过程，输出X-Y补，并置

37、溢出、进位等信号到标志寄存器。, 给出控制信号：FX=1，加法器F的输出结果 X-Y补送入寄存器X。减法运算结束。, 当寄存器X或寄存器Y的内容送到加法器F时，将符号位等值扩充一位，形成双符号位；双符号位只在加法器中执行加法运算时是必要的。, 寄存器X、寄存器Y和加法器F的二进制位数对运算数据和运算结果的大小有限制作用，当超过了这些运算结构所能表示的数据范围时，就产生溢出。, 以加法器和通用寄存器的二进制位数定义为计算机的字长。计算机的字长通常是8的整数倍。,3.4 定点乘法运算, 常规的乘法运算方法（定点小数）, 笔-纸乘法方法，, 原码乘法，, 带符号位运算的补码乘法，, 用组合逻辑线路构

38、成的阵列乘法器。,3.4.1 原码一位乘法, 用原码实现乘法运算时，符号位与数值位是分开计算的；, 原码乘法运算分为二步；, 第二步是计算乘积的数值位；乘积的数值部分为两数的绝对值之积。, 第一步是计算乘积的符号位；乘积的符号为相乘二数符号的异或值。, 用数学表达式描述原码乘法运算, 设：X原=x0 x1xn，Y原= y0y1yn (其中x0 、y0分别为它们的符号位), 若 X*Y原=z0z1z2n (其中z0 为结果之符号位) 则 z0= x0 y0, z1z2n= (x1xn ) *(y1yn), 笔-纸乘法方法, 例1. X=0.1011,Y=0.1101，X*Y的笔-纸乘法过程：,0

39、.1011 被乘数X=0.x1x2x3x4=0.1011 * 0.1101 乘数Y=0.y1y2y3y4=0.1101,1011 X* y4*2 4,0000 X* y3*2 3,1011 X* y2*2 2,1011 X* y1*2 1,0.10001111, 因此 X*Y=0.10001111, X*Y的笔-纸乘法过程中，计算两个正数的乘法特点：, 用乘数Y的每一位依次去乘以被乘数，得X*yi，i=4、3、2、1。若yi=0，得0。若yi=1，得X。, 把中求得的各项结果X*yi在空间上向左错位排列，即逐次左移，可以表示为X* yi*2-i 。, 对中求得的结果求和， ，这也就是两个正数的

40、乘积。, 就笔-纸乘法方法，为提高效率而采取的改进措施, 每将乘数Y 的一位乘以被乘数得X*yi后，就将该结果与前面所得的结果累加，而得到P i，称之为部分积；这减少了保存每次相乘结果X*yi的开销。, 将部分积P i右移一位与X*yi相加。加法运算始终对部分积中的高n位进行；因此，只需用 n位的加法器就可实现二个n位数的相乘。, 对乘数中“1”的位执行加法和右移运算，对“0”的位只执行右移运算，而不执行加法运算。可以节省部分积的生成时间。, 已知两正小数X和Y，Y=0.y1y2yn，则： X*Y=X*(0.y1y2yn),= X* y1*2-1 +X* y2*2-2 +X* y3*2-3 +

41、- +X* yn*2-n, 部分积迭代法,=2-1 2-1 2-1-2-1 (2-1 (0 + X* yn)+ X* yn-1)+ -+ X* y2+ X* y1 n个2-1, 设P0=0 P1= 2-1 (P0+ X* yn) P2= 2-1 (P1+ X* yn-1) Pi+1= 2-1 (Pi+ X* yn-i) ( i=0,1,2,3, n-1 ) Pn= 2-1 (Pn-1+ X* y1), 上述乘法运算可以归结为循环地计算下列算式：, 显然，X*Y= Pn, 迭代过程可以归结为：, 若Yn-i的值为“1”，将上一步迭代的部分积Pi 与X相加。, 若Yn-i的值为“0”，什么也不做。

42、再右移一位，产生本次的迭代部分积Pi+1。, 整个迭代过程以乘数最低位yn和P0=0开始，经过n次“判断加法右移”循环直到求出Pn为止。, Pn就为乘法结果。, 实现这种方法的二个定点小数乘法的逻辑电路框图,图3.16 实现定点乘法运算的逻辑电路,图3.17 两个定点小数的乘法操作流程, 例1 已知 X原=01101 , Y原= 01011 , z1z8=1101*1011的计算采用上述乘法流程，实现的具体过程如下：, 若 X*Y原=z0z1z8 则 z0= 0 0=0,C P Y 说明 0 0000 1011 开始，设P0=0,+1101 y4=1，+X,0 1101 C,P 和Y同时右移一

43、位,0 0110 1 101 得P1,+1101 y3=1，+X,1 0011 C,P 和Y同时右移一位,0 1001 11 10 得P2,y2=0，不作加法 C,P 和Y同时右移一位 0 0100 111 1 得P3,+1101 y1=1，+X,1 0001 C,P 和Y同时右移一位,0 1000 1111 得P4, z1z8=10001111, X*Y原=z0z1z8=010001111,0 0110 1 101 得P1,3.4.2 原码二位乘法, 为提高乘法的速度，可以对乘数的每两位取值情况进行判断，一步求出对应于该两位的部分积。, 在乘法中，乘数的每两位有四种可能的组合，每种组合对应于

44、以下操作：, 原码二位乘法的思想, 采用原码二位乘法，只需增加少量的逻辑线路，就可以将乘法的速度提高一倍。,00 Pi+1=2-2Pi,01 Pi+1=2-2(Pi +X),10 Pi+1=2-2(Pi +2X),11 Pi+1=2-2(Pi +3X), 实现+3X有两种方法：, 分+X再+2X来进行，次法速度较低。, 以4X-X来代替3X运算，在本次运算中只执行-X，而+4X则归并到下一拍执行。 Pi+1=2-2(Pi +3X)= 2-2(Pi -X+4X)= 2-2(Pi -X) +X。, 用yi-1、yi和T三位来控制乘法操作, 触发器T用来记录是否欠下+X，若是，则1T, 原码两位乘法

45、运算规则,表3.3 原码两位乘法运算规则, 原码两位乘法运算过程举例,例1： 已知 X原=0111001 , Y原= 0100111 , |X|补=0111001 ，-|X|补=1000111 ；, 若 X*Y原=z0z1z12 则 z0= 0 0=0, z1z12=111001*100111 具体过程：,P Y T 说明 000 000000 100111 0 开始，P0=0，T=0,+111 000111 y5y6T=110 ，-X ,T=1,111 000111 P和Y同时右移2位,111 000111 P和Y同时右移2位,111 110001 11 1001 1 得P1,+001 11

46、0010 y3y4T=011 ，+2X ,T=0,001 100011 P和Y同时右移2位,000 011000 1111 10 0 得P2,+001 110010 y1y2T=100 ，+2X ,T=0,010 001010 P和Y同时右移2位,000 100010 101111 0 得P3, z1z12=100010101111, 因此X*Y原=0100010101111,3.4.3 补码一位乘法, 考查两个补码乘法运算的例子,例1： 已知 X=0.1011，Y=0.0001,X补=01011 , Y补= 00001,X*Y补=000001011,X补*Y补=000001011, 显然，X

47、*Y补=X补*Y补,例2： 已知 X=0.1011，Y= - 0.0001,X补=01011 , Y补= 11111,X*Y补=111110101,X补*Y补=101010101, 显然，X*Y补X补*Y补, 对两个正数来说，它们补码的乘积等于它们乘积的补码。若乘数是负数时，这种情况就不成立了。, 若X补=x0 x1 xn , Y补= y0y1 yn 。, 考查两个补码乘法运算的一般情况, 根据补码定义，可得出其真值: Y= - y0+ yi2-i,i=1,n, X*Y补= X*(-y0+ yi2-i) 补,= X *yi2-i-X*y0 补,= X *yi2-i 补 +-X*y0补,n,i=

48、1,i=1,n,n,i=1, Booth（布斯）乘法, 相乘二数用补码表示，它们的符号位与数值位一起参与乘法运算过程，直接得出用补码表示的乘法结果，且正数和负数同等对待。, A.D.Booth算法思想：, Booth算法推导：, 已知X补=x0 x1 xn , Y补= y0y1 yn ；根据补码定义，可得出:, 根据补码定义，可得出其真值: Y= - y0+ yi2-i,i=1,n,= - y0+y12-1+y22-2+y32-3+ +yn2-n,= - y0+(y1-y12-1)+ (y22-1-y22-2)+ + (yn2-(n-1)-yn2-n),= (y1-y0)+ (y2-y1)2-

49、1+ (y3-y2)2-2+ + (yn-yn-1 )2-(n-1) +(0-yn )2-n,= (yi+1-yi)2-i,n,i=1, 设yn+1=0（称为辅助位）；有： X*Y补=X* (yi+1-yi)2-i补,n,i=1,=(y1-y0)X+ 2-1( y2-y1)X + 2-1( y3-y2)X + +2-1(yn-i+1-yn-i)X+ +2-1(yn-yn-1)X+2-1(yn+1-yn) X) ) ) 补, 得到如下递推公式： Pi+1补= 2-1(Pi + (yn-i+1-yn-i)X)补 ( i= 0，1，2 n), 上式中Pi为上次部分积，Pi1为本次部分积。 令P0补0

50、，有：,P1补=2-1(yn+1-yn)*X补 (i= 0) P2补=2-1(P1 + (yn-yn-1)*X)补 (i= 1) Pn补=2-1(Pn-1 + (y2-y1)*X)补 (i= n-1) Pn+1补=Pn + (y1-y0)*X补, 经过比较可得 X*Y补=Pn+1补= Pn + (y1-y0)*X补,= Pn 补+ (y1-y0)*X补, 对乘数的连续两位yn-i和yn-i+1进行判断,若yn-i yn-i+1=01， 则Pi+1补=2-1(Pi + X)补 若yn-i yn-i+1=10， 则Pi+1补=2-1(Pi - X)补 若yn-i yn-i+1=00或11，则Pi+

51、1补=2-1Pi 补, 一个补码数据的右移是连同符号位右移，且最高位补充符号位的值。, 补码乘法运算规则：, 乘数最低位增加一辅助位yn+1= 0；, 判断yn-i yn-i+1的值，决定是“+X”或“-X”，或仅右移一位，得部分积；, 重复第步，直到最高位参加操作(y1-y0)*X，但不作移位，结果得X*Y补。, 图3.18 是实现布斯乘法的算法流程图,是,是,是,否,否,否,图3.18 布斯乘法运算流程图,开始,yn+1，P0 X补码制的被乘数 Y补码制的乘数 Cnn,yn yn+1,P P+X,Cn=0,P和Y同时右移一位 Cn Cn-1,yn yn+1,P P-X,结束, 例3： 已知

52、 X补=01101, Y补= 10110，-X补=10011。, 用布斯乘法计算X*Y补的过程如下,P Y yn+1 说明 00 0000 10110 0 开始，设y5=0，P0补=0,y4 y5 =00，P、Y同时右移一位 00 0000 0 1011 0 得P1补,+11 0011 y3 y4 =10，+-X补,11 0011 P、Y同时右移一位,11 1001 10 101 1 得P2补,y2 y3 =11，P、Y同时右移一位,11 1100 110 10 1 得P3补,11 1100 110 10 1 得P3补,+00 1101 y1y2 =01，+X补,00 1001 P、Y同时右移

53、一位,00 0100 1110 1 0 得P4补,+11 0011 y0 y1 =10，+-X补,11 0111 1110 1 最后一次不右移, 因此，X * Y补=101111110, 布斯乘法的算法过程为n+1次的“判断加减右移”的循环，判断的次数为n+1次，右移的次数为n次。, 在布斯乘法中，遇到连续的“1”或连续的“0”时，是跳过加法运算，直接实现右移操作的，运算效率高。,3.4.4 补码二位乘法, 补码二位一乘的方法可以用布斯乘法过程来推导, Pi+1补=2-1Pi补 + (yn-i+1-yn-i)* X 补, Pi+2补=2-1Pi+1补+ (yn-i-yn-i-1)* X 补,

54、Pi+2 补=2-2Pi 补+ (yn-i+1 +yn-i -2yn-i-1)* X 补, 根据乘数的两位代码yn-i-1和yn-i以及右邻位yn-i+1的值的组合作为判断依据，跳过Pi+1补步，即从Pi补直接求得Pi+2补。,乘数代码对 右邻位 加减判断规则 Pi+2补 yn-i-1 yn-i yn-i+1,表3.4 乘数3位代码组合构成的判断规则,0 0 0 0 2-2Pi补,0 0 1 +X补 2-2Pi补+X补,0 1 0 +X补 2-2Pi补+X补,0 1 1 +2X补 2-2Pi补+2X补,1 0 0 +2-X补 2-2Pi补+2-X补,1 0 1 +-X补 2-2Pi补+-X补,

55、1 1 0 +-X补 2-2Pi补+-X补,1 1 1 0 2-2Pi补, 设乘数Y补= y0y1 yn ，导出补码二位乘法中的计算量。,(1) 当n为偶数时，乘法运算过程中的总循环次数为n/2+1。,(2) 当n为奇数时，乘法运算过程中的总循环次数为（n+1）/2。, 例4：已知X补=00011 , Y补= 11010 ；-X补=11101 。用补码二位乘法计算X * Y补的过程。,P Y yn+1 说明,000 0000 11010 0 开始，设y5=0，P0补=0,+111 1010 y3 y4 y5 =100，+2-X补,111 1010 P和Y同时右移二位,111 1110 10 1

56、10 1 得P1补,+111 1101 y1 y2 y3 =101，+-X补,111 1011 P和Y同时右移二位,111 1110 1110 1 1 得P2补,y0 y0 y1 =111，不做加法 最后一次不右移, X * Y补=111101110,3.4.5 阵列乘法器, 实现上述执行过程的阵列结构的乘法器，称为阵列乘法器(Array Multiplier), 图3.19中实现了X*Y的乘法运算，其中X=x1x2 x3 x4 , Y= y1y2y3y4 。X和Y都是无符号的小数部分。, 上式中一位乘积xi*yj用一个两输入端的“与”门实现；, 每一次加法操作用一个全加器实现；, 2-i和2-j 的因子所蕴含的移位是由全加器的空间错位来实现。,图3.19 直接实现定点数绝对值相乘的阵列乘法器, Booth算法的乘法运算也可以用阵列乘法器的方法实现，但要求的单元更复杂。, 阵列乘法器的组织结构规则性强，标准化程度高。适合用超大规模集成电路实现，且能获得很高的运算速度。, 集成电路的价格不断下降，阵列乘法器在某些数字系统中，例如在信号及数据处理系统中受到重视，它不需要时钟脉冲，而其乘法速度仅决定于门和加法器的传输延迟