计算机算法和算法逻辑实现 课件.ppt

计 算 机 组 成 原 理,第六-八讲,计算机算法和算法逻辑实现,1、定点数加减法运算及电路实现补码的加减法运算，全加器，溢出，快速加法运算（进位链），74181ALU2、定点数乘除运算和电路实现原码、补码，布斯算法，原码恢复余数、不恢复余数3、快速乘除法运算技术和电路实现布斯高基乘法，阵列乘法器，阵列除法器4、浮点数四则运算以及实现加减乘除,本讲安排,本讲将解决的主要问题,掌握计算机算法。加减乘除运算方法和运算器的构成，原码和补码的加减乘除四则运算，浮点数的四则运算。,补码加、减法,溢出概念与检测方法,基本的二进制加法/减法器,十进制加法器,加法规则： 先判符号位，若相同，绝对值相加，结果符号不变; 若不同，则作减法， |大| - |小|，结果符号与|大|相同。减法规则： 两个原码表示的数相减，首先将减数符号取反，然后将被减数与符号取反后的减数按原码加法进行运算。,补码加法,1.原码加/减法运算,补码加法的公式:, x 补 y 补 xy 补 (mod 2),在模2意义下,任意两数的补码之和等于该两数之和的补码。 这是补码加法的理论基础。,2.补码加法运算,特点：不需要事先判断符号，符号位与码值位一起参加运算。 符号位相加后若有进位，则舍去该进位数字。,假设采用定点小数表示,因此证明的先决条件是: x1, y1, xy1。,(1) x0, y0, 则 xy0。 相加两数都是正数,故其和也一定是正数。正数的补码和原码是一样的,可得： x 补 y 补xy xy 补(mod 2),公式证明:,(2) x0, y0, 则 xy0 或 xy0 时, 2+ (x+y) 2, 进位2必丢失, 又因 (x+y)0， 故 x补 y补xy xy补 (mod 2) 当xy0时, 2 (xy) 2, 又因 (x+y)0， 故x补y补2(xy)xy补(mod 2),(3) x0, 则 xy0 或 xy0。 同(2),把 x 和 y 的位置对调即可。 (4) x0, y0, 则 xy0。 相加两数都是负数,则其和也一定是负数。x补2x, y补2yx补 y补2x2y2(2xy) 因为|xy|1, 1(2xy)2, 2(2xy) 进位2 必丢失，又因x+y0 故 x补 y补2(xy) xy补(mod 2),至此证明了在模2意义下，任意两数的补码之和等于该两数之和的补码。 其结论也适用于定点整数。补码加法的特点： （1）符号位要作为数的一部分一起参加运算； （2）在模2的意义下相加，即大于2的进位要丢掉。,结论：,例: x0.1001, y0.0101, 求 xy。,解: x补0.1001, y补0.0101 x补0.1001 y补 0.0101 xy 补 0.1110,所以 xy0.1110,例: x0.1011, y0.0101, 求 xy。,所以 xy0.0110,解: x补0.1011,y补1.1011 x补0.1011y补1.1011 xy补 10.0110,补码减法,减法运算要设法化为加法完成,补码减法运算的公式： xy 补 x 补 y 补 x 补y 补,公式证明： 只要证明y补 y补, 上式即得证。,xy补x补 y补(mod 2) 令 y= x0补x补 + x补故 x补 x补 (mod 2),证明：,例: x0.1101, y0.0110, 求 xy。,解:x补0.1101 y补0.0110,y补1.1010 x补 0.1101 y补 1.1010 xy补 10.0111,xy0.0111,解： x补=1.0011 y补=1.1010 -y补=0.0110 x补 1.0 0 1 1 + -y补 0.0 1 1 0 x-y补 1.1 0 0 1,例： x= -0.1101，y= -0.0110，求x-y=?,x-y = -0.0111,溢出及与检测方法,在定点小数机器中,数的表示范围为|1。在运算过程中如出现大于1的现象,称为 “溢出”。,1. 概念,解： x补=0.1011 y补=0.1001 x补 0. 1 0 1 1 + y补 0. 1 0 0 1 x+y补1. 0 1 0 0 两个正数相加的结果成为负数，这显然是错误的。,例: x=+0.1011, y=+0.1001, 求x+y。,例: x= -0.1101, y= -0.1011, 求x+y。,解： x补=1.0011 y补=1.0101 x补 1. 0 0 1 1 + y补 1. 0 1 0 1 x+y补 0. 1 0 0 0 两个负数相加的结果成为正数，这同样是错误的。,发生错误的原因，是因为运算结果产生了溢出。两个正数相加: 结果大于机器所能表示的最大正数，称为上溢；两个负数相加：结果小于机器所能表示的最小负数，称为下溢。,分析 ：,2.溢出的检测方法,x补 0. 1 0 1 1 + y补 0. 1 0 0 1 x+y补1. 0 1 0 0,x补 1. 0 0 1 1 + y补 1. 0 1 0 1 x+y补 0. 1 0 0 0,(1) 单符号位法,判断电路,一个符号位只能表示正、负两种情况，当产生溢出时，符号位的含义就会发生混乱。如果将符号位扩充为两位(Sf1、Sf2)，其所能表示的信息量将随之扩大，既能判别是否溢出，又能指出结果的符号。,(2) 双符号位法,双符号位法也称为“变形补码”或“模4补码” 。,变形补码定义：, 任何小于1的正数： 两个符号位都是“0”，即 00.x1x2.xn; 任何大于-1的负数：两个符号位都是“1”，即 11.x1x2xn,两数变形补码之和等于两数和的变形补码，要求： 两个符号位都看做数码一样参加运算； 两数进行以4为模的加法，即最高符号位上产生的进位要丢掉,模4补码加法公式： x补+ y补=x+y补 （mod 4),采用变形补码后数的表示：,Sf1Sf2 00 结果为正数，无溢出 01 结果正溢 10 结果负溢 11 结果为负数，无溢出,即：结果的两个符号位的代码不一致时，表示溢出; 两个符号位的代码一致时，表示没有溢出。 不管溢出与否，最高符号位永远表示结果的正确符号。,溢出逻辑表达式为： VSf1Sf2 中Sf1和Sf2分别为最高符号位和第二符号位，此逻辑表达式可用异或门实现。,双符号位的含义如下：,解： x补=00.1100 y补=00.1000 x补 0 0. 1 1 0 0 + y补 0 0. 1 0 0 0 0 1. 0 1 0 0 符号位出现“01”，表示已溢出，正溢。即结果大于+1,例 x= +0.1100, y= +0.1000, 求x+y。,解： x补=11.0100 y补=11.1000 x补 1 1.0 1 0 0 + y补 1 1.1 0 0 0 1 0. 1 1 0 0符号位出现“10”，表示已溢出，负溢出。即结果小于-1,例 x= -0.1100, y= -0.1000, 求x+y。,从上面例中看到： 当最高有效位有进位而符号位无进位时,产生上溢； 当最高有效位无进位而符号位有进位时,产生下溢。 （简单地说是正数相加为负数或负数相加为正数则产生溢出） 故溢出逻辑表达式为： VCfCo 其中Cf为符号位产生的进位,Co为最高有效位产生的进位。此逻辑表达式也可用异或门实现。,(3) 利用进位值的判别法,x补0 0. 1 1 0 0+y补0 0. 1 0 0 00 1. 1 0 0 0,x补1 1.0 1 0 0+y补1 1.1 0 0 01 0.1 1 0 0,VC1Co,VSf1Sf2,判断电路,基本的二进制加法/减法器,1.一位全加器,逻辑电路（一位全加器）,常用的全加器逻辑电路,逻辑符号,2.n位的行波进位加减器,n个1位的全加器(FA)可级联成一个n位的行波进位加减器。,T被定义为相应于单级逻辑电路的单位门延迟。 T通常采用一个“与非”门或一个“或非”门的时间延迟来作为度量单位。,3.n位的行波进位加法器的问题,时间延迟,(1)对一位全加器(FA)来说，Si的时间延迟为6T(每级 异或门延迟3T)；Ci1的时间延迟为5T。,3T,3T,T,T,(2) n位行波进位加法器的延迟时间ta为:, 9T为最低位上的两极“异或”门再加上溢出“异或”门的总时间； 2T为每级进位链的延迟时间。,tan2T9T(2n9)T,考虑溢出检测时，有：,当不考虑溢出检测时，有：ta(n-1)2T9T,ta为在加法器的输入端输入加数和被加数后,在最坏的情况下加法器输出端得到稳定的求和输出所需要的最长时间。 ta越小越好。,缺点：(1)串行进位,它的运算时间长；(2)只能完成加法和减法两种操作而不能完成逻辑操作。 多功能算术/逻辑运算单元(ALU): 不仅具有多种算术运算和逻辑运算的功能； 而且具有先行进位逻辑。 从而能实现高速运算。,由一位全加器(FA)构成的行波进位加法器:,1.基本思想,SiAiBiCi,一位全加器(FA)的逻辑表达式为:,将Ai和Bi先组合成由控制参数S0,S1,S2,S3控制的组合函数Xi和Yi；(2)然后再将Xi,Yi和下一位进位数通过全加器进行全加。这样,不同的控制参数可以得到不同的组合函数,因而能够实现多种算术运算和逻辑运算。,解决方案：,多功能算术/逻辑运算单元(ALU),将全加器的功能扩展以完成多种算术逻辑运算。,= AiBiBiCiCiAi,参数S0 ,S1 ,S2 ,S3 分别控制输入Ai 和Bi ,产生Y和X的函数。其中：Yi是受S0 ,S1控制的Ai和Bi的组合函数；Xi是受S2 ,S3控制的Ai和Bi组合函数。,函数关系如表所示。, 核心部分是由两个半加器组成的全加器。 由M控制第二级半加器选择逻辑运算或 算术运算（所需的低位进位Cn ）。,一位ALU基本逻辑电路,进一步化简:,FiYiXiCn+i Cni1YiXiCni,综上所述，ALU的一位逻辑表达式为：,FiYiXiCn+i Cni1YiXiCni,4位之间采用先行进位（并行进位）公式。 根据 Cni1YiXiCni ，每一位的进位公式可递推如下： 第0位向第1位的进位公式为: Cn1Y0X0Cn (其中Cn是向第0位（末位）的进位) 第1位向第2位的进位公式为: Cn2Y1X1Cn1Y1Y0X1X0X1Cn 第2位向第3位的进位公式为: Cn3Y2X2Cn2Y2Y1X1Y0X1X2X0X1X2Cn 第3位的进位输出（即整个4位运算进位输出）公式为: Cn4 =Y3+X3Cn3 =Y3+Y2X3+Y1X2X3+Y0X1X2X3+X0X1X2X3Cn,4位ALU的进位关系及逻辑电路,Cn1Y0X0CnCn2Y1X1Cn1Y1Y0X1X0X1CnCn3Y2X2Cn2Y2Y1X1Y0X1X2X0X1X2CnCn4 =Y3+X3Cn3 =Y3+Y2X3+Y1X2X3+Y0X1X2X3+X0X1X2X3Cn Cn+4是最后进位输出。 逻辑表达式表明, 这是一个先行进位逻辑。换句话说, 第0位的进位输入Cn可以直接传送到最高位上去,因而可以实现高速运算。 下图为用上述原始推导公式实现的4位算术/逻辑运算单元(ALU) 74181ALU,从进位关系上看,正逻辑表示的74181,第3位的进位输出（即整个4位运算进位输出）公式为: Cn4 =Y3+X3Cn3 =Y3+Y2X3+Y1X2X3+Y0X1X2X3+X0X1X2X3Cn设 GY3Y2X3Y1X2X3Y0X1X2X3 PX0X1X2X3 则 Cn4GPCn 其中G称为进位发生输出,P称为进位传送输出。 在电路中多加这两个进位输出的目的,是为了便于实现多片（组）ALU之间的先行进位。,P和G的含义,负逻辑表示的74181,2.算术逻辑运算的实现,上图中控制端用来控制ALU进行算术运算还是进行逻辑运算:0时： 对进位信号没有任何影响。此时Fi 不仅与本位的被操作数Yi 和操作数Xi 有关, 而且与向本位的进位值Cn+i 有关, 因此0时, 进行算术操作。 1时： 封锁了各位的进位输出, 即Cn+i 0, 因此各位的运算结果Fi 仅与Yi 和Xi 有关, 故1时, 进行逻辑操作。,下图为工作于负逻辑和正逻辑操作方式的74181ALU方框图。两种操作是等效的。, 对正逻辑操作数来说： 算术运算称高电平操作； 逻辑运算称正逻辑操作 (即高电平为“1”,低电平为“0”)。 对于负逻辑操作数来说: 正好相反。,(1) H高电平,L低电平；(2) *表示每一位均移到下一个更高位,即A*2A。(3) 算术运算操作是用补码表示法来表示的，其中： “加”是指算术加，运算时要考虑进位； 符号“”是指“逻辑加”。(4) 减法是用补码方法进行的，其中数的反码是内部产生的, 而结果输出“A减B减1”，因此做减法时需在最末位产生一个强迫进位(加1), 以便产生“A减B”的结果。(5) “AB”输出端可指示两个数是否相等；,3.并行加法器的进位逻辑,74181ALU为4位并行加法器， 组成16位的并行加法器怎么办？ 4片(组)74181连接 怎样连？ 组与组之间串行连接 组与组之间并行连接,组间串行进位,C4G0P0 C0,C8G1P1 C4,C12G2P2 C8,C16G3P3 C12,进位关系,Cn1Y0X0CnCn2Y1X1Cn1Y1Y0X1X0X1CnCn3Y2X2Cn2Y2Y1X1Y0X1X2X0X1X2CnCn4 =Y3+X3Cn3 =Y3+Y2X3+Y1X2X3+Y0X1X2X3+X0X1X2X3Cn,组内,组间,GY3Y2X3Y1X2X3Y0X1X2X3 PX0X1X2X3,进位传递时间,(2)组间并行进位两级先行进位的ALU,由串行进位关系,C8 = G1P1 C4 = G1 + P1 (G0P0 C0 ) = G1+G0P1+P0P1C0,得：,C4 = G0P0 C0,C12= G2P2 C8 = G2 + P2 (G1+G0P1+P0P1Cn) = G2+G1P2+G0P1P2+P0P1P2C0,C16 = G3+P3C12 = G3+G2P3+G1P1P2+G0P1P2P3+P0P1P2P3C0 = G*P*C0,其中: P*P0P1P2P3 G*G3G2P3G1P1P2G0P1P2P3,根据上述公式实现逻辑电路:,0,进位的传递时间,由上图可见， 当Xi和Yi形成以后，经过1.5ty，产生第一小组的C1，C2，C3 和所有的Gi、Pi；, 经过1.5ty，由第二级进位链产生C4，C8，C12，C16； 再经1.5ty后，产生第2，3，4小组内的C5C6C7， C9C10C11，C13C14C15。整个进位传递时间为4.5ty。,4.先行进位部件（CLA）74182,74182是一个并行进位部件，其内部结构图如下：,其中G*称为成组进位发生输出，P*称为成组进位传送输出。,Cn+= G0+P0CnCn+= G1+P1Cn+= G1+G0P1+P0P1CnCn+= G2+P2Cn+= G2+G1P2+G0P1P2+P0P1P2CnCn4 = G3+P3Cn+= G3+G2P3+G1P1P2+G0P1P2P3+P0P1P2P3Cn = G*P*Cn其中: P*P0P1P2P3 G*G3G2P3G1P1P2G0P1P2P3,先行进位部件74182CLA所提供的进位逻辑关系如下：,74181ALU设置了P和G两个本组先行进位输出端。 如果将四片74181的P,G输出端送入到74182先行进位部件（CLA）,又可实现第二级的先行进位,即组与组之间的先行进位。,例：16位字长ALU的构成, C3、C7、C11是由74182同时形成的； 其不同点是74182还提供大组间的进位函数G* 和大 组传递条件P*，以便在位数更长时组成下一级先行进 位链。,由图可知：,用若干个74181ALU位片, 与配套的74182先行进位部件CLA在一起, 可构成一个全字长的ALU。,例：全字长的ALU的构成,用两个16位全先行进位部件级联组成的32位ALU逻辑方框图。,十进制加法器,十进制加法器可由BCD码(二十进制码)来设计,它可以在二进制加法器的基础上加上适当的“校正”逻辑来实现。,X+Y+C10不调整,X+Y+C10调整,故： 1. 和为1015时，加6校正； 2. 和数有进位时，加6校正。,和数(4位)有进位调整,1.一位BCD码行波式进位加法器一般结构：,101010111100110111101111,2.n位BCD码行波式进位加法器一般结构：,原码乘法,补码乘法,定点乘法运算,设n位被乘数和乘数用定点小数表示 被乘数 x原xf . xn1 x1x0 乘数 y原yf . yn1 y1y0 则乘积 z原(xfyf)(0. xn1 x1x0)(0. yn1 y1y0) 式中，xf为被乘数符号， yf为乘数符号。,原码一位乘法,1. 乘法的手工算法,(2) 手工运算过程：,设0.1101,0.1011,(1)乘积符号的运算规则：同号相乘为正，异号相乘为负。,(1) 机器通常只有n位长, 两个n位数相乘, 乘积可能为2n位。(2) 只有两个操作数相加的加法器难以胜任将n位积 一次相加起来的运算。,机器与人们习惯的算法不同之处：,0.1 1 0 1 x 0.1 0 1 1 y 0.0 0 0 0 1 1 0 1 x共4次右移 0.0 0 0 1 1 0 1 x共3次右移 0.0 0 0 0 0 0 x共2次右移 + 0.0 1 1 0 1 x共1次右移 0.1 0 0 0 1 1 1 1,2. 适合定点机的形式,为了适合两个操作数相加的加法器，将 xy 改写成下面形式：,xy = x(0.1011) = 0.1x + 0.00 x + 0.001 x + 0.0001 x = 0.1 x+0.1 0 + 0.1 (x+0.1 x) = 2-1 x+ 2-1 0 + 2-1(x+2-1x) ,根据此式，按式中括号可表达的层次，从内向外逐次进行移位累加。,一般而言，设被乘数x,乘数y都是小于1的n位定点正数： x=0.x1x2.xn 1 y=0.y1y2.yn 1,其乘积为：xy=x(0.y1y2.yn ) =x(y12-1 +y22-2 + yn2-n ) = 2-1(y1x+2-1(y2x+2-1(+2-1(yn-1x+2-1(ynx+0),形成递推公式,令zi表示第i次部分积，则根据从内到外的原则有： z0 = 0, z1 = 2-1(ynx+z0) z2 = 2-1(yn-1x+z1) zi = 2-1(yn-i+1x+zi-1) zn = xy = 2-1(y1x+ zn-1)特点：每次只需要相加两个数，然后右移一位。且相加的两个数（部分积和位积）都只有n位，因而不需要2n位的加法器。,3.原码一位乘法流程图,部分积,乘数,说明,最后结果 ： xy=0.10001111,0 0.0 0 0 0 yf 1 0 1 1 z0=0 + 0 0.1 1 0 1 y4=1, +x 0 0.1 1 0 1 0 0.0 1 1 0 1 yf 1 0 1 右移，得z1 + 0 0.1 1 0 1 y3=1, +x 0 1.0 0 1 1 0 0.1 0 0 1 1 1 yf 1 0 右移，得z2 + 0 0.0 0 0 0 y2=0, +0 0 0.1 0 0 1 0 0.0 1 0 0 1 1 1 yf 1 右移，得z3 + 0 0.1 1 0 1 y1=1, +x 0 1.0 0 0 1 0 0.1 0 0 0 1 1 1 1 yf 右移，得z4=xy,例：x=0.1101 , y=0.1011 , 求 xy 。,4.原码一位乘硬件逻辑原理图,计数器：对移位的次数进行计数，以便判断乘法运算是否结束。 当计数器i=n时，计数器i的溢出信号使控制触发器Cx 置0，关闭时序脉冲T，乘法操作结束。,原码一位乘法的主要问题是：符号位不能参与运算，而补码乘法可以实现符号位直接参与运算。,2 补码一位乘法,1.原码一位乘的缺点,2.补码一位乘法的规律推导 采用比较法。比较法是Booth夫妇首先提出来的，又称Booth算法。,设x补 = x0.x1x2xn 当x0时, x0=0，,Booth算法,x补=0.x1x2xn = = x,= -1+ 0.x1x2xn= -1+,x = -x0 +,真值与补码的关系：,当x0时, x0=1， x补=1.x1x2xn = 2 + x x=1.x1x2xn-2,(1)真值和补码之间的关系,在补码机器中，一个数不论其正负，连同符号位向右移一位，符号位保持不变，就等于乘1/2。 设 x补 = x0.x1x2xn, x = -x0 +,= -x0 +,写成补码的形式，即得：,要得到2-ix补,连同符号位右移i位即可,(2) 补码的右移,设被乘数 x补 = x0.x1x2xn 乘数 y补 = y0.y1y2yn 均为任意符号，则有补码乘法算式：, xy 补 = x补 y,(3) 补码乘法规则,1）、当被乘数x符号任意，乘数y符号为正时： 根据补码定义：,由于（y1y2yn)是大于或等于1的正整数，根据模运算性质（大于2的部分全部丢掉）有：2 (y1y2yn) = 2,即：,公式证明,2）、 当被乘数x符号任意，乘数y符号为负时：,又因 ( 0.y1y2yn )0,所以：,(mod2),= x补,= x补 y,为推导出逻辑实现的分步算法，将上式展开得到各项部分积累加的形式。,( yn+1是增加的附加位，初值为0 ),公式展开,将上式改为接近于分步运算逻辑实现的递推关系。,M,M,递推公式,最后一步不移位,由此可见： 每次都是在前次部分积的基础上，由（yi+1-yi ) 决定对x补的操作，然后再右移一位，得到新的部分积；重复进行。,yn+1，yn的作用： 开始操作时，补充一位yn+1 , 使其初始为0。由yn+1 yn 判断进行什么操作；然后再由ynyn-1 判断第二步进行什么操作 。,若 yn yn1 =1 则 yi1-yi =1 做加x补运算；,ynyn1 = 则 yi1-yi= - 做加-x补运算；,则 yi1-yi= 0 zi加0，即保持不变；,补码一位乘的运算规则,(1) 如果 yn=yn+1 ，则部分积 zi 加0，再右移一位；,(2) 如果 yn yn+1=01 ，则部分积 zi 加x补，再右移一位；,(2) 如果 yn yn+1=10 ，则部分积 zi 加-x补, 再右移一位；,如此重复n + 1步，但最后一步不移位。 包括一位符号位，所得乘积为2n+1位，其中n为尾数位数。,算法流程图,0 0.0 0 0 0 1. 0 0 1 1 0 yn+1=0+ 0 0.1 0 1 1 ynyn+1=10, 加-x补 0 0.1 0 1 1 0 0.0 1 0 1 1 1 0 0 1 1 右移一位+ 0 0.0 0 0 0 ynyn+1=11, 加0 0 0.0 1 0 1 0 0.0 0 1 0 1 1 1 0 0 1 右移一位+ 1 1.0 1 0 1 ynyn+1=01, 加x补 1 1.0 1 1 1 1 1.1 0 1 1 1 1 1 1 0 0 右移一位+ 0 0.0 0 0 0 ynyn+1=00, 加0 1 1.1 0 1 1 1 1.1 1 0 1 1 1 1 1 1 0 右移一位+ 0 0.1 0 1 1 ynyn+1=10, 加-x补 0 0.1 0 0 0 1 1 1 1 1 0 最后一位不移位,例：x补=1.0101，y补=1.0011, 求xy补=？ -x补=0.1011,xy补=0.10001111 算法步骤存在错误!,部分积,乘数 yn yn+1,说明,0 0 0 0 0 0 1 0 1 1 0 0 yn+1=0+ 0 0 0 0 0 0 ynyn+1=00, 加0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 右移一位+ 1 1 0 0 1 1 ynyn+1=10, 加-x补 1 1 0 0 1 1 1 1 1 0 0 1 1 0 1 0 1 1 右移一位+ 0 0 0 0 0 0 ynyn+1=11, 加0 1 1.1 0 0 1 1 1.1 1 0 0 1 1 0 1 0 1 右移一位+ 0 0 1 1 0 1 ynyn+1=01, 加x补 0 0 1 0 0 1 0 0 0 1 0 0 1 1 1 0 1 0 右移一位+ 1 1 0 0 1 1 ynyn+1=10, 加-x补 1 1 0 1 1 1 1 1 1 0 1 0 最后一位不移位,x补=001101，y补=10110, -x补=110011,xy补=101111110,部分积,乘数 yn yn+1,说明,例：x=13, y=-10 求xy=？,xy = -01000 0010=-82H=-130,4.补码一位乘逻辑原理图,注被乘数寄存器R2的每一位用原码（触发器Q端）或 反码（触发器Q端）经多路开关送出；送-x补时， 即送R2反码且在加法器最末为加1；(2) R0保存部分积，其符号与加法器符号位f始终一致。(3) 当计数器i=n+1时，封锁LDR1、LDR0信号，使最后 一步不移位。,高基乘法,以上讨论的乘法都只是检查一位二进制位。能否同时检查K位二进制位？以K=2， C=A B为例,如果这两位二进制位为00，则加0,如果这两位二进制位为01，则加A,如果这两位二进制位为10，则加2A,如果这两位二进制位为11，则加3A,2A=4A 2A,3A=4A A,如果这两位二进制位为11，则减A，4A待下一次补上，由于部分积已右移两位，原来加4A变成加A,如何知道有4A的操作哪？两位二进制位为10或11，则加4A,Booth 4基乘法算法,例：A=011011，B=011001 ，计算C=A B 。,0 0 0 0 0 0 0 1 0 1 0 0 1 0 010，加A补+ 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 1 1 0 0 1 0 1 0 1 0 0 算术右移两位+ 0 0 1 1 1 0 0 100, 加-2A补 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 1 算术右移两位+ 0 0 0 1 1 1 0 101， 加-A补 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 算术右移两位,解：A补=110010，B补=101001, -A补=0001110 -2A补=0011100,AB补=0 0 0 0 1 0 1 0 0 0 0 1 0,部分积,乘数 yn-1 yn yn+1,说明,AB =0 0001 0100 0010 =142H =322D,例：A=-14，B=-23 , 求AB=？,1.串行加法器的优劣分析, 不需要很多器件，硬件结构简单； 速度太慢，执行一次乘法操作的时间至少是加法操 作的n倍； 由于乘法操作大约占全部算术运算的1/3，故采用高速乘法部件是非常必要的。,高速乘法部件-阵列乘法器,2.不带符号的阵列乘法器,设有两个不带符号的二进制整数 Aam1a1a0 , Bbn1b1b0它们的数值分别为a和b,即：,在二进制乘法中,被乘数A与乘数B相乘,产生mn位乘积P： Ppmn1p1p0 乘积P 的数值为:,am-1 am-2 a1 a0 ) bn-1 b1 b0 am-1b0 am-2b0 a1b0 a0b0 am-1b1 am-2b1 a1b1 a0b1 . . . . . .+) am-1bn-1 am-2bn-1 a1bn-1 a0bn-1,pm+n-1 pm+n-2 pm+n-3 pn-1 p1 p0,(1) 习惯方法运算过程：,3.带符号的阵列乘法器,(1) 对2求补器电路,例1： 对1010求补。,例2： 对1011求补。,方法：从数的最右端a0开始,由右向左, 直到找出第一个“1”,例如ai1, 0in。这样, ai以左的每一个输入位都求反, 即1变0, 0变1。,1 0 1 0,0 1 1 0,1,对2求补电路,(2) 带符号的阵列乘法器,包括求补级的乘法器又称为符号求补的阵列乘法器。 在这种逻辑结构中，共使用三个求补器: 两个算前求补器 作用是：将两个操作数A和B在被不带符号的乘法 阵列(核心部件)相乘以前，先变成正整数。 算后求补器 作用则是：当两个输入操作数的符号不一致时， 把运算结果变成带符号的数。,结构:,在必要的求补操作以后，A和B的码值输送给nn位不带符号的阵列乘法器，并由此产生2n位的乘积: ABPp2n1p1p0p2nanbn 其中P2n为符号位。,原码一位除法,补码一位除法,并行除法器,定点除法运算,被除数 x，其原码为x原xf . xn1 x1 x0除数 y，其原码为y原yf . yn1 y1 y0 则有商q/,其原码为q原(xfyf) + (0. xn1x1x0 / 0.yn1 y1y0), 商的符号运算qfxfyf 与原码乘法一样; 商的数值部分的运算,实质上是两个正数求商的运算。,原码一位除法,设有n位定点小数：,1.手算运算步骤,例: 设被除数x=0.1001, 除数y=0.1011, 仿十进制除法运算, 手算求xy的过程。,得的商q0.1101, 余数为r0.00000001。,2.机器运算与手算的不同,(1) 在计算机中,小数点是固定的,不能简单地采用手算的办法。 为便于机器操作, 除数Y固定不变, 被除数和余数进行左移 (相当于乘2),原码一位除法,结果与手算相同，但余数不是真正的余数，多乘了2n，故正确的余数应为2-nrn，即：0.00000001,00.0001 第四次余数r4, 01.0010 被除数左移一位，2xy，商1,+ 11.0101 减y，即+-y补,00.0111 第一次余数r1, 00.1110 r1左移一位 ，2r1y，商1,+ 11.0101 减y,00.0011 第二次余数r2, 00.0110 r2左移一位 ，2r2y，商0, 00.1100 r3左移一位 ，2r3=4r2y，商1,+ 11.0101 减y,00.,1,1,0,1,x=0.1001, y=0.1011，-y补=1.0101,(2) 机器不会心算,必须先作减法,若余数为正, 才知道够减；若 余数为负, 才知道不够减。不够减时必须恢复原来的余数, 以便再继续往下运算。这种方法称为恢复余数法。(3) 要恢复原来的余数, 只要当前的余数加上除数即可。但由于 要恢复余数, 使除法进行过程的步数不固定, 因此控制比较 复杂。 实际中常用不恢复余数法,又称加减交替法。其特点是 运算过程中如出现不够减,则不必恢复余数,根据余数符号, 可以继续往下运算,因此步数固定,控制简单。,机器运算与手算的不同,3.恢复余数法,被除数减除数，够减时，商1；不够减时商0。 由于商时若不够减，即不能作减法，但现在在判断是否商时，已经减了除数，为了下次能正确运算，必须把已减掉的除数加回去恢复余数。这就是“恢复余数法”。,【例1】x=0.1001, y=0.1011, 用恢复余数法求 x/y. 解：x原 =x补= x=.1001, y补=0.1011, -y补=1.0101,0 0.1 0 0 1+-y补 1 1.0 1 0 1 x减y 1 1.1 1 1 0 余数 r00，商“1” 0 0.1 1 1 0 0. 1 商1移入q，r1左移 +-y补 1 1.0 1 0 1 减y 0 0.0 0 1 1 r20，商“1” 0 0.0 1 1 0 0. 1 1 商1移入q，r2左移 +-y补 1 1.0 1 0 1 减y 1 1.1 0 1 1 r30，商“1” 0 0.0 0 0 1 0. 1 1 0 1 商1移入q，r4不左移,被除数x / 余数 r 商q 说明,x原 =.1001y补=0.1011-y补=1.0101,余数每次左移相当于乘以2，在求得n位商后，相当于多乘了2n，所以最后余数应乘以2n才是正确的值。,故：q原=0. 1 1 0 1 余数 r4原=0.00000001,4.加减交替法,上述恢复余数法由于要恢复余数，使得除法的步数不固定，控制比较复杂。实际上常用的是加减交替法。特点：当运算过程中出现不够减的情况，不必恢复余数，而是根据余数的符号，继续往下运算，因此步数固定，控制简单。运算规则： 当余数为正时，商1，余数左移一位，减除数； 当余数为负时，商0，余数左移一位，加除数。【例2】x=0.1001, y=0.1011, 用加减交替法求 x/y. 解：x原=x补= x =.1001, y补=0.1011, - y补=1.0101,0 0.1 0 0 1+-y补 1 1.0 1 0 1 x减y 1 1.1 1 1 0 余数 r00 0 0. 1 1 1 0 0.1 商1，r和q左移一位 +-y补 1 1. 0 1 0 1 减y 0 0. 0 0 1 1 余数r20 0 0. 0 1 1 0 0.11 商1，r和q左移一位 +-y补 1 1. 0 1 0 1 减y 1 1. 1 0 1 1 余数r30 0.1101 商1，仅q左移一位,被除数x / 余数 r 商q 说明,得： q = x/y =0.1101 余数 r = 2-4 r4 = 0.00000001,x原= .1001, y补=0.1011, - y补=1.0101,原码加减交替法原理框图,若被除数与除数同号，被除数减去除数； 若被除数与除数异号，被除数加上除数。(2)余数和除数同号,商1,余数左移一位,下次减除数； 余数和除数异号,商0,余数左移一位,下次加除数。(3) 重复步骤(2)，连同符号位在内，共做n+1步。,1.补码加减交替算法,补码除法的被除数、除数用补码表示，符号位和数位一起参与运算，商的符号位与数位由统一的算法求得。,补码一位除法,为统一并简化硬件电路： 一开始就根据x补和y补的符号位是否相同，上一位商q0， 但q0不是真正的商的符号，称其为假商。 如果x补和y补的符号位相同，假商为1，控制下次做减法； 如果x补和y补的符号位不同，假商为0，控制下次做加法。 按同样的规则，共做n+1步运算后，假商q0移出了存放商的寄存器，剩下q0至qn，即运算结果。,例3：x补=1.0111,y补=0.1101,求x/y补。,1 1.0 1 1 1 0 x补,y补异号，商q0=0+y补 0 0. 1 1 0 1 加除数 0 0.0 1 0 0 余数和除数同号 0 0.1 0 0 0 01 左移一位，商1 +-y补 1 1.0 0 1 1 减除数 1 1.1 0 1 1 余数和除数异号 0 0. 1 1 1 0 010 左移一位， 商0 +y补 1 1. 0 1 0 1 加除数 0 0. 0 0 1 1 余数和除数同号 0 0. 0 1 1 0 0101 左移一位，商1 +-y补 1 1. 0 0 1 1 减除数 1 1. 1 0 0 1 余数和除数异号 1 1. 0 0 1 0 01010 左移一位，商0 +y补 0 0. 1 1 0 1 加除数 1 1. 1 1 1 1 余数和除数异号 1 1. 1 1 1 1 1.0100 仅q左移一位, 商0，余数不左移,被除数x / 余数 r 商q 说明,得：q补= x/y =1.0100+0.0001 (校正量) = 1.0101 r补=1.1111,x补=1.0111y补=0.1101-y补=1.0011,补码一位除法的算法是在商的末位“恒置1”的舍入条件下推导的，故此算法存在误差，这样引起的最大误差是2-n。在对计算精度没有特殊要求的情况下，一般就采用商的末位“恒置1”的办法，这样操作比较简单，而且易于实现。 如果需要进一步提高商的精度，可按上述方法多求一位，再用以下方法进行校正：(1)刚好能除尽时，若除数为正，商不必校正； 若除数为负，则商加2-n。,2.商的校正,(2) 不能除尽时，若商为正，则不必校正； 若商为负，则商加2-n。,阵列式除法器是一种并行运算部件, 采用大规模集成电路制造。与早期的串行除法器相比, 阵列除法器不仅所需的控制线路少, 而且能提供令人满意的高速运算速度。 阵列除法器有多种多样形式： 不恢复余数阵列除法器； 补码阵列除法