计算机组成原理（第3章）

第3章运算器与运算方法本章学习导读：（1）运算器由哪几部分组成？（2）如何实现定点/浮点的加、减、乘、除和移位等操作？（3）为了提高运算器速度采取了哪些措施？●运算器部件是计算机中的执行部件，它可以对二进制数据进行各种算术和逻辑运算；运算器也是计算机内部数据信息的重要通路。●本章重点介绍运算器的核心部件——算术逻辑运算单元ALU的组成与工作原理，以及数据在运算器的基本运算方法。3.1基本组成1.算术逻辑运算单元ALU▲运算器实现了对计算机中数据的加工处理；包括数值数据的算术运算和逻辑数据的逻辑操作。▲运算器中完成数据算术与逻辑运算的部件称之为算术与逻辑运算单元（ArithmeticandLogicUnit，简称ALU）。ALU是运算器的核心。▲

ALU通常表示为两个输入端口，一个输出端口和多个功能控制信号端的这样的一个逻辑符号。图3.1ALU的逻辑符号表示与多路开关2.通用寄存器组▲运算器内设有若干通用寄存器，构成通用寄存器组；用于暂时存放参加运算的数据和某些中间结果。▲在运算器中用来提供一个操作数并存放运算结果的通用寄存器称作为累加器。通用寄存器的数量越多，对提高运算器性能和程序执行速度越有利。通用寄存器组是对用户开放的，用户可以通过指令去使用这些寄存器。如：ADDA,Rj3.专用寄存器▲运算器需要记录下指令执行过程中的重要状态标记，以及提供运算前后数据的暂存缓冲等，这通过在运算器中设置若干专用寄存器来实现。循环计数器对程序员是透明的。程序状态字PSW(ProgramStatusWord)，它存放着指令执行结果的某些状态；如是否溢出、是否为零、是否有进位/借位、是否为负等。它对程序员是开放的。堆栈指针SP(StackPointer)，它指示了堆栈的使用情况。4.附加的控制线路▲在运算器中附加一些控制线路；以达到运算速度快，运算精度高的目的，。如：运算器中的乘除运算和某些逻辑运算是通过移位操作来实现的。在ALU的输出端设置移位线路来实现左移、右移和直送。移位线路是一个多路选择器。图3.2实现移位功能的多路选择器

3.2算术与逻辑单元

3.2.1

半加器与全加器◆运算器中各种运算都是分解成加法运算进行的，因此加法器是计算机中最基本的运算单元。1.半加器▲两个一位二进制数相加(不考虑低位的进位)，称为半加。实现半加操作的电路，称为半加器。

XiYiHiCi

0

00 0 011 0 1010 110 1表3.1半加运算的真值表HAXiYi

XiYi

HiCiHi

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.5n位加法器◆先行进位或并行进位加法器预先形成各位进位，将进位信号同时送到各位全加器的进位输入端。▲就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代入前面的C1~C4式，可得：

C1=G1+P1C0C2=G2+P2G1+P2P1C0C3=G3+P3G2+P3P2G1+P3P2P1C0C4=G4+P4G3+P4P3G2+P4P3P2G1+P4P3P2P1C0▲“先行进位产生电路”（图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+P4G3+P4P3G2+P4P3P2G1应用于四个4位先行进位加法器，则有：

Cm1=Gm1+Pm1C0Cm2=Gm2+Pm2Cm1

=Gm2+Pm2Gm1+Pm2Pm1C0Cm3=Gm3+Pm3Cm2=Gm3+Pm3Gm2+Pm3Pm2Gm1+Pm3Pm2Pm1C0Cm4=Gm4+Pm4Cm3=Gm4+Pm4Gm3+Pm4Pm3Gm2+Pm4Pm3Pm2Gm1+Pm4Pm3Pm2Pm1C0图3.8组间由先行进位链构成的16位加法器▲可将并行进位的概念用于更大位数的加法器上，随着加法器位数的增加，加法电路变得越来越复杂。3.2.3ALU部件◆

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逻辑图1．ALU实现加法操作的原理▲当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=AiBiCn+I。由图3.9可知：

Pi=AiBiS2+AiBiS3=Xi+Yi

Gi=Ai+BiS0+BiS1=XiYi图3.1074181作加法运算时的简化逻辑图2．ALU单元实现逻辑运算▲当M=H时，由图3.9可知，进位门13~16均被封锁，Fi=PiGi，位间不发生关系，电路执行逻辑运算。

S3S2S1S0=HLLH时，Fi=PiGi=AiBi，对输入数据A3A2A1A0和B3B2B1B0执行逻辑“同或”(异或非)操作。

S3S2S1S0=HHHH时，Fi=PiGi=Ai，即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+P3P2P1G0Cn+4=GP3P2P1P0Cn

=G+PCn=GP+GCn

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)CnP=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位ALU3．3定点加、减法运算■计算机的一个重要特点是它只能用有限的数码位数来表示操作数和操作结果制定用来表示正、负数的各种码制；通过数据编码来简化数据的运算，特别是补码，把加法和减法巧妙地结合起来。定点加、减法运算只有在遵守模运算规则的限制条件下其结果才是正确的，否则就会出现结果“溢出”。3.3.1补码定点加、减法◆补码制的加、减法运算公式：[X+Y]补=([X]补+[Y]

补)MOD2n[X-Y]补=([X]补+[-Y]

补)MOD2n在补码制方法下，无论X、Y是正数还是负数，加、减法运算统一采用加法来处理；[X]补和[Y]补的符号位和数值位一起参与求和运算，加、减运算结果的符号位也在求和运算中直接得出。◆例1：已知[X]补=01001，[Y]补=11100；求[X+Y]补，

[X-Y]补。则[-Y]补=00100[X+Y]补=([X]补+[Y]补)MOD25=(01001+11100)MOD25=00101[X-Y]补=([X]补+[-Y]补)MOD25=(01001+00100)MOD25

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

[20]10>15产生上溢[-14]10-[4]10=

[-18]10<-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）MOD4=11时，结果不溢出；两个负数的双符号位的运算为（11+11）MOD4=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。②给出控制信号：XF=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]原=001113.4定点乘法运算◆常规的乘法运算方法（定点小数）笔---纸乘法方法，原码乘法，带符号位运算的补码乘法，◆用组合逻辑线路构成的阵列乘法器。3.4.1原码一位乘法◆用原码实现乘法运算时，符号位与数值位是分开计算的；◆原码乘法运算分为二步；第二步是计算乘积的数值位；乘积的数值部分为两数的绝对值之积。第一步是计算乘积的符号位；乘积的符号为相乘二数符号的异或值。◆用数学表达式描述原码乘法运算设：[X]原=x0x1xn，[Y]原=y0y1yn(其中x0、y0分别为它们的符号位)若[X*Y]原=z0z1z2n(其中z0

为结果之符号位)则z0=x0y0

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

1011X*y4*2–4 0000X*y3*2–3 1011X*y2*2–2 1011

X*y1*2–10.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=0P1=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=00=0

C

P

Y

说明000001011开始，设P0=0+1101

y4=1，+X01101

C,P和Y同时右移一位001101101得P1+1101

y3=1，+X1

0011

C,P和Y同时右移一位010011110得P2

y2=0，不作加法

C,P和Y同时右移一位001001111得P3+1101

y1=1，+X10001C,P和Y同时右移一位010001111得P4z1z8=10001111[X*Y]原=z0z1z8=010001111001101101得P13.4.2原码二位乘法为提高乘法的速度，可以对乘数的每两位取值情况进行判断，一步求出对应于该两位的部分积。◆在乘法中，乘数的每两位有四种可能的组合，每种组合对应于以下操作：◆原码二位乘法的思想采用原码二位乘法，只需增加少量的逻辑线路，就可以将乘法的速度提高一倍。00———Pi+1=2-2Pi01———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=00=0

z1z12=111001*100111

具体过程：

PY

T说明0000000001001110开始，P0=0，T=0+111000111

y5y6T=110，-X,T=1111000111P和Y同时右移2位111000111P和Y同时右移2位1111100011110011

得P1+001110010y3y4T=011，+2X,T=0001100011P和Y同时右移2位0000110001111100得P2+001110010y1y2T=100，+2X,T=0010001010P和Y同时右移2位

0001000101011110得P3z1z12=100010101111因此[X*Y]原=01000101011113.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]补=x0x1

……

xn,[Y]补=y0y1……

yn

。◆考查两个补码乘法运算的一般情况根据补码定义，可得出其真值:

Y=-y0+yi2-ii=1n

[X*Y]补=[X*(-y0+yi2-i)]

补=[X*yi2-i-X*y0]补=[X*yi2-i]

补+[-X*y0]补ni=1i=1nni=1◆

Booth（布斯）乘法相乘二数用补码表示，它们的符号位与数值位一起参与乘法运算过程，直接得出用补码表示的乘法结果，且正数和负数同等对待。▲

A.D.Booth算法思想：▲

Booth算法推导：已知[X]补=x0x1

……

xn,[Y]补=y0y1……

yn

；根据补码定义，可得出:根据补码定义，可得出其真值:

Y=-y0+yi2-ii=1n=-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-ini=1设yn+1=0（称为辅助位）；有：[X*Y]补=[X*(yi+1-yi)2-i]补

ni=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为上次部分积，Pi＋1为本次部分积。令[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-iyn-i+1=01，

则[Pi+1]补=[2-1(Pi+X)]补若yn-iyn-i+1=10，

则[Pi+1]补=[2-1(Pi-X)]补若yn-iyn-i+1=00或11，则[Pi+1]补=[2-1Pi]补一个补码数据的右移是连同符号位右移，且最高位补充符号位的值。▲补码乘法运算规则：①乘数最低位增加一辅助位yn+1=0；②判断yn-iyn-i+1的值，决定是“+X”或“-X”，或仅右移一位，得部分积；③重复第②步，直到最高位参加操作(y1-y0)*X，但不作移位，结果得[X*Y]补。图3.18是实现布斯乘法的算法流程图是是是否否否图3.18布斯乘法运算流程图开始yn+1，P0X补码制的被乘数Y补码制的乘数Cnnynyn+1PP+XCn=0P和Y同时右移一位CnCn-1yn

yn+1PP-X结束▲例3：已知[X]补=01101,[Y]补=10110，[-X]补=10011。用布斯乘法计算[X*Y]补的过程如下

PYyn+1

说明000000101100开始，设y5=0，[P0]补=0

y4y5=00，P、Y同时右移一位000000010110得[P1]补+110011y3y4=10，+[-X]补110011P、Y同时右移一位111001101011得[P2]补

y2y3=11，P、Y同时右移一位111100110101得[P3]补111100110101得[P3]补+001101y1y2=01，+[X]补001001P、Y同时右移一位000100111010得[P4]补+110011y0y1=10，+[-X]补11011111101最后一次不右移因此，[X*Y]补=101111110▲布斯乘法的算法过程为n+1次的“判断—加减—右移”的循环，判断的次数为n+1次，右移的次数为n次。▲在布斯乘法中，遇到连续的“1”或连续的“0”时，是跳过加法运算，直接实现右移操作的，运算效率高。3.4.4补码二位乘法◆补码二位一乘的方法可以用布斯乘法过程来推导[Pi+1]补=2-1{[Pi]补+(yn-i+1-yn-i)*[X]

补

[Pi+2]补=2-1{[Pi+1]补+(yn-i-yn-i-1)*[X]

补[Pi+2]补=2-2{[Pi]

补+(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-iyn-i+1

表3.4乘数3位代码组合构成的判断规则

00

002-2[Pi]补

001+[X]补2-2{[Pi]补+[X]补}

010+[X]补2-2{[Pi]补+[X]补}

011+2[X]补2-2{[Pi]补+2[X]补}

100+2[-X]补2-2{[Pi]补+2[-X]补}

101+[-X]补2-2{[Pi]补+[-X]补}

110+[-X]补2-2{[Pi]补+[-X]补}

11102-2[Pi]补◆设乘数[Y]补=y0y1……

yn，导出补码二位乘法中的计算量。(1)当n为偶数时，乘法运算过程中的总循环次数为n/2+1。(2)当n为奇数时，乘法运算过程中的总循环次数为（n+1）/2。◆例4：已知[X]补=00011,[Y]补=11010；[-X]补=11101。用补码二位乘法计算[X*Y]补的过程。

P

Yyn+1

说明0000000110100开始，设y5=0，[P0]补=0+1111010y3y4y5=100，+2[-X]补1111010P和Y同时右移二位1111110101101得[P1]补+1111101y1y2y3=101，+[-X]补1111011P和Y同时右移二位1111110111011得[P2]补

y0y0y1=111，不做加法最后一次不右移

[X*Y]补=1111011103.4.5阵列乘法器◆实现上述执行过程的阵列结构的乘法器，称为阵列乘法器(ArrayMultiplier)◆图3.19中实现了X*Y的乘法运算，其中X=x1x2x3x4,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若R1<0，则上商q0=0，同时恢复余数：R1=R1+Y。若R1>=0，则上商q0=1。

q0位不是符号位，而是两定点小数相除时的整数部分；q0=1时，当作溢出处理。第2步：若已求得第i次的部分余数为Ri，则第i+1次的部分余数为：Ri+1=2Ri-Y若Ri+1<0，上商qi=0，同时恢复余数：Ri+1=Ri+1+Y。若Ri+1>=0，则上商qi=1。第3步：不断循环执行第2步，直到求得所需位数的商为止。例1：已知[X]原=01011,[Y]原=11101；求[X/Y]原。计算分为符号位和数值位两部分[X/Y]原商的符号位：01=1[X/Y]原商的数值位计算采用恢复余数法。运算中的减法操作用补码加法实现。[-|Y|]补=10011。▲分别标识为X和Y运算过程：部分余数商说明0010110000

开始R0=X+110011R1=X-Y11111000000R1<0，则q0=0+001101恢复余数：R1=R1+Y001011

得R101011000002R1（部分余数和商同时左移）+110011-Y00100100001R2>0，则q1=101001000012R2(左移)+110011-Y00010100011R3>0，则q2=100010100011R3>0，则q2=100101000112R3(左移)+110011-Y11110100110R4<0，则q3=0+001101恢复余数：R4=R4+Y00101000110得R401010001102R4(左移)+110011

-Y00011101101R5>0，则q4=1可见商的数值位为1101[X/Y]原=11101(最高位为符号位)，余数为0.0111*2-4。加法器加法和移位控制逻辑QqnY计数器CnR加法移位控制上商图3.20实现两个正数除法的逻辑线路图

开始R被除数,Q=0Y除数CnnR(R)-(Y)(R)<0置溢出标志(或上商“1”)R,Q同时左移一位R(R)-(Y)qn0R(R)+(Y)(R)<0qn0R(R)+(Y)

qn1Cn(Cn)-1(Cn)=0结束是否是是否否图3.21恢复余数除法的运算流程图2.不恢复余数的除法(加减交替法)▲当第i次的部分余数为负时，跳过恢复余数的步骤，直接求第i+1次的部分余数。这种消除前一算法中恢复余数步骤的算法称之为不恢复余数除法。▲对两个正的定点小数X和Y采用不恢复余数除法的基本步骤：第1步：R1=X-Y

若R1<0，则上商q0=0；

若R1>=0，则上商q0=1；

q0代表两定点小数相除时的整数部分，当q0=1时，将当作溢出处理。第2步：若已求得部分余数Ri，

则第i+1次的部分余数为：若Ri<0，上商qi-1=0，Ri+1=2Ri+Y，

上一步中多减去的Y在这一步中弥补回来；若Ri>=0，上商qi-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运算过程如下：部分余数商说明0010110000开始R0=X+110011R1=X-Y11111000000R1<0，则q0=011110000002R1（部分余数和商同时左移）+001101+Y00100100001R2>0，则q1=101001000012R2（左移）+110011-Y00010100011R3>0，则q2=100010100011R3>0，则q2=100101000112R3（左移）+110011-Y11110100110R4<0，则q3=011101001102R4（左移）+001101+Y00011101101R5>0，则q4=1商的数值位为1101[X/Y]原=11101。因为R5>0，所以，余数为0.0111*2-4。

n位数的不恢复余数除法需要n次加法运算。对恢复余数除法来说，平均需要3n/2次加法运算。▲在不恢复余数除法运算中，每一位商的计算或是加法，或是减法，而不是两者都要。3.5.2补码除法运算◆补码除法与原码除法比较(1)在原码除法中，符号位与数值位区分开来运算，除法运算是在两数的绝对值上进行的。在补码除法中，符号位与数值位同等参与整个除法运算过程，商的符号位在除法运算中产生。(2)部分余数和除数都用带符号位的补码表示时，部分余数与除数是否够除，就不再能用两数直接相减的方法来判断。两数同号时，用减法判断，差的符号与除数符号一致表示够除，否则为不够除。两数异号时，用加法判断，和的符号与除数符号一致表示不够除，否则为够除。部分余数[R]补除数[Y]补[R]补-[Y]补[R]补+[Y]补010100011011够减(商1)不够减(商0)够减(商1)够减(商1)不够减(商0)不够减(商0)不够减(商0)够减(商1)表3.5两补码数是否够减的判别方法表中的0或1表示相应数的符号值(3)补码除法的结果是连同符号位在内的补码形式的商。两数同号，商为正数，够减上商“1”，不够减上商“0”；两数异号，商为负数，够减上商“0”，不够减上商“1”；除法结束后，可在最低位加1的办法求出补码值的商。◆被除数为[X]补，除数为[Y]补，则[X/Y]

补的补码除法运算规则：在这里需做除法溢出判断：若[X]

补与[Y]补同号且上商q0=1，则溢出。第1步：若[X]补与[Y]补同号：

R1=[X]

补-[Y]补若[X]补与[Y]补异号：R1=[X]

补+[Y]补若R1与[Y]补同号：上商q0=1若R1与[Y]补异号：上商q0=0若[X]

补与[Y]补异号且上