计算机组成原理(第3章).ppt

第3章 运算器与运算方法,本章学习导读：（1）运算器由哪几部分组成？（2）如何实现定点/浮点的加、减、乘、除和移位等操作？（3）为了提高运算器速度采取了哪些措施？,运算器部件是计算机中的执行部件，它可以对二进制数据进行各种算术和逻辑运算；运算器也是计算机内部数据信息的重要通路。,本章重点介绍运算器的核心部件算术逻辑运算单元ALU的组成与工作原理，以及数据在运算器的基本运算方法。,3.1 基本组成,1.算术逻辑运算单元ALU,运算器实现了对计算机中数据的加工处理；包括数值数据的算术运算和逻辑数据的逻辑操作。,运算器中完成数据算术与逻辑运算的部件称之为算术与逻辑运算单元（Arithmetic and Logic Unit，简称ALU）。ALU是运算器的核心。,ALU通常表示为两个输入端口，一个输出端口和多个功能控制信号端的这样的一个逻辑符号。,图3.1 ALU的逻辑符号表示与多路开关,2.通用寄存器组,运算器内设有若干通用寄存器，构成通用寄存器组；用于暂时存放参加运算的数据和某些中间结果。,在运算器中用来提供一个操作数并存放运算结果的通用寄存器称作为累加器。,通用寄存器的数量越多，对提高运算器性能和程序执行速度越有利。,通用寄存器组是对用户开放的，用户可以通过指令去使用这些寄存器。,如：ADD A,Rj,3.专用寄存器,运算器需要记录下指令执行过程中的重要状态标记，以及提供运算前后数据的暂存缓冲等，这通过在运算器中设置若干专用寄存器来实现。,循环计数器对程序员是透明的。,程序状态字PSW(Program Status Word)，它存放着指令执行结果的某些状态；如是否溢出、是否为零、是否有进位/借位、是否为负等。它对程序员是开放的。,堆栈指针SP(Stack Pointer)，它指示了堆栈的使用情况。,4.附加的控制线路,在运算器中附加一些控制线路；以达到运算速度快，运算精度高的目的，。,如：运算器中的乘除运算和某些逻辑运算是通过移位操作来实现的。在ALU的输出端设置移位线路来实现左移、右移和直送。,移位线路是一个多路选择器。,图3.2 实现移位功能的多路选择器,3.2 算术与逻辑单元 半加器与全加器,运算器中各种运算都是分解成加法运算进行的，因此加法器是计算机中最基本的运算单元。,1.半加器,两个一位二进制数相加(不考虑低位的进位)，称为半加。实现半加操作的电路，称为半加器。,Xi Yi Hi Ci,0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1,表3.1 半加运算的真值表,HA,Xi Yi Xi Yi,Hi Ci Hi Ci,图 3.3(a)逻辑图(b)符号表示,表3.1 是两个一位二进制数Xi、Yi相加的真值表，Hi和Ci的逻辑表达式如下：,2.全加器,考虑低位进位的加法运算就是全加运算，实现全加运算的电路称为全加器。,根据真值表表3.2可写出Fi和Ci的逻辑表达式：,表 3.2 全加运算的真值表,图 3.4 全加器的逻辑图和符号表示,实现逻辑表达式的全加器逻辑图和全加器的符号表示,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任一个为“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)(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 C2=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位加法器的运算速度。,Cm表示4位加法器的进位输出，Pm表示4位加法器的进位传递输出，Gm表示4位加法器的进位产生输出。,Cm=Gm+PmC0,Pm 和Gm分别为：Pm=P4P3P2P1Gm=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+Pm4Pm3Gm2+Pm4Pm3Pm2 Gm1+Pm4Pm3Pm2P m1C0,图3.8 组间由先行进位链构成的16位加法器,可将并行进位的概念用于更大位数的加法器上，随着加法器位数的增加，加法电路变得越来越复杂。,3.2.3 ALU部件,ALU是一种能进行多种算术运算与逻辑运算的组合逻辑电路，它的基本逻辑结构是先行进位加法器。,74181型4位ALU中规模集成电路工作原理,能对两个4位二进制代码A3A2A1A0和B3B2B1B0进行16种算术运算（当M为低电位时）和16种逻辑运算（当M为高电位时），产生结果F3F2F1F0。,16种运算操作由S3S2S1S0四位控制选择,Cn是ALU的最低位进位输入，低电平有效，即Cn=L表示有进位输入；Cn+4是ALU进位输出信号。,图3.9 是74181型4位ALU的逻辑图及其在正逻辑下的功能表,图3.9(a)正逻辑功能表,图3.9(b)74181型ALU逻辑图,1ALU实现加法操作的原理,当S3S2S1S0=HLLH，M=L时，ALU实现对A3A2A1A0和B3B2B1B0两个4位二进制代码在进位输入Cn参与下的加法运算；即：Fi=AiBiCn+i(i=3,2,1,0)。,设Xi=Ai，Yi=Bi；可推导Xi、Yi 和 Ai、Bi的关系：,Xi+Yi=AiBiXiYi=Ai+BiXiYi=AiBi,ALU就可以改画成以Xi、Yi为输入的结构较简单的单元；可证明GiPi=XiYi。,图3.10 是一个由先行进位加法器组成的单元，电路输出：Fi=XiYi Cn+i=AiBi Cn+I。,由图3.9可知：Pi=AiBiS2+AiBiS3=Xi+Yi Gi=Ai+BiS0+BiS1=XiYi,图3.10 74181作加法运算时的简化逻辑图,2ALU单元实现逻辑运算,当M=H时，由图3.9 可知，进位门1316均被封锁，Fi=PiGi，位间不发生关系，电路执行逻辑运算。,S3S2S1S0=HLLH时，Fi=PiGi=AiBi，对输入数据A3A2A1A0和B3B2B1B0执行逻辑“同或”(异或非)操作。,S3S2S1S0=HHHH时，Fi=PiGi=A i，即F=A，此时，电路执行“传送A”的操作。,按以上方法，可全面分析、理解74181的逻辑图和真值表。,左图是 74181ALU在正逻辑下的图形符号,图3.12 用四片74181构成的16位ALU,下图 是用4片74181组成的16位ALU，芯片内用先行进位方法，但片间为串行进位。,在图3.9的74181的逻辑图中，用先行进位方法产生的进位输出Cn+4和图中P、G的输出信号用表达式：,考虑算术运算，M=LP=P3P2P1P0G=G3+P3G2+P3P2G1+P3P2P1G0 Cn+4=G P3P2P1P0 Cn=G+P Cn=G P+G Cn,P称为片间进位传递函数，G称为片间进位产生函数,根据74181提供的G、P信号，很容易实现芯片之间的先行进位。,在图3.12 中，高三片74181的片间进位输入可以表示为如下表达式：,Cn+4=G(0)+P(0)Cn=G(0)P(0)+G(0)CnCn+8=G(1)+P(1)Cn+4=G(1)+P(1)(G(0)+P(0)Cn)=G(1)P(1)+G(1)G(0)P(0)+G(1)G(0)Cn Cn+12=G(2)+P(2)Cn+8=G(2)+P(2)G(1)P(1)+G(1)G(0)P(0)+G(1)G(0)Cn=G(2)P(2)+G(2)G(1)P(1)+G(2)G(1)G(0)P(0)+G(2)G(1)G(0)Cn,P=P(3)P(2)P(1)P(0),图3.13 片间先行进位产生电路(74182),G=G(3)P(3)+G(3)G(2)P(2)+G(3)G(2)G(1)P(1)+G(3)G(2)G(1)G(0),用四片74181和一片74182芯片组成的16位快速ALU；利用16片74181和5片74182芯片可以很容易组成64位快速ALU。,图3.14 四片74181和一片74182构成的快速16位ALU,33 定点加、减法运算,计算机的一个重要特点是它只能用有限的数码位数来表示操作数和操作结果,制定用来表示正、负数的各种码制；通过数据编码来简化数据的运算，特别是补码，把加法和减法巧妙地结合起来。,定点加、减法运算只有在遵守模运算规则的限制条件下其结果才是正确的，否则就会出现结果“溢出”。,3.3.1 补码定点加、减法,补码制的加、减法运算公式：X+Y补=(X补+Y 补)MOD 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,若结果超过了允许表示的最小负数时，产生的溢出称为下溢。,当算术运算的结果超出了数码位数允许的数据范围时，就产生溢出。,对于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=-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。,两个正数双符号位的运算为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的两个操作数。,在补码加、减法运算中，寄存器X和寄存器Y分别存放补码形式的数据。,设置特征信息的判别线路和保存特征信息的标志寄存器。,进位控制信号1F时，加法器接收进位输入，实现和的末位+1操作。,如果给出1F的同时执行YF，则实现Y取补操作。,加法结果存入寄存器X。,特征信息有加、减运算结果的溢出信号、运算产生的进位/借位信号、结果为负信号、及结果为零信号等。,每个特征信号对应标志寄存器中的一个标志位(Flag)。,用图3.15 来实现加法X+Y补的逻辑操作步骤如下：,X补寄存器X，Y补寄存器Y。,给出控制信号：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补，并置溢出、进位等信号到标志寄存器。,给出控制信号：FX=1，加法器F的输出结果 X-Y补送入寄存器X。减法运算结束。,当寄存器X或寄存器Y的内容送到加法器F时，将符号位等值扩充一位，形成双符号位；双符号位只在加法器中执行加法运算时是必要的。,寄存器X、寄存器Y和加法器F的二进制位数对运算数据和运算结果的大小有限制作用，当超过了这些运算结构所能表示的数据范围时，就产生溢出。,以加法器和通用寄存器的二进制位数定义为计算机的字长。计算机的字长通常是8的整数倍。,3.3.2 原码定点加、减法,原码是用符号位和绝对值来表示的一种数据编码,在原码加、减法运算中，符号位和数值位是分开来计算的；,符号位在运算过程中起判断和控制作用，并且对结果的符号位产生影响。,加、减法运算在数值位上进行。,原码加、减法运算规则：,比较两操作数的符号，对加法实行“同号求和，异号求差”，对减法实行“异号求和，同号求差”。,求和：和的数值位：两操作数的数值位相加。如数值最高位产生进位，则结果溢出。和的符号位：采用被加数（被减数）的符号。,求差：差的数值位：被加数（被减数）的数值位加上加数（减数）的数值位的补码。分二种情况。,2)最高数值位没有产生进位，表明加法结果为负，得到的是数值位的补码形式，因此，对加法结果求补，还原为绝对值形式的数值位。,差的符号位：在上述1)的情况下，符号位采用被加数（被减数）的符号。在上述2)的情况下，符号位采用被加数（被减数）的符号取反。,1)最高数值位产生进位，表明加法结果为正，所得数值位正确。,例1：已知 X原=10011 Y原=11010 计算X+Y原,1)两数同号，所以采用加法求和。,2)和的数值位：0011+1010=1101,和的符号位：采用X原的符号位，为1,所以 X+Y原=11101,例2：已知 X原=10011 Y原=11010 计算X-Y原,1)两数同号，所以采用减法求差。,2)差的数值位：0011+(1010)补=0011+0110=1001，最高数值位没有产生进位，表明加法结果为负，,对1001求补，还原为绝对值形式的数值位，(1001)补=0111,差的符号位：采用X 原的符号位取反，为0 所以 X-Y原=00111,3.4 定点乘法运算,常规的乘法运算方法（定点小数）,笔-纸乘法方法，,原码乘法，,带符号位运算的补码乘法，,用组合逻辑线路构成的阵列乘法器。,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.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。,对中求得的结果求和，这也就是两个正数的乘积。,就笔-纸乘法方法，为提高效率而采取的改进措施,每将乘数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+-+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”，什么也不做。再右移一位，产生本次的迭代部分积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同时右移一位,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 原码二位乘法,为提高乘法的速度，可以对乘数的每两位取值情况进行判断，一步求出对应于该两位的部分积。,在乘法中，乘数的每两位有四种可能的组合，每种组合对应于以下操作：,原码二位乘法的思想,采用原码二位乘法，只需增加少量的逻辑线路，就可以将乘法的速度提高一倍。,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,原码两位乘法运算规则,表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 110010 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,因此X*Y原,3.4.3 补码一位乘法,考查两个补码乘法运算的例子,例1：已知 X=0.1011，Y=0.0001,X补=01011,Y补=00001,X*Y补=000001011,X补*Y补=000001011,显然，X*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=1,i=1,n,n,i=1,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-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，有：,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+1补=2-1Pi 补,一个补码数据的右移是连同符号位右移，且最高位补充符号位的值。,补码乘法运算规则：,乘数最低位增加一辅助位yn+1=0；,判断yn-i yn-i+1的值，决定是“+X”或“-X”，或仅右移一位，得部分积；,重复第步，直到最高位参加操作(y1-y0)*X，但不作移位，结果得X*Y补。,图3.18 是实现布斯乘法的算法流程图,是,是,是,否,否,否,图3.18 布斯乘法运算流程图,开始,yn+1，P0X补码制的被乘数Y补码制的乘数Cnn,yn yn+1,P P+X,Cn=0,P和Y同时右移一位Cn Cn-1,yn yn+1,P P-X,结束,例3：已知 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同时右移一位,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 补,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补,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 110 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,阵列乘法器,实现上述执行过程的阵列结构的乘法器，称为阵列乘法器(Array Multiplier),图3.19中实现了X*Y的乘法运算，其中X=x1x2 x3 x4,Y=y1y2y3y4。X和Y都是无符号的小数部分。,上式中一位乘积xi*yj用一个两输入端的“与”门实现；,每一次加法操作用一个全加器实现；,2-i和2-j 的因子所蕴含的移位是由全加器的空间错位来实现。,图3.19 直接实现定点数绝对值相乘的阵列乘法器,Booth算法的乘法运算也可以用阵列乘法器的方法实现，但要求的单元更复杂。,阵列乘法器的组织结构规则性强，标准化程度高。适合用超大规模集成电路实现，且能获得很高的运算速度。,集成电路的价格不断下降，阵列乘法器在某些数字系统中，例如在信号及数据处理系统中受到重视，它不需要时钟脉冲，而其乘法速度仅决定于门和加法器的传输延迟。,阵列乘法器的特点,3.5 定点除法运算 3.5.1 原码除法运算,笔-纸方法的除法步骤：,被除数与除数比较，决定上商。若被除数小，上商0；否则上商1。得到部分余数。,将除数右移，再与上一步部分余数比较，决定上商，并且求得新的部分余数。,重复执行第步，直到求得的商的位数足够为止。,例1：已知两正数X=0.10011101，Y=0.1011,X/Y的商为0.1110，余数为0.0011*2-4,商的符号为相除两数符号的“异或”值，商的数值为两数的绝对值之商。,原码一位除法规律,原码一位除法运算与原码一位乘法运算一样，要区分符号位和数值位两部分。,计算机中实现二个正数除法时，有几点不同：,比较运算用减法来实现，由减法结果的正负来判断两数的大小。结果为正，上商1；结果为负，上商0。,减法运算时，加法器中两数的对齐是用部分余数左移实现，并与除数比较，以代替除数右移(手算时)与部分余数比较。左移出界的部分余数的高位都是0，对运算不会产生任何影响。,在计算机中，每一次上商过程都是把商写入商值寄存器的最低位，然后部分余数和商一起左移，腾空商寄存器的最低位以备上新的商。,采用部分余数减去除数的方法比较两者的大小，当减法结果为负，即上商0时，破坏了部分余数。可采取两种措施。,1.恢复余数的除法,两个正的定点小数X和Y，X=0.x1x2xn，Y=0.y1y2yn，求解X/Y的商和余数的方法：,第1步：R1=X-Y 若R10，则上商q0=0，同时恢复余数：R1=R1+Y。,若R1=0，则上商q0=1。,q0位不是符号位，而是两定点小数相除时的整数部分；q0=1时，当作溢出处理。,第2步：若已求得第i次的部分余数为Ri，则第i+1次的部分余数为：Ri+1=2Ri-Y 若R i+10，上商qi=0，同时恢复余数：R i+1=R i+1+Y。,若R i+1=0，则上商qi=1。,第3步：不断循环执行第2步，直到求得所需位数的商为止。,例1：已知X原=01011,Y原=11101；求X/Y原。,计算分为符号位和数值位两部分,X/Y原商的符号位：01=1,X/Y原商的数值位计算采用恢复余数法。运算中的减法操作用补码加法实现。,-|Y|补=10011。,分别标识为X和Y运算过程：,部分余数 商 说明 00 1011 0000 开始R0=X,+11 0011 R1=X-Y,11 1110 0000 0 R10，则q0=0,+00 1101 恢复余数：R1=R1+Y,00 1011 得R1,01 0110 000 0 2R1（部分余数和商同时左移）,+11 0011-Y,00 1001 000 01 R20，则q1=1,01 0010 00 01 2R2(左移),+11 0011-Y,00 0101 00 011 R30，则q2=1,00 0101 00 011 R30，则q2=1,00 1010 0 011 2R3(左移),+11 0011-Y,11 1101 0 0110 R40，则q3=0,+00 1101 恢复余数：R4=R4+Y,00 1010 0 0110 得R4,01 0100 0110 2R4(左移),+11 0011-Y,00 0111 01101 R50，则q4=1,可见商的数值位为1101,X/Y原=11101(最高位为符号位)，余数为0.0111*2-4。,加法器,加法和移位控制逻辑,Q qn,Y,计数器Cn,R,加法,移位控制,上商,图3.20 实现两个正数除法的逻辑线路图,开始,R被除数,Q=0Y除数Cnn,R(R)-(Y),(R)0,置溢出标志(或上商“1”),R,Q同时左移一位R(R)-(Y),qn0R(R)+(Y),(R)0,qn0R(R)+(Y),qn1,Cn(Cn)-1,(Cn)=0,结束,是,否,是,是,否,否,图3.21 恢复余数除法的运算流程图,2.不恢复余数的除法(加减交替法),当第i次的部分余数为负时，跳过恢复余数的步骤，直接求第i+1次的部分余数。这种消除前一算法中恢复余数步骤的算法称之为不恢复余数除法。,对两个正的定点小数X和Y采用不恢复余数除法的基本步骤：,第1步：R1=X-Y,若R10，则上商q0=0；,若R1=0，则上商q0=1；,q0代表两定点小数相除时的整数部分，当q0=1时，将当作溢出处理。,第2步：若已求得部分余数Ri，则第i+1次的部分余数为：,若R i 0，上商q i-1=0，Ri+1=2Ri+Y，上一步中多减去的Y在这一步中弥补回来；,若R i=0，上商q i-1=1，Ri+1=2Ri-Y，保持原有的除法过程；,第3步：不断循环执行第2步，直到求得所需位数的商为止。,结束时，若余数为负值，要执行恢复余数的操作 Rn=Rn+Y。,图3.22 实现两正定点数相除的不恢复余数除法运算流程,X/Y原商的数值位的计算采用不恢复余数的除法,参加运算的数据是|X|补和|Y|补两数，分别标识为X和Y；-|Y|补=10011。,例1：已知 X原=01011,Y原=11101；计算X/Y原。,计算分为符号位和数值位两部分,X/Y原商的符号位：01=1,运算过程如下：,部分余数 商 说明 00 1011 0000 开始R0=X,+11 0011 R1=X-Y,11 1110 0000 0 R10，则q0=0,11 1100 000 0 2R1（部分余数和商同时左移）,+00 1101+Y,00 1001 000 01 R20，则q1=1,01 0010 00 01 2R2（左移）,+11 0011-Y,00 0101 00 0