1、第三章 运算方法和运算器3.1快速加法器设计快速加法器设计一、全加器 全加器有三个输入量：第 i 位的两个操作数 Ai、Bi 和低位送来的进位 Ci；两个输出量：全加和 i 及向高位的进位Ci+1。全加和 i 及进位 Ci+1 的逻辑表达式：_ _ _ _ _ _ i=AiBiCi+AiBiCi+AiBiCi+AiBiCi =Ai Bi Ci _ _ _ Ci+1=AiBiCi+AiBiCi+AiBiCi+AiBiCi =AiBi+(Ai Bi)Ci二、串行加法器和并行加法器 加法器有两种形式：串行加法器和并行加法器。（一）串行加法器 n 位字长的加法器仅有一位全加器，使用移位寄存器从低位到高
2、位串行地提供操作数，分n步进行相加。（二）并行加法器 全加器位数和操作数位数相同，同时对所有位进行求和。三、并行加法器的进位结构 进位线路结构分为：串行进位、并行进位，将整个加法器分组（分级），对组内、组间（级间）分别采用串行或并行进位。（一）对进位公式的分析Ci+1=AiBi+(Ai Bi)Ci 进位逻辑表达式 设：Gi=AiBi 进位产生函数(Carry Generate Function)Pi=Ai Bi 进位传递函数(Carry Propagate Function)当Pi=1时，如果低位有进位，本位将产生进位。则：Ci+1=Gi+PiCi（二）串行进位（行波进位）串行进位的逻辑表达式
3、：最长进位延迟时间为 4+2.5(n-1)ty，与 n 成正比。C1=G0+P0C0C2=G1+P1C1C3=G2+P2C2 Cn=Gn-1+Pn-1Cn-1（三）并行进位（同时进位、先行进位）C1=G0+P0C0C2=G1+P1C1=G1+P1(G0+P0C0)C3=G2+P2C2=G2+P2(G1+P1(G0+P0C0)C4=G3+P3C3=G3+P3(G2+P2(G1+P1(G0+P0C0)展开整理：C1=G0+P0C0C2=G1+P1G0+P1P0C0C3=G2+P2G1+P2P1G0+P2P1P0C0C4=G3+P3G2+P3P2G1+P3P2P1G0+P3P2P1P0C0 全部进位
4、输出信号仅由进位产生函数 Gi，进位传递函数 Pi 以及最低位进位 C0 决定，与低位进位无关。因为进位信号同时产生，所以称为并行进位。又称为同时进位或先行进位。（四）组内并行、组间串行的进位结构 将n位加法器分成若干个小组，小组采用并行、组间采用串行的进位结构。例：将16位加法器分成4组，每组4位，组内采用并行进位结构，组间采用串行进位结构。最高进位的形成时间为(4+32)ty=10 ty 如果采用串行进位，最高进位的形成时间为(4+152.5)ty=41.5 ty（五）组内并行、组间并行的进位结构 将加法器分成几个小组，每一小组包括几位，采用并行进位结构，小组间也采用并行进位。再引入两个辅
5、助函数 Gi*和Pi*；分别称为组进位产生函数和传递函数。Gi*为本小组产生的进位（与低位小组来的进位无关）。Pi*为小组进位的传递条件（决定于低位小组进位能否传送至高位小组）。Gi*和Pi*的逻辑表达式：设：G0*=G3+P3G2+P3P2G1+P3P2P1G0G1*=G7+P7G6+P7P6G5+P7P6P5G4G2*=G11+P11G10+P11P10G9+P11P10P9G8G3*=G15+P15G14+P15P14G13+P15P14P13G12P0*=P3P2P1P0 P1*=P7P6P5P4P2*=P11P10P9P8 P3*=P15P14P13P12 小组间产生四个进位，C4、
6、C8、C12和C16。C4=G0*+P0*C0C8=G1*+P1*G0*+P1*P0*C0C12=G2*+P2*G1*+P2*P1*G0*+P2*P1*P0*C0C16=G3*+P3*G2*+P3*P2*G1*+P3*P2*P1*G0*+P3*P2*P1*P0*C0 组间并行进位线路如图7-11(b)所示。当Gi*、Pi*及C0形成后，C4、C8、C12和C16便可同时产生。C4、C8、C12和C16已由组间进位线路产生，组内并行进位线路不需要再产生这些进位，将其作适当修改，便可产生小组的本地进位Gi*和小组的传送条件Pi*以及小组内的低3位进位（见图3-11(a)）。例：16位加法器采用组内
7、并行、组间并行进位结构的框图，如图7-10所示。进位形成过程如下：从Ai、Bi、C0输入开始：经过4ty形成C1、C2、C3及全部Gi*、Pi*；又经过2.5ty形成C4、C8、C12、和C16；最后再经 2.5ty 形成二、三、四、小组内的其余进位 C75、C119、C1513。最长进位形成时间：(4+2.5+2.5)ty=9ty 组间串行：(4+32)ty=10ty 完全串行：(4+152.5)ty=41.5ty四、组内并行、组间并行进位加法器实例1、SN74181 算术逻辑单元，简称ALU，具有组内并行进位链，提供了辅助函数G，P供组间进位链使用。一位ALU单元：两个半加器构成全加器。A
8、i,Bi输入由选择控制S0S1S2S3进行控制。第二级半加器的输入由（电位）M控制，选择算术运算所需的低位进位或作逻辑运算。Xi，Yi的设计：Xi、Yi与输入信号Ai、Bi的关系：_ _ _ _Xi=S3AiBi+S2AiBi _ _ _Yi=S1Bi+S0Bi+Ai(当S3S2S1S0取不同值时)_ Xi选择可以为：1，Ai+Bi，Ai+Bi，Ai可以提供进位传递条件:Pi=Ai+Bi _ Yi选择可以为：0，Ai，AiBi，AiBi可以提供进位产生函数:Gi=AiBi2、SN74182（先行进位发生器）提供：组间并行进位信号Cn+x，Cn+y，Cn+z_ _大组辅助函数：P，G例：用SN7
9、4181和SN74182组成16位分二级同时进位的加法器。利用并行进位链74182可产生向高一级进位链提供 _ _辅助函数G*、P*，用于位数更长时，组成第三级并行进位链。3.2定点加减运算定点加减运算一、原码加减运算二、补码加减运算（一）两个基本关系式：x+y补=x补+y补(mod M)x-y补=x补+-y补(mod M)由y补求-y补的方法：将y补连同符号位一起求反加1。注意：求一个数的补码：正数时，补码和原码相同；负数时,对原码除符号位外求反加1。求-y补是对y补包括符号位求反加1。例1 y=-0.0110y补=1.1010-y补=0.0110例2y=0.0111y补=0.0111-y补
10、=1.1001（二）补码加、减运算规则参加运算的操作数用补码表示。符号位参加运算。操作码为加运算时，两数直接相加；当操作码为减运算时，将减数连同符号位一起求反加1与被减数相加。运算结果以补码表示。例1:已知:x=0.1001,y=-0.0110,求 x+y=?解:x补=0.1001 y补=1.1010 x补 0.1001+y补 1.1010 x+y补 1 0.0011x+y=0.0011例2:已知:x=-0.1001,y=-0.0101,求 x+y=?解:x补=1.0111 y补=1.1011 x补 1.0111+y补 1.1011x+y补 1 1.0010 x+y=-0.1110例3:已知:
11、x=0.1001,y=0.0110,求 x-y=?解:x补=0.1001 y补=0.0110-y补=1.1010 x补 0.1001+-y补 1.1010 x-y补 1 0.0011x-y=0.0011例4:已知:x=-0.1001,y=-0.0110,求 x-y=?解:x补=1.0111 y补=1.1010-y补=0.0110 x补 1.0111+-y补 0.0110 x-y补 1.1101x-y=-0.0011（三）溢出检测采用双符号位(变形补码)判溢出。正数：两个符号位均为0；00.x1x2xn 负数：两个符号位均为1；11.x1x2xn 溢出判断：两数相加，结果符号位为00、11，表示
12、没溢出；结果符号位为01表示正溢出，为10表示负溢出。如果用 Sn+1、Sn 分别表示最高符号位和第二符号位，则采用变形补码溢出检测电路：OVR=Sn+1 Sn OVRSn+1Sn三、反码加减运算 反码加减运算的规则：参加运算的操作数用反码表示。符号位参加运算。当操作码为加运算时，两数直接相加；当操作码为减运算时，将减数连同符号位一起求反与被减数相加。如果符号位产生进位，则在末位加1。运算结果用反码表示。3.3定点乘法运算定点乘法运算一、移位操作1.逻辑移位：只有数码位置的变化，而无数量的变化。左移：低位补0，右移：高位补0。例：A寄存器的初值为 10110101 逻辑右移一位后为 01011
13、010 逻辑左移一位后为 011010102.循环移位：寄存器两端触发器有移位通路，形成闭合的移位环路。例：A寄存器的初值为 10011001 循环右移一位后为 11001100 循环左移一位后为 001100113.算术移位：数的符号不变而数量发生变化。左移一位将使数值扩大一倍（乘以2）右移一位则使数值缩小一倍（乘以1/2）.算术移位规则：（1）正数：原码、补码、反码左右移位时，空位均补入0（符号不变）。左移一位：0.1100右移一位：0.0011（2）负数：原码：符号位不变（为1），空位补0。例：A寄存器的初值为 1.0110 算术左移一位后为 1.1100 算术右移一位后为 1.0011
14、 补码：左移后的空位补0，右移后的空位补1。左移：|1|1|0 右移：|1|例：A寄存器初值：0.0110 例：初值：1.1011左移一位：1.0110右移一位：1.1101 反码：移位后的空位补1 例：初值：1.1011左移一位：1.0111右移一位：1.1101二、原码一位乘法 乘积的符号：为相乘两数符号的异或值 数值部分：为两数绝对值之积。0.1101)0.1011 1101 1101 0000 1101 0.10001111例：x=0.1101 y=0.1011 计算机计算：将n位乘转化为n次“累加与移位”。每一步只求一位乘数所对应的新部分积，并与原部分积作一次累加，然后移位一次。乘法
15、步骤：（1）初始化：|被乘数|B，|乘数|C，0A，nCTR。（2）C0=1 时，A+BA。C0=0 时，A+0A。（3）A、C联合右移一位。（4）CTR-1CTR，若CTR0按（2）、（3）、（4）步骤循环至CTR=0为止。（5）乘积为2n位，高位在A，低位在C。符号由异或门决定并放在乘积最高位之前。三、补码一位乘法1.补码乘法算法的推导（1）被乘数x符号任意，乘数y符号为正设：x补=xn.xn-1x1.x0 y补=0.yn-1yn-2y1 y0 根据补码定义：x补=2+x=2n+1+x (mod 2)y补=yx补y补=2n+1y+xy=2(yn-1y1 y0)+xy (mod 2)2(yn
16、-1y1 y0)=2(mod 2)x补y补=2+xy=xy补(mod 2)即：xy补=x补y补=x补 y=x补(0.yn-1y1 y0)（2）被乘数x符号任意，乘数y符号为负x补=xn.xn-1xn-2x0y补=1.yn-1y1 y0=2+y(mod 2)y=y补-2=1.yn-1y1 y0-2=0.yn-1y1 y0-1x y=x(0.yn-1y1 y0)-xxy补=x(0.yn-1y1 y0)-x补 =x(0.yn-1y1 y0)补+-x补 =x(0.yn-1y1 y0)补-x补 =x补(0.yn-1y1 y0)-x补（3）当被乘数x和乘数y符号任意，以补码表示：xy补=x补(0.yn-1
17、y1 y0)-x补yn y0：yn=0 不需校正 y0：yn=1 需要校正（-x补）2.补码乘法比较法布斯（Booth）乘法 运算法则xy补=x补-yn+yn-12-1+yn-22-2+y02-n=x补-yn+(yn-1-yn-12-1)+(yn-22-1-yn-22-2)+(y02-(n-1)-y02-n)=x补(yn-1-yn)+(yn-2-yn-1)2-1+(y0-y1)2-(n-1)+(0-y0)2-n=x补(yn-1-yn)+2-1(x补(yn-2-yn-1)+2-1(x补(yn-3-yn-2)+2-1(x补(y0-y1)+2-1(x补(y-1-y0)设：(y-1=0)递推公式：p0
18、补=0p1补=2-1(p0补+(y-1-y0)x补)p2补=2-1(p1补+(y0-y1)x补)pi补=2-1(pi-1补+(yi-2-yi-1)x补)pn补=2-1(pn-1补+(yn-2-yn-1)x补)pn+1补=pn补+(yn-1-yn)x补=xy补 每一步乘法在前次部分积的基础上，根据 yi-2-yi-1(i=1,2n)的值决定对 x补 进行什么操作，然后右移一位，得到新的部分积。重复n步。第n+1步由(yn-1-yn)的值决定对x补的操作但不移位。Booth算法：参加运算的数用补码表示 符号位参加运算 乘数最低位后面增加一位附加位y-1（初值为0），逐次比较相邻两位并按下列规则运算
19、：yi yi-1 yi-1-yi 操 作 000 部分积加 0，右移一位 011 部分积加 x补，右移一位 10-1 部分积加-x补，右移一位 110 部分积加 0，右移一位 按上述算法进行n+1步（n是不包括符号位在内的字长），第n+1步不移位 移位要按补码的移位规则进行四、原码两位乘法 两位乘数有四种组合：yiyi-1=00 相当于0 x 部分积加 0，右移两位；yiyi-1=01 相当于1 x 部分积加|x|，右移两位；yiyi-1=10 相当于2 x 部分积加 2|x|，右移两位；yiyi-1=11 相当于3 x 部分积加 3|x|，右移两位。原码两位乘的算法：（1）同原码一位乘法一样
20、，数值部分和符号位分别处理。（2）部分积和被乘数采用三个符号位（3）减|x|的操作是通过加-|x|补来实现的。右移按补码右移规则（4）当乘数为偶数位n时，乘数的符号位设置两位“00”，做 n/2 次移位，做 n/2+1次加法。当乘数为奇数位n时，乘数符号位设置一位“0”，做n/2+1次加法，n/2+1次移位（最后一次移一位）。五、补码两位乘法 补码两位乘法的算法，运算规则如下：yi+1 yiyi-1 操作0 0 0部分积+0，右移两位0 0 1部分积+x补，右移两位0 1 0 部分积+x补，右移两位0 1 1 部分积+2x补，右移两位1 0 0部分积+2-x补，右移两位1 0 1 部分积+-x
21、补，右移两位1 1 0 部分积+-x补，右移两位1 1 1 部分积+0，右移两位 乘数数值位数为偶数n，采用双符号位，做n/2+1 步加法，n/2步移位，最后一步不移位。乘数数值位数为奇数n，采用一个符号位，做 n/2+1 步加法及移位，最后一步移一位。部分积和被乘数采用三个符号位。3.4定点除法运算定点除法运算一、原码除法 商的符号为相除两数符号的异或值，数值用两数的绝对值相除。设x原=xs.x1x2xn，y原=ys.y1y2yn 则商q原=(xs ys).(x1x2xn/y1y2yn)小数除法，要求：0|被除数|除数|，调整比例因子。若：余数符号为1（差为负数），|被除数|除数，（够减）,
22、商“1”，余数为负，上一次余数除数，（不够减），商“0”。恢复原来的余数。重复步骤，直到商的位数=操作数位数。余数的符号与权的处理余数的符号与权的处理:(小数除法小数除法)(1).让加符号前的商和余数都保持正值让加符号前的商和余数都保持正值,当最当最后一步不够减时后一步不够减时,应恢复余数应恢复余数(即即:当余数为当余数为负数时负数时,要加上除数要加上除数,得到真正的余数得到真正的余数)(2).进行了进行了n步除之后步除之后,形式上的余数形式上的余数,应应乘以乘以2-n才为真正的余数的值才为真正的余数的值被除数被除数(余数余数)采用采用2位符号位位符号位.(变形补变形补)原码除法恢复余数法原码
23、除法恢复余数法:例例:x=0.1011,y=-0.1101,求求x/y原原 及及 x/y解解:x =0.1011,y =0.1101,-y 补补=1.0011被除数被除数(余数余数):A 商商(C)00.1011 0.0000|初态(0)作减法+)11.0011|x|+-|y|补余数 11.1110 为负商0恢复余 +)00.1101 0.000|0 数+|y|00.1011 (1)余数与商左 01.0110 0.00|0 移一位减除数+)11.0011 +-|y|补 余数为 00.1001 0.00|01 正,商“1”01.0010 0.0|01 (2)余数与商左+)11.0011 移一位减
24、除数 00.0101 0.0|011 +-|y|补余数为 00.1010 0.|011 正,商“1”(转下页)00.1010 0.|011 (3)余数与商左 +)11.0011 移一位减除数 +-|y|补余数 11.1101 0.|0110 为负,商“0”+)00.1101 恢复余数+|y|00.1010 (4)余数与商左 01.0100|0.110 移一位减除 +)11.0011 数+-|y|补余数 00.0111 0.1101 为正,商“1”商值为商值为:0.1101,商的符号为商的符号为xs ys=0 1=1x/y原原=1.1101 余数为余数为:0.0111*2-4x/y=-0.110
25、1-0.0111/0.1101*2-4(二）不恢复余数法（加减交替法）对恢复余数法进行修正 第 i 步：ri=2ri-1-|y|。若ri0,商“1”，下一步：ri+1=2ri-|y|。若ri0,商“0”，恢复余数ri+|y|，下一步ri+1=2(ri+|y|)-|y|=2ri+2|y|-|y|=2ri+|y|不恢复余数除法规则：当余数为正，商上“1”，做2ri-|y|的运算。当余数为负，商上“0”，做2ri+|y|的运算。重复、，上商n+1次，左移n次按被除数与除数符号的异或值，决定商的符号。二、补码不恢复余数法（加减交替法）（一）两数符号任意时，比较它们大小的方法 比较算法表 比较x补与 求
26、余数ri补 比较ri补与 y补的符号 y补的符号 同号 x补-y补 同号表示够减 异号 x补+y补 异号表示够减（二）上商原则商值及新余数的确定：ri补与y补 商 新余数 同 号 1 ri+1补=2ri补-y补 异 号 0 ri+1补=2ri补+y补（三）商符的确定统一求商符、商值法：（1）第一步运算：当被除数和除数同号时，作x补-y补=r0补；当被除数和除数异号时，作x补+y补=r0补；（2）第二步：当被除数和除数同号时，r0补必与y补异号，按上商规则，商应上“0”，（恰好是正商的符号）；当被除数和除数异号时，r0补必与y补同号，按上商规则，商应上“1”，（恰好是负商的符号）。求商值、商符的
27、规则统一（第一步运算要做x补y补，第二步做2ri补y补），但运算操作不统一。(末位恒置“1”）统一运算操作过程方法：一开始将被除数 x补 当做初始余数 r0补，如果 r0补 与除数 y补 同号，按上商规则商应上“1”，如果 r0补 与除数 y补 异号，商应上“0”。与实际商符矛盾，必须将商符取反以进行校正。(四)补码加减交替法的运算规则。(a)为统一求商符、商值法，(b)为统一运算操作过程法 参加运算的数用补码表示。符号位参加运算。(a)被除数与除数同号，做被除数减除数的运算；被除数与除数异号，做被除数加除数的运算。(b)将被除数作为第一次余数。如果余数与除数同号，商“1”，ri+1补=2ri
28、补-y补；如果余数与除数异号，商“0”，ri+1补=2ri补+y补。重复步骤 n次（n是不包括符号位在内的字长）。(a)末位恒置1。(b)假商加(1+2-n)得到真商。若对商的精度要求较高时，第5步改为：对n位数求商n+1次，求n+1次商时，(ri与y)同号，商“1”，+-y补，异号，商“0”，不操作，得正确余数 r。再采用下面的校正规则对商进行处理。若能除尽，除数为正，商不必校正；除数为负，则(a)商加2-n，(b)假商加(1+2-n)。若不能除尽，商为正，则不必校正；商为负，则(a)商加2-n，(b)假商加(1+2-n)。双倍被除数的除法双倍被除数的除法.P314(补码不恢复余补码不恢复余
29、 数法运算规则数法运算规则)(1)参加运算的数用补码表示，符号参加运算的数用补码表示，符号位参加运算位参加运算.A,C 存放被除数存放被除数(2n位位长长),B存放除数存放除数(n位位)(2)将被除数左移一位(A,C联合左移),若被除数与除数同号,则:A-B;若异号则:A+B;若余数(A)与除数(B)同号，上商1,A,C1,A-B若余数(A)与除数(B)异号，上商0,A,C1,A+B商的修正.将商的最末位恒置“1”3.5浮点四则运算及浮点运算器浮点四则运算及浮点运算器一、浮点加减运算及实现 设有两个浮点数x和yx=2ExMxy=2EyMyMx和My分别为x和y的尾数，Ex和Ey分别为x和y的阶
30、码。运算步骤1.对阶 阶码：反映了数的小数点位置。浮点数相加减要求阶码相等，小数点的位置对齐，这个过程称为对阶。求阶差E=Ex-Ey 若E=0，不需对阶。若E0，需对阶，按|E|调整阶码。保留大阶 对阶的规则：小阶向大阶看齐。阶码小的尾数向右移位，每右移一位阶码加1，直至阶差为0。例：两浮点数为x=0.1101201y=-(0.1010)211求x+y=?解：x、y以补码表示：x补=00，01；00.1101 Ex Mxy补=00，11；11.0110 Ey My(1.对阶)E补=Ex补-Ey补=00,01+11,01=11,10即 E=-2，x阶码 2m-1-1时，称为阶码上溢 当 阶码-2
31、m-1时，称为阶码下溢二、浮点乘除运算及实现 设两个浮点数分别为 x=2ExMx，y=2EyMy1、乘法运算：xy=2(Ex+Ey)(MxMy)乘积的阶码为：两数的阶码之和。乘积的尾数为：两数的尾数之积。2、除法运算：x/y=2(Ex-Ey)(Mx/My)商的阶码为：被除数的阶码减去除数的阶码之差。商的尾数为：被除数的尾数除以除数的尾数所得的商。讨论阶码运算（讨论对移码的运算规则和判定溢出的方法）。（一）阶码加减运算（移码表示的阶码）x移与x补：符号位相反，其数值位相同。x移=2n+x -2nx2nx移+y移=2n+x+2n+y =2n+(2n+x+y)=2n+x+y移x移+y移+2n=x+y
32、移 (mod2n+1)y补=2n+1+y (整数补码)又y移=2n+y y补=2n+2n+y=2n+y移x移+y补=x+y移 (mod2n+1)同理x移+-y补=x-y移 执行阶码加减运算，对加数或减数的移码符号位求反再运算，结果就是正确的移码值。（二）溢出判断 阶码采用双符号位，（最高符号位）恒为0。运算结果符号：01结果为正无溢出00结果为负10上溢11下溢例：阶码用四位表示（包括一位符号位）Ex=+110Ey=+011Ex移=01,110 Ey补=00,011 -Ey补=11,101Ex+Ey移=Ex移+Ey补=10,001 上溢Ex-Ey移=Ex移+-Ey补=01,011 正确(+3)
33、当Ex=-110 Ey=-011时Ex移=00,010 Ey补=11,101 -Ey补=00,011Ex+Ey移=Ex移+Ey补=11,111 结果下溢Ex-Ey移=Ex移+-Ey补=00,101 结果正确(-3)例：浮点数相乘，4位阶码（移码表示），8位尾数（包括符号位，用补码表示）。已知 x=23(0.1001101)，y=2-5(-0.1110010)，求 xy=?解：x的浮点表示形式 1,011；0.1001101 y的浮点表示形式 0,011；1.0001110 移码采用双符号位 Ex移=01,011 Ey补=11,011 -Mx补=1.0110011 乘法步骤：阶码相加，Ex+Ey
34、移=Ex移+Ey补Ex移01,011Ey补 +)11,011Ex+Ey移 00,110尾数相乘，采用补码两位乘方案。规格化处理：MxMy补=1.01110110110110舍入 设尾数保留8位(包括符号位)，采用0舍1入法，尾数为 MxMy补=1.0111011。xy的浮点表示为：0,110；1.0111011，xy=2-2(-0.1000101)。3.6十进制运算十进制运算.十进制数的8421码加法运算规则(1)两数相加,当所得的和1001时，不必修正。例：3 +4 78421码运算：0011+)0100 0111 (+7)正确结果(2)两个数相加，当所得的和1010时，和数需+6修正。例：8 +5 138421码运算：1000+)0101 1101 结果错误，+6修正。+)0110 1,0011 (13)10 结果正确。两个一位十进制数相加，其和18，加上低位进位，其和最大值是19。
