数值的机器运算乘法

1、1,4.4 定点乘法运算,运算器概念模型： N位加法器： 寄存器： A寄存器：部分积与最后乘积的高位部分，初值为0。 B寄存器：被乘数X。 C寄存器：乘数Y，运算后C寄存器中不再需要保留乘数，改为存放乘积的低位部分。 移位电路：,2,设n位被乘数和乘数用定点小数表示 被乘数 x原xf . xn1 x1x0 乘数 y原yf . yn1 y1y0 则乘积 z原(xfyf)(0. xn1 x1x0)(0. yn1 y1y0) 式中，xf为被乘数符号，yf为乘数符号。,1. 乘法的手工算法,4.4.1原码一位乘法,3,(2) 手工运算过程：,设0.1101,0.10110,0. 1 1 0 1 (x)

2、 0. 1 0 1 1 0 (y) 0 0 0 0 1 1 0 1 1 1 0 1 0 0 0 0 + 1 1 0 1 0. 1 0 0 0 1 1 1 1 (z),(1)乘积符号的运算规则：同号相乘为正，异号相乘为负。,4.4.1原码一位乘法,0. 1 1 0 1 (x) 0. 1 0 1 1 0 (y) 0. 0 0 0 0 0 0 0 0 0. 0 0 0 0 1 1 0 1 0. 0 0 0 1 1 0 1 0. 0 0 0 0 0 0 + 0. 0 1 1 0 1 0. 1 0 0 0 1 1 1 1 (z),4,一般而言，设被乘数x,乘数y都是小于1的n位定点正数： x=0.x1x

3、2.xn 1 y=0.y1y2.yn 1,其乘积为： xy=x(0.y1y2.yn ) =x(y12-1 +y22-2 + yn2-n ) = xy12-1+xy22-2 +xyn2-n = 2-1(y1x+2-1(y2x+2-1(+2-1(yn-1x+2-1(ynx+0),4.4.1原码一位乘法,5,形成递推公式,令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),4.4.1原码一位乘法,2-1(y1x+2-1(

4、y2x+2-1(+2-1(yn-1x+2-1(ynx+0),优点： 1、每次只有两个数相加。 2、相加的的位数为n。 3、容易确定加数。,6,4.4.1 原码一位乘,原码一位乘法的规则为： 参加运算的操作数取其绝对值,且用两位符号； 令乘数的最低位为判断位，若为“1”，加被乘数，若为“0”，不加被乘数（加0）； 累加后的部分积右移一位； 重复n次和； 符号位单独处理，同号为正，异号为负。,7,4.4.1原码一位乘法,8,部分积,乘数,说明,最后结果 ： 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

5、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.4.1原码一位乘法,尾数,9,设x补 = x0.x1x2xn 当x

6、0时, x0=0，,x补=0.x1x2xn = = x,= -1+ 0.x1x2xn= -1+,x = -x0 +,真值与补码的关系：,当x0时, x0=1， x补=1.x1x2xn = 2 + x x=1.x1x2xn-2,(1)真值和补码之间的关系,4.4.2 补码一位乘法,10,设被乘数 x补 = x0.x1x2xn 乘数 y补 = y0.y1y2yn 均为任意符号，则有补码乘法算式：, xy 补 = x补 y,或：, xy 补 = x补,(2) 补码乘法规则(校正法),原码乘法： xy=x(y12-1 +y22-2 + yn2-n ) = xy12-1+xy22-2 +xyn2-n =

7、 2-1(y1x+2-1(y2x+2-1(+2-1(yn-1x+2-1(ynx+0),与原码乘法运算规则的区别： 1、操作数用补码表示。 2、被乘数的符号位参与运算。 3、乘数的符号位决定最后是否修正，修正不移位。,11,部分积,乘数,说明,最后结果 ： xy补=1.01110001,0 0.0 0 0 0 yf 0 1 0 1 1 z0=0 + 1 1.0 0 1 1 y4=1, +x 1 1.0 0 1 1 1 1.1 0 0 1 1 yf 01 0 1 右移，得z1 + 1 1.0 0 1 1 y3=1, +x 1 0.1 1 0 0 1 1.0 1 1 0 0 1 yf 0 1 0 右

8、移，得z2 + 0 0.0 0 0 0 y2=0, +0 1 1.0 1 1 0 1 1.1 0 1 1 0 0 1 yf 0 1 右移，得z3 + 1 1.0 0 1 1 y1=1, +x 1 0.1 1 1 0 1 1.0 1 1 1 0 0 0 1 yf 右移，得z4=xy,例：x=-0.1101 , y=0.1011 , 求 xy 。,X补=11.0011，Y补=Y=0.1011,12,部分积,乘数,说明,0 0.0 0 0 0 yf 1 0 1 0 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 0 右

9、移，得z1 + 0 0.0 0 0 0 y3=1, +x 0 0.0 1 1 0 0 0.0 0 1 1 0 1 yf 1 0 1 右移，得z2 + 0 0.1 1 0 1 y2=0, +0 0 1.0 0 0 0 0 0.1 0 0 0 0 0 1 yf 1 0 右移，得z3 + 0 0.0 0 0 0 y1=1, +x 0 0.1 0 0 0 0 0.0 1 0 0 0 0 0 1 yf 右移，得z4=xy 1 1.0 0 1 1 y0 1，-x 1 1.0 1 1 1 0 0 0 1 不移位,例：x=0.1101 , y=0.1011 , 求 xy 。,X补=00.1101 Y补=11.

10、0101 -X补=11.0011,最后结果 ： xy补=1.01110001,13,( yn+1是增加的附加位，初值为0 ),Booth算法,14,将上式改为接近于分步运算逻辑实现的递推关系。,递推公式,最后一步不移位,15,由此可见： 每次都是在前次部分积的基础上，由（yi+1-yi ) 决定对x补的操作，然后再右移一位，得到新的部分积；重复进行。,yn+1，yn的作用： 开始操作时，补充一位yn+1 , 使其初始为0。由yn+1 yn 判断进行什么操作；然后再由ynyn-1 判断第二步进行什么操作 。,若 yn yn1 =1 则 yi1-yi =1 做加x补运算；,ynyn1 = 则 yi

11、1-yi= - 做加-x补运算；,则 yi1-yi= 0 zi加0，即保持不变,16,补码BOOTH一位乘的运算规则,(1) 如果 yn=yn+1 ，则部分积 zi 加0，再右移一位；,(2) 如果 yn yn+1=01 ，则部分积 zi 加x补，再右移一位；,(3) 如果 yn yn+1=10 ，则部分积 zi 加-x补, 再右移一位；,如此重复n + 1步，但最后一步不移位。 包括一位符号位，所得乘积为2n+1位，其中n为尾数位数。,(4) 数值用补码表示，被乘数和部分积取两位符号位，乘数取一位符号，符号也参加运算。,17,BOOTH法流程图,18,0 0.0 0 0 0 1. 0 0 1

12、 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

13、 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,说明,19,0 0 0 0 0 0 1 0 1 1 1 0 yn+1=0 + 1 1 0 0 1 1 ynyn+1=10, 1 1 0 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 右移一位 + 0 0 0 0 0 0 ynyn+1=11 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 0 1 1 右移一位 + 0 0 0

14、0 0 0 ynyn+1=11, 加0 1 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 0 1 右移一位 + 0 0 1 1 0 1 ynyn+1=01, 加x补 0 0 1 0 1 1 0 0 0 1 0 1 1 0 1 1 1 0 右移一位 + 1 1 0 0 1 1 ynyn+1=10, 加-x补 1 1 1 0 0 0 1 0 1 1 1 0 最后一位不移位,x补=001101，y补=10111, -x补=110011,xy补=110001011,部分积,乘数 yn yn+1,说明,例：x=13, y=-9 求xy=？,xy = -0111 0101=-117,20,y

15、i或yi与yi+1组合控制变量，决定每次加法的加数！,Z1,Z2,Z3,Z4,21,补码一位乘法比较, xy 补 = x补,22,4.4 定点乘法运算,4.4.3 补码两位乘法 为了提高乘法的执行速度，可以选用两位乘法的方案。所谓两位乘法，就是每次处理乘数中的两位，从而使乘法的速度提高了一倍。 根据前面介绍的Booth乘法方便地推导出补码两位乘法，即把补码两位乘理解为将Booth乘法的两次合并为一次来做。 补码两位乘法可以通过Yi-1YiYi+1三位的不同组合来判断原部分积与X补的运算情况，然后右移两位得到新的部分积。,23,4.4 定点乘法运算,24,4.4 定点乘法运算,补码两位乘法规则如

16、下： 参加运算的数用补码表示； 符号位参加运算； 乘数最低位后增加一位附加位Yn+1，初值为0； 根据乘数的最低三位Yn-1YnYn+1的值决定每次应执行的操作； 移位按补码右移规则进行。 比较结果（Yi+1+Yi-2Yi-1）,25,4.4 定点乘法运算,Yn-1YnYn+1 0 0 0 +0，右移2位 0 0 1 +X补，右移2位 0 1 0 +X补，右移2位 0 1 1 +2X补，右移2位 1 0 0 +2-X补，右移2位 1 0 1 +-X补，右移2位 1 1 0 +-X补，右移2位 1 1 1 +0，右移2位,26,4.4 定点乘法运算,被乘数和部分积取三符号位，当乘数的数值位n 为

17、偶数时，乘数取两符号位，共需作(n/2)+1次累加，n/2次移位（最后一次不移位）；当n为奇数时，乘数只需一个符号位，共需(n1)/2次累加和移位，但最后一次仅移一位。,27,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