算数逻辑运算电路

1、 第四章第四章 算数逻辑运算电路算数逻辑运算电路计算机结构与逻辑设计 输输入入设设备备 运算器运算器输输出出设设备备控制器控制器存储器存储器计算机的基本功能是对数据信息进行加工处理。计算机的基本功能是对数据信息进行加工处理。算数运算算数运算逻辑运算逻辑运算加法加法比较比较移位移位运运算算器器基本思想：基本思想：将各种复杂的运算处理分解为最基本的将各种复杂的运算处理分解为最基本的算数运算和逻辑运算。算数运算和逻辑运算。1 1 数据格式数据格式 计算机中常用的数值数据有两种表示格式计算机中常用的数值数据有两种表示格式：（1）定点格式）定点格式（2）浮点格式）浮点格式 定点格式：所有数据定点格式：所

2、有数据的的小数点位置固定小数点位置固定 浮点格式浮点格式：各数据的：各数据的小数点小数点位置浮动位置浮动数据格式数据格式 浮点数的浮点数的IEEE754 标准格式标准格式 ：其中：其中：S=浮点数的符号位浮点数的符号位（0表示正数，表示正数，1表示负数），表示负数）， M为为23位纯小数表示位纯小数表示; E=阶码，阶码，用用8位位纯整数表示。纯整数表示。 注意：真实尾数设定注意：真实尾数设定为：为：1.M （“1”是隐含的）是隐含的） 阶码符号采用隐含方式阶码符号采用隐含方式，即：采用，即：采用移码移码方式来表示正负指数。方式来表示正负指数。 SEM 31 30 23 22 032位位标准格

3、式标准格式:对应的真值：对应的真值：1272). 1()1( EeSMx【例】【例】将将X=+20.59375= 转换为转换为754标准浮点格标准浮点格式。式。已知已知: X=+20.59375=+0.10100100112+5 =+1.0100100112+4(e=4) S=0, E=e+127=131=(10000011)2, M=010010011该该“1”将隐含将隐含故：其故：其32位位754标准浮点格式为标准浮点格式为 0100 0001 1010 0100 1100 0000 0000 0000=(41A4C000)H321920 【机器码表示法小结机器码表示法小结】在数据的四种机

4、器码表示法中：在数据的四种机器码表示法中： 正数的原码、反码、补码等同于真值；只有负数才分正数的原码、反码、补码等同于真值；只有负数才分别有不同的表示方法。别有不同的表示方法。 移移码在数值上与补码相同，符号位（最高位）正好相码在数值上与补码相同，符号位（最高位）正好相反。移码主要用于表示浮点数的阶码，可以直接比较反。移码主要用于表示浮点数的阶码，可以直接比较大小。大小。 补码可以连同符号位一起直接进行加减法运算补码可以连同符号位一起直接进行加减法运算( (后面给后面给予算法证明予算法证明) )，十分方便，因此目前计算机中广泛采用，十分方便，因此目前计算机中广泛采用补码表示法。补码表示法。机器

5、码表示法小结机器码表示法小结2.补码加法补码加法补码加法的公式补码加法的公式: (设设x、y为两个为两个n位定点整数位定点整数)补补补补补补 (mod 2n+1)补码的加法补码的加法即：在模数即：在模数2n+1意义下意义下, ,任意两个任意两个n位位整数的补码之和等整数的补码之和等于该两数之和的补码于该两数之和的补码。这是补码加法的理论基础这是补码加法的理论基础, ,其结论也适用于定点小数。其结论也适用于定点小数。 两个两个补码可以直接相加，即可得到补码可以直接相加，即可得到“和的补码和的补码”。（符号位直接参与运算符号位直接参与运算）例例：1101, 1001, 求求。解解:补补0,1101

6、 补补1,0111 补补0,1101补补1,0111 补补 10,0100 +0100=+100补码的加法补码的加法最高位为模数最高位为模数自行丢失自行丢失可见，可见，补码加法的特点补码加法的特点为：为： 1、符号位作为数的一部分直接参加运算；、符号位作为数的一部分直接参加运算； 2、超过模数、超过模数(Mod)的进位自动丢掉的进位自动丢掉。 3、补码减法补码减法 由补码的原理可知，补码的减法运算可以通过加由补码的原理可知，补码的减法运算可以通过加法来完成，进而简化运算器的结构。法来完成，进而简化运算器的结构。补码的减法公式如下：补码的减法公式如下：补补补补补补补补 补补即：即： 减法可以变成

7、加法来计算！减法可以变成加法来计算！补码的减法补码的减法方法方法： （以定点整数为例以定点整数为例） 对对已知的已知的补补：连同符号位一起，各位求反、最：连同符号位一起，各位求反、最末位加末位加1，即得到，即得到 补补。 记为：记为：补补 补补1 问题问题：若已知若已知补补，如何求取如何求取补补？对对补补连同符号位一起的求反连同符号位一起的求反例例13 已知已知 1 1101, 2 1110, 求：求： 1补补, 1补补, 2补补, 2补补。 解解: 1补补0,11011补补 1补补11,001011,0011 2补补1,00102补补 2补补10,110110,1110补码的减法补码的减法（

8、见黑板见黑板）例例14 1101, 0110, 求。求。解解 : 补补0,1101补补0,0110 补补1,1010 补补 0,1101补补 1,1010 补补 1 0,0111 00111补码的减法补码的减法已知：已知： xy补补=x补补y补补模数自行丢失模数自行丢失被加数被加数 1 0 1 1 0 1加数加数 0 0 1 1 0 1 和和 进位进位 0 1 1 0 1被加数被加数 1 0 1 1 0 1加数加数 0 0 1 1 0 1 和和 1 1 1 0 1 0如何用硬件电路来实现加法运算呢？如何用硬件电路来实现加法运算呢？半半加加器器全全加加器器0 00 01 01 01 01 00

9、10 10 00 00 10 11 01 01 11 1S S COCOP QP Q半加器真值表半加器真值表1 1半加器半加器- -只考虑本位两个一位二进制数相加，而不考虑来自低位只考虑本位两个一位二进制数相加，而不考虑来自低位进位数相加的运算电路。进位数相加的运算电路。=1P&QSCO 逻辑电路图逻辑电路图 PQCOQPS 输输 入入输输 出出PQ CISCO0000010100111001011101110010100110010111B)(ACI+AB=ABCI+CIAB+CIBA+BCIA=COCIBA=ABCI+CIBA+CIBA+CIBA=S =1&=11ABCISCOPQCICO

10、1位全加器位全加器74183符号符号串行进位加法器串行进位加法器并行（超前）进位加法器并行（超前）进位加法器 按进位信号产生的方法不同分为：按进位信号产生的方法不同分为：1 1四位串行进位加法器四位串行进位加法器S3A3B3C3C01COCICOCICOCICOCIC2C1C0S2S1S0A2B2A1B1A0B0特点特点 ：1. 进位信号逐位由低向高传递；进位信号逐位由低向高传递； 2. 工作速度较慢。工作速度较慢。基本原理基本原理：加到第：加到第i i位的进位输入信号是两个加数第位的进位输入信号是两个加数第i i位以位以前各位（前各位（0 j-10 j-1）的函数，）的函数， 可在相加前由可

11、在相加前由A,BA,B两数确定两数确定。优点优点：快，每：快，每1 1位的位的和和及最后的及最后的进位进位基本同时产生。基本同时产生。 运算速度相当于运算速度相当于2 2位数运算。位数运算。 缺点缺点：电路复杂。高成本。：电路复杂。高成本。2 2超前进位加法器超前进位加法器(74LS283)(74LS283)S3A3B3C3C0-1CICICICI超前进位电路超前进位电路S2S1S0A2B2A1B1A0B0超前进位加法器逻辑结构示意图超前进位加法器逻辑结构示意图C1C0C22 2超前进位加法器超前进位加法器(74LS283)(74LS283)(CI)B(AB)(AB(AB(ABA(CI)BAS

12、)(CI)B(AB)(AB(AB)(AB(ABA)(CI)B(ABA(CO)(CI)B(AB)(AB(ABA(CO)(CI):2i)(CI)B(AB)(AB(ABA)(CO)B(ABA(CO)(CI)B(AB(ABA(CO)BAS(CO)(CI):1i)(CI)B(ABA(CO)(CI)BAS0(CI):0i000001111222222000001111222222222200000111112000001111011111000001101110100000000000 74LS28374LS283超前加法器逻辑功能示意图超前加法器逻辑功能示意图A A0 0A A1 1A A2 2A A3

13、 3B B0 0B B1 1B B2 2B B3 3CICIS S0 0S S1 1S S2 2S S3 3COCO加数加数加数加数和和相邻相邻低位低位进位进位进位进位输出输出【例】【例】 利用利用74LS28374LS283实现将实现将8421BCD8421BCD转换成转换成余余3 3码码。 一个二进制的小数点向左和向右移动一个二进制的小数点向左和向右移动1位分别意味着将该数位分别意味着将该数2和和2，因而在定点数系统中整个数左移，因而在定点数系统中整个数左移1位（最低位输入位（最低位输入0），），就是将数字就是将数字2 。0 0 0 0 0 1 0 100 0 0 1 0 1 0 00 在

14、浮点数系统中，尾数的移动也是如此，但阶码的移动则在浮点数系统中，尾数的移动也是如此，但阶码的移动则意味着指数的意味着指数的2和和2运算。运算。右移右移1位（最高位输入一个位（最高位输入一个0）就是将数字）就是将数字 20 0 0 0 1 0 1 000 0 0 0 1 0 1 00左移前左移前左移后左移后右移前右移前右移后右移后算术移位规则：算术移位规则：o 算术移位：带符号数的移位。移位后数量发生变化。算术移位：带符号数的移位。移位后数量发生变化。o 原码移位：不论正数还是负数，均符号位不变，数值位原码移位：不论正数还是负数，均符号位不变，数值位高位或低位补高位或低位补0；X=0011001

15、0左移一位？左移一位？右移一位呢？右移一位呢？X=10110010左移一位？左移一位？右移一位呢？右移一位呢？o 补码移位：连同符号位一起移；补码移位：连同符号位一起移；o 若是正数，则不论左移还是右移均补若是正数，则不论左移还是右移均补0；o 若是负数，左移空位补若是负数，左移空位补0；右移补；右移补1.算术移位规则：算术移位规则：X=00110010左移一位？左移一位？右移一位呢？右移一位呢？X=10110010左移一位？左移一位？右移一位呢？右移一位呢？ 移位运算一般靠移位寄存器实现。移位寄存器有移位运算一般靠移位寄存器实现。移位寄存器有如下信号：如下信号：使能控制使能控制：控制移位方式

16、（左移、右移、装入等），：控制移位方式（左移、右移、装入等），此信号应维持一个时钟周期的时间长度。此信号应维持一个时钟周期的时间长度。时钟信号：时钟信号：同步控制信号，只有在时钟的作用下电同步控制信号，只有在时钟的作用下电路才能按使能信号规定的操作产生移位或装入（置路才能按使能信号规定的操作产生移位或装入（置数）。数）。移进数据：移进数据：需要左移或右移的需要左移或右移的1 1或或0 0。异步控制：异步控制：寄存器通常都有异步清寄存器通常都有异步清0 0端。端。如图是集成移位寄存如图是集成移位寄存器器74194逻辑图，多逻辑图，多级级联可实现级级联可实现2或或2运算的寄存器电路。运算的寄存器电

17、路。移位寄存器74194S1S011DSLDSR数据输出数据输出数据输入数据输入系统时钟系统时钟装入命令装入命令2命令命令2命令命令CO 处 理 电 路图4.7 移位存储原理另一种实现方法通另一种实现方法通常与数据处理联合常与数据处理联合使用，它将普通寄使用，它将普通寄存器中所存储的数存器中所存储的数据取出处理后再存据取出处理后再存入寄存器时，采用入寄存器时，采用错位存入的方法，错位存入的方法，实现了移位操作。实现了移位操作。1 11 1位数值比较器位数值比较器A B F1 F2 F30 0 0 0 10 1 0 1 01 0 1 0 01 1 0 0 1 表表 1 1位比较器真值表位比较器真

18、值表 11&A1FFFB 解：解：1 1位数值比较器的输入位数值比较器的输入是两个要进行比较的是两个要进行比较的1 1位二进位二进制数，这里用制数，这里用A A、B B表示，输表示，输出用出用F1F1、F2F2和和F3F3表示。设表示。设A AB B时时F1=1F1=1；A AB B时时F2=1F2=1；A=BA=B时时F3=1F3=1。得。得1 1位数值比位数值比较器的真值表较器的真值表BA=F2AB+BA=F3BA=F1 数值比较器是对两个位数相同的二进制数值比较并判断其大小数值比较器是对两个位数相同的二进制数值比较并判断其大小关系的算术运算电路。关系的算术运算电路。 3210=B A=B

19、 AB IAB FAB3A3B2A2B1A1B0A0=BA=BA=BA=BAB4.2 ALU4.2 ALU的组织的组织ALUALU：Arithmetic Logic Unit-Arithmetic Logic Unit-算术逻辑单元。算术逻辑单元。ALUALU是计算机中对数据进行是计算机中对数据进行运算或逻辑处理运算或逻辑处理的的核心部件核心部件4.2.1 4.2.1 加法运算与加法运算与ALUALU的组织的组织4.2.1.1 4.2.1.1 加法加法ALUALU的基本结构的基本结构累加器累加器A全加器全加器ADD寄存器寄存器B到存储器到存储器来自存储器来自存储器 在计算机中，参加运算的数在计

20、算机中，参加运算的数（操作数）是放在（操作数）是放在存储器存储器中的，做中的，做加法运算时，需将它们从存储器取加法运算时，需将它们从存储器取出，放在操作数出，放在操作数寄存器寄存器中，然后在中，然后在加法操作命令加法操作命令下完成加法操作。运下完成加法操作。运算结果也应存放在一个算结果也应存放在一个寄存器寄存器中，中，等待存数命令到达时存入存储器。等待存数命令到达时存入存储器。加法的操作过程：加法的操作过程：累加器累加器A全加器全加器ADD寄存器寄存器B到存储器到存储器来自存储器来自存储器（1 1）取）取操作数操作数（被加数被加数MM）存入累加）存入累加器器A A相加，并将和（相加，并将和（M

21、)M)存入累加器存入累加器A A。并行置数并行置数将累加器将累加器A A清除；清除；清除（清除（CLR)取操作数取操作数MM存入寄存器存入寄存器B;B; 并行置数并行置数累加器累加器A全加器全加器ADD寄存器寄存器B到存储器到存储器来自存储器来自存储器（2 2）取另一操作数（加数）取另一操作数（加数N N）与）与MM相相加，并将和数存入累加器加，并将和数存入累加器A A。MNMNM+N计算机指令计算机指令ADDADD（3 3）将和数）将和数存入存储器存入存储器 存储指令存储指令STOSTO4.2.1.2 4.2.1.2 关于加法运算的一些考虑关于加法运算的一些考虑补码加减运算的基本规则：补码加

22、减运算的基本规则： 参加运算的各个操作数均以参加运算的各个操作数均以补码补码表示，表示结果仍以表示，表示结果仍以补码补码表示。表示。 按二进制按二进制“逢二进一逢二进一”规则运算。规则运算。 符号位与数值位符号位与数值位一起一起参与参与运算运算，结果的，结果的符号位符号位由运算得出。由运算得出。 进行补码加法时，将两补码数直接进行补码加法时，将两补码数直接相加相加，得到两数，得到两数之和之和的补码；的补码；进行补码减法时，将减数求补，然后相加，得到两数进行补码减法时，将减数求补，然后相加，得到两数之差之差的补的补码。码。 补码总是对确定的模而已，如果运算结果超过了模，则自动补码总是对确定的模而

23、已，如果运算结果超过了模，则自动溢溢出。出。溢出概念与检测方法溢出概念与检测方法 在运算过程中在运算过程中, ,如数值的大小超出其字长所能表示的如数值的大小超出其字长所能表示的范围范围, ,则称为则称为“溢出溢出”。 这在计算机中是不允许的！这在计算机中是不允许的！那么，那么， 如何判断定点数的计算出现了如何判断定点数的计算出现了“溢出溢出”？ “溢出溢出”的特征是什么？的特征是什么？溢出概念与检测方法溢出概念与检测方法见后例见后例（1 1）溢出问题）溢出问题 （OverflowOverflow） 溢出判别电路溢出判别电路 电路设计思路：电路设计思路：两个两个正数正数相加时，溢出表现在和的符号

24、位为相加时，溢出表现在和的符号位为1 1；两个两个负数负数相加时，溢出表现在和的符号位为相加时，溢出表现在和的符号位为0 0。一个一个正数正数和一个和一个负数负数相加是相加是不会产生溢出不会产生溢出。可根据两个操作数的符号位可根据两个操作数的符号位A An n、B Bn n和和 和数的符号位和数的符号位n n来判断来判断是否有溢出。是否有溢出。 An + Bn n An Bn n Ovr 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 0 Ovr =An Bn n + AnBn n 图图4.12 溢出判断电路溢出判断电

25、路111&nAnBnOvr例例1 1011, , 1001, 求求。解解:补补0,1011 补补0,1001 补补 0,1011 补补0,1001 补补1,0100 01101 两正数相加，结果正确，无溢出两正数相加，结果正确，无溢出.溢出概念与检测方法溢出概念与检测方法无进位无进位无进位无进位例例 1101, , 1011, 求求。解解: 补补1,0011 补补1,0101 补补 1,0011 补补 1,0101 补补 1 0,1000 0,1000 0两负数相加，结果为正，显然错误。两负数相加，结果为正，显然错误。 （运算中出现了（运算中出现了“下溢下溢”）溢出概念与检测方法溢出概念与检测

26、方法无进位无进位有进位有进位+1000 ?模数自模数自行丢失行丢失可见，计算结果溢出的特征为可见，计算结果溢出的特征为： 两个正数相加两个正数相加, ,结果为负结果为负, ,称为称为上溢上溢。 （即：（即：计算结果大计算结果大于机器所能表示的最大正数于机器所能表示的最大正数） 两个负数相加两个负数相加, ,结果为正称为结果为正称为下溢下溢。 （即：（即：计算结果小计算结果小于机器所能表示的最小负数于机器所能表示的最小负数) )产生产生“溢出溢出”的原因的原因： 运算过程中，当最高有效数值位的运算过程中，当最高有效数值位的运算进位运算进位与符号位的与符号位的运运算进位算进位不一致时，将产生运算不

27、一致时，将产生运算“溢出溢出”。溢出概念与检测方法溢出概念与检测方法“溢出溢出”检测方法检测方法： 可采用两种方法进行可采用两种方法进行“溢出溢出”检测。检测。（1 1）检测方法检测方法1 1： “ “单符号位法单符号位法”。从例题中看到从例题中看到: : 设：符号位运算进位设：符号位运算进位C Cf f，最高有效位运算最高有效位运算进位进位C Cn n-1-1，当当 C Cf fC Cn-1n-1时，即产生时，即产生“溢出溢出”。 溢出逻辑表达式为溢出逻辑表达式为： V VC Cf fC Cn n-1-1（显然：（显然：用异或门即可方便地得到溢出信号用异或门即可方便地得到溢出信号V=1V=1

28、） 在定点机中，机器会自动检查运算结果是否发生溢在定点机中，机器会自动检查运算结果是否发生溢出出, ,若溢出，则要进行中断处理若溢出，则要进行中断处理。 VCf Cn-1溢出溢出（2 2）检测方法检测方法2 2： 双符号位法双符号位法，又称为，又称为“变形补码法变形补码法”. .溢出概念与检测方法溢出概念与检测方法补补0,1011 补补00,1011 y补补1,0111 y补补11,0111 变形补码变形补码: 将符号位由一位扩展为二位，如：将符号位由一位扩展为二位，如： 两个符号位两个符号位Sf1、Sf2与数值一样，都直接参加运算与数值一样，都直接参加运算； 最高符号位上若产生进位最高符号位

29、上若产生进位Cf1，则被自然丢掉则被自然丢掉。 直接根据结果的双符号位，即可判断是否直接根据结果的双符号位，即可判断是否“溢出溢出”。溢出概念与检测方法溢出概念与检测方法注意，在用变形补码运算时注意，在用变形补码运算时：溢出检测方法溢出检测方法： 采用变形补码后，两个补码相加，如果结果的双采用变形补码后，两个补码相加，如果结果的双符号位出现符号位出现“01”或或“10”两种组合时两种组合时, 则表示发生则表示发生溢出溢出。VSf1 Sf2溢出逻辑式为：溢出逻辑式为： 两个符号位两个符号位其中：其中：Sf1、Sf2分别为最高符号位和第二符号位分别为最高符号位和第二符号位 例例14 14 1100

30、, 1000，用变形补码法，用变形补码法 计算：计算：。溢出概念与检测方法溢出概念与检测方法 解解 : 补补00,1100,补补00,1000 补补 00,1100 补补 00,1000 01,0100 两个符号位出现两个符号位出现“01”, 表示已溢出表示已溢出。（上溢）上溢） *(正确的符号位正确的符号位)即：即： 结果溢出结果溢出 ！（见黑板见黑板） 又又例例 1100, 0001，求求。溢出概念与检测方法溢出概念与检测方法 解解 : 补补00,1100,补补00,0001 补补 00,1100 补补 00,0001 00,1101 两个符号位两个符号位 =“00”, 表示表示无溢出无溢

31、出。+1101 结果准确结果准确(正确的符号位正确的符号位) 例例1515 1100, -0110, 求求溢出概念与检测方法溢出概念与检测方法 解解 : 补补11,0100,补补11,1010 补补11,0100补补11,1010 10,1110 两个符号位出现两个符号位出现“10”, ,表示已溢出表示已溢出。( (下溢下溢) ) 溢出溢出！ （正确的符号位）正确的符号位）溢出概念与检测方法溢出概念与检测方法小结小结：当以变形补码运算当以变形补码运算, ,运算结果的双符号位运算结果的双符号位相异相异时时, ,表示表示溢出溢出；相同相同时时, ,则表示则表示未溢出未溢出。1.1.两变形补码相加，

32、两变形补码相加，不论结果是否溢出不论结果是否溢出, ,最高符号位最高符号位S Sf f1 1总是给出结果的正确符号总是给出结果的正确符号。4.2.2 4.2.2 减法运算与求补电路减法运算与求补电路累加器累加器A全加器全加器ADD求补电路求补电路到存储器到存储器来自存储器来自存储器寄存器寄存器B思考：如何利用加法器设计实思考：如何利用加法器设计实现减法电路？现减法电路？a a0 0a a1 1a a2 2a a3 3A A0 0A A1 1A A2 2A A3 3B B0 0B B1 1B B2 2B B3 3CICIS S0 0S S1 1S S2 2S S3 3COCOb b0 0b b1

33、 1b b2 2b b3 3& & & & & & & & & & &1P Q CICO41P Q CICO31P Q CICO21P Q CICO11P Q CICO0111111Q4Q3Q2Q1Q0P3P4P2P1P0ADDSUB求补电路是将减数取反，同时在末位加求补电路是将减数取反，同时在末位加1 1。& & &1P Q CICO01Q0P01ADDsub二进制加法二进制加法/减法器减法器n位位行波进位行波进位补码加补码加/减器逻辑电路减器逻辑电路(一位全加器一位全加器)运算运算控制控制4.2.3 定点乘法运算定点乘法运算 1 原码并行乘法原码并行乘法2 补码并行乘法补码并行乘法*定点乘

34、法运算定点乘法运算原码并行乘法原码并行乘法1. 1. 算法分析算法分析已知：原码的数值部分为其真值的绝对值（正值）已知：原码的数值部分为其真值的绝对值（正值） 两个原码可以直接相乘，非常方便。两个原码可以直接相乘，非常方便。 运算规则运算规则为：为： 乘积的数值部分是两个数值相乘之积；而乘积的符乘积的数值部分是两个数值相乘之积；而乘积的符号位则由两数的符号位号位则由两数的符号位“异或异或”运算即可得到运算即可得到。原码乘法运算原码乘法运算设：设：n位被乘数和乘数用位被乘数和乘数用定点整数定点整数表示表示:被乘数被乘数 原原n ,n110乘数乘数 原原n ,n110 则乘积则乘积(=)的原码为：

35、的原码为：原原z zn, (n110)(n110)式中式中: z zn(n n) 为乘积的符号。为乘积的符号。 注意到：注意到： 原码做乘法运算时，符号位不参与计算，只原码做乘法运算时，符号位不参与计算，只需完成数值部分的相乘运算即可需完成数值部分的相乘运算即可。4.2.3 4.2.3 乘法的实现与乘法的实现与ALUALU结构结构 乘法是加法的扩展，因此可用全加器通过乘法是加法的扩展，因此可用全加器通过一定算法一定算法实现。实现。常用算法有常用算法有连加法连加法和和移位相加移位相加法。法。4.2.3.1 4.2.3.1 连加法连加法MM* *N, N, 就是将就是将MM连续相连续相加加 N N

36、次。次。累加器累加器A全加器全加器ADD到存储器到存储器来自存储器来自存储器寄存器寄存器Y递减计数器递减计数器C来自存储器来自存储器被乘数被乘数MM乘数乘数N N乘积乘积P P思路：每做一次加法，递减思路：每做一次加法，递减计数器减计数器减1 1，减至，减至0 0，MM刚好刚好被加了被加了N N次。次。AA+Y (加加N次）次）CC-1 （计（计N次）次）设设1101,1011. 先用习惯方法求其乘积先用习惯方法求其乘积,观察其过程观察其过程: 1 1 0 1 (x) 1 0 1 1 (y) 1 1 0 1 1 1 0 1 0 0 0 0+ 1 1 0 1 1 0 0 0 1 1 1 1 (z

37、 z)（手工计算过程手工计算过程） 这种手工算这种手工算法若用于计算法若用于计算机，存在什么机，存在什么问题？问题？问题一问题一：机器字通常固定为：机器字通常固定为n位长位长, 运算器也是运算器也是n位长，位长，而两个而两个n位二进制数相乘位二进制数相乘, 乘积可能为乘积可能为2n位。位。问题二问题二：加法器每次加法器每次只能进行只能进行两个操作数两个操作数的的相相加，无加，无法实现法实现n n个部分积的同时相加。个部分积的同时相加。原码乘法运算原码乘法运算 1 1 0 1 (x) 1 0 1 1 (y) 1 1 0 1 1 1 0 1 0 0 0 0+ 1 1 0 1 1 0 0 0 1 1

38、 1 1 (z z)问题如何解决？问题如何解决？本例字长本例字长n=4位位乘积字长乘积字长8位位=2n超出运算超出运算器字长器字长 解决方法解决方法 ： 早期计算机中为了简化硬件结构早期计算机中为了简化硬件结构, 采用逐次执行采用逐次执行“加法加法移位移位”的软件串行操作来实现。但是的软件串行操作来实现。但是运算速运算速度太慢度太慢，目前已淘汰，目前已淘汰。 目前普遍使用的是流水式目前普遍使用的是流水式阵列乘法器阵列乘法器, 它们属于它们属于并行乘法器并行乘法器。结构分析：结构分析：实现上述乘法过程所需要的操作和人们的习惯方法非常类似实现上述乘法过程所需要的操作和人们的习惯方法非常类似： am

39、-1 am-2 a1 a0 bn-1 b1 b0 am-1b0 am-2b0 a1b0 a0b0 am-1b1 am-2b1 a0b1+ am-1bn-1 am-2bn-1 a0bn-1 pm+n-1 pm+n-2 pm+n-3 pn-1 p1 p0原码乘法运算原码乘法运算 乘积乘积P Pn位乘数位乘数Bm位被乘数位被乘数A A位积因子位积因子位积因子位积因子所有的位积因子都是所有的位积因子都是“与与”逻辑逻辑同时生成所有同时生成所有的位积因子的位积因子阵列乘法器逻辑结构阵列乘法器逻辑结构：加法器阵列加法器阵列与门阵列与门阵列 am-1 am-2 a1 a0 bn-1 b1 b0 am-1b0

40、 am-2b0 a1b0 a0b0 am-1b1 am-2b1 a0b1+ am-1bn-1 am-2bn-1 a0bn-1 pm+n-1 pm+n-2 pm+n-3 pn-1 p1 p0原码乘法运算原码乘法运算由由“与门阵列与门阵列”同同时时生成全部位积因子生成全部位积因子一位加法器一位加法器 若乘法器为若乘法器为mn位时位时,需要需要mn个个“与门与门”和和m(n1)个个“全加器全加器”。55位阵位阵列乘法器列乘法器思考：用一个思考：用一个4 4位二进制并行加法器和六个与门位二进制并行加法器和六个与门设计一个乘法器，实现设计一个乘法器，实现A AB,B,其中其中A=a3a2a1,B= A=

41、a3a2a1,B= b2b1. b2b1. 74283对负数的补码再对负数的补码再求一次补，即可求一次补，即可得到对应的原码得到对应的原码若输入乘法器的两数是补码：若输入乘法器的两数是补码：x补补、y补补， 例：例：x=+(21)10=+10101 x补补=0,10101 y=-(25)10=-11001 y补补=1,00111那么，那么， x补补、y补补能够直接送入无符号乘法器运算，能够直接送入无符号乘法器运算， 即：即：x补补y补补=xy 补补吗？吗？2.2.带符号的阵列乘法器带符号的阵列乘法器-补码乘法器补码乘法器结论不对结论不对！原因？原因？ 负数补码数值的变化！负数补码数值的变化！解

42、决方法解决方法： 将将x补、补、y补补转换成对应的原码转换成对应的原码：x原原、y原原，再把数值部分送入无符号乘法器，完成数值的乘法再把数值部分送入无符号乘法器，完成数值的乘法运算。运算。算前求补算前求补移位相加乘法器移位相加乘法器算后求补算后求补 P P2n-12n-1 P P0 0B Bn-1n-1 B B0 0A An-1n-1 A A0 0算前求补算前求补 =1=1P P2n2nA An n B Bn n被乘数被乘数乘数乘数 补码运算时，应将两个补码运算时，应将两个补码表示的数取绝对值，补码表示的数取绝对值，而乘积的符号位用异或逻而乘积的符号位用异或逻辑求得。辑求得。运算结果：当经异或

43、处理运算结果：当经异或处理后的值为后的值为1 1时，说明乘积的时，说明乘积的结果为结果为负负，还需将绝对值，还需将绝对值表示的乘积表示的乘积再求补再求补。2 2 补码乘法运算补码乘法运算(1) 求补器的电路实现求补器的电路实现 已知，一个负数的常规求补过程：已知，一个负数的常规求补过程： 例：例： X= -1110， 则：则：X补补=1,0010 ； Y= -0100，则：，则： Y补补=1,1100算法特点算法特点：从数据的最右边开始向左边逐位扫描从数据的最右边开始向左边逐位扫描。 求补算法的求补算法的电路实现电路实现： 一个具有使能控制的二进制数求补器电路。一个具有使能控制的二进制数求补器

44、电路。 带符号的阵列乘法器带符号的阵列乘法器 E=0时时： A*=AE=1时启动求补时启动求补：A*=A补补A=A*=符号位符号位符号位符号位乘积的乘积的符号位符号位EEE4.2 定点除法运算定点除法运算 定点除法运算定点除法运算4.2.1 原码除法算法原理原码除法算法原理4.2.2 并行除法器并行除法器基本原理基本原理： 两个两个原码数原码数相除时相除时: : 商的符号单独处理（商的符号单独处理（两数的符号位两数的符号位“异或异或” ）；）；1.1. 商的数值部分由两数的数值部分直接相除求得商的数值部分由两数的数值部分直接相除求得* *。原码除法运算原理原码除法运算原理4.2.1 4.2.1

45、 原码除法运算原理原码除法运算原理商的求法商的求法：商的商的数值数值部分的运算，实质上是部分的运算，实质上是两个正数两个正数求商求商的运算的运算，商的符号位单独商的符号位单独“异或异或”获得。获得。 原码除法原码除法只需考虑两个正数相除即可只需考虑两个正数相除即可。1 1 除法除法ALUALU的基本结构的基本结构试除法试除法符号：正正得正，正负得负符号：正正得正，正负得负数值部分：比较法，若干次减法数值部分：比较法，若干次减法+移位构成移位构成除数除数 11 1 1 1 0 1 0 1 0 0 1 1 1 1 0 1 0 1 1 1 1 0 0 1 1 1 商商 被除数被除数 部分余数部分余数

46、 部分余数部分余数 余数余数够减，够减，商商1,减除减除数数不够减，不够减，商商0,不减不减不够减，不够减，商商0,不减不减够减，够减，商商1,减除减除数数每一次除数都要右移一位，然后与余数做比较每一次除数都要右移一位，然后与余数做比较比较法规则：比较法规则： 商的各位是通过比较余数（初始时是被除数）与除数的大商的各位是通过比较余数（初始时是被除数）与除数的大小得到的。若余数大于除数，则商为小得到的。若余数大于除数，则商为1，将余数减去除数，将余数减去除数，若余数小于除数，则商为若余数小于除数，则商为0.再把除数右移一位与余数作比再把除数右移一位与余数作比较。较。 每次做减法时，总是余数不动，

47、低位补每次做减法时，总是余数不动，低位补0，再与右移的除，再与右移的除数相减。数相减。 商的符号单独处理。商的符号单独处理。比较方法：比较方法： 比较器。耗费资源。比较器。耗费资源。 用减法代替。用减法代替。问题：问题： 用减法电路替代比较器时，若不够减，进行减法后，余数用减法电路替代比较器时，若不够减，进行减法后，余数已经被减去了，怎么办？已经被减去了，怎么办？ 除数每次右移一位，故全加器位数增多，器件规模增大？除数每次右移一位，故全加器位数增多，器件规模增大？ 如何实现把求得的商逐个存储？如何实现把求得的商逐个存储？解决办法：解决办法： 用恢复余数法或不恢复余数法解决。用恢复余数法或不恢复

48、余数法解决。4.2.4.2 4.2.4.2 恢复余数法操作过程恢复余数法操作过程 当当不够减不够减时已经减掉了除数，时已经减掉了除数，加上除数加上除数，恢复到未减时的，恢复到未减时的值，此法称值，此法称恢复余数法。恢复余数法。 商商 被除数被除数第一次部分余数（正）第一次部分余数（正）第二次部分余数（负）第二次部分余数（负） 恢复原来的余数恢复原来的余数第三次部分余数（负）第三次部分余数（负） 恢复原来的余数恢复原来的余数第四次部分余数（正）第四次部分余数（正）第五次部分余数（正）第五次部分余数（正） 余数余数特点：部分余特点：部分余数不动，除数数不动，除数右移右移减除数减除数, ,余余数为正

49、数为正, ,商商1 1除数右移除数右移减除数减除数, ,余余数为负数为负, ,商商0 0加除数加除数 1 1 0 1 1 除数除数 11 0 1 1 1 0 1 1 0 1 1 0 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 1 1 1 0 1 1 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0计算机完成除法时，计算机完成除法时，需考虑需

50、考虑到：到： 1、由于计算机中小数点位置固定，为便于机器操作，、由于计算机中小数点位置固定，为便于机器操作，计算机常采用计算机常采用 “余数左移余数左移”的方法来替代的方法来替代“除数右移除数右移”。 2、机器不能直接判断够不够减：必须先作减法，若余数、机器不能直接判断够不够减：必须先作减法，若余数为正，则为为正，则为够减；若余数为负，则不够减。够减；若余数为负，则不够减。 发现发现不够减时，必须恢复原来的余数，才能继续往下不够减时，必须恢复原来的余数，才能继续往下运算。这种方法又称为运算。这种方法又称为恢复余数法恢复余数法。 由于要恢复余数，使计算的效率降低，同时使除法过由于要恢复余数，使计算的效率降低，同时使除法过程的程的步数不固定步数不固定，因此控制比较复杂。，因此控制比较复杂。定点除法运算定点除法运算 由于恢复余数法中包含有一些无效（冗余）运由于恢复余数法中包含有一些无效（冗余）运算，算，且运算且运算步数不固定步数不固定，实际中，一般采用实际中，一般采用不恢复不恢复余数法余数法，又称又称加减交替法加减交替法。4.2.4.2 4.2.4.2 不恢复余数法操作过程不恢复余数法操作过程 不恢复余数法不恢复余数法是在恢复余数法的基本步中当部分余数减去是在恢