第3章 (3.3 二进制乘法运算)

1/23,1,一、定点数一位乘法,两个原码数相乘，其乘积的符号为相乘两数的异或值，数值则为两数绝对值之积。,(1)原码一位乘,3.3二进制乘法运算,2/23,2,解：0.11100.110111100000111011100.10110110,例：X0.1110，Y0.1101，计算XY(人工算法)。,机器内多个数据一般不能同时相加，一次加法操作只能求出两数之和。,问题：,需用n个寄存器存放n个部分积。,最后结果是2n位的数，需用2n位的加法器。,结论：,不经济，上述算法需要改进。,部分积,3/23,3,把每次运算得到的部分积逐次累加。每次仅有2个部分积相加，所需的寄存器数减少。,改进：,部分积右移时，乘数寄存器同时右移一位，则始终用乘数寄存器的最低位来控制相加数(取被乘数或零)，同时乘数寄存器的最高位可以接收部分积右移出来的一位。因此，完成乘法运算后，A寄存器保存乘积的高位部分，乘数寄存器保存乘积的低位部分。,在求本次部分积时，前一部分积的最低位不再参与运算，因此可将其右移一位，相加数可直送而不必偏移，则用n位加法器就可实现两个n位数相乘。,4/23,4,例：X0.1110，Y0.1101，计算XY。,解：B|X|原0.1110，|Y|原0.1101部分积A乘数C00.0000.1101B00.111000.1110右移1位00.01110.110右移1位00.001110.11B00.111001.0001右移1位00.1000110.1B00.111001.0110右移1位00.10110110.,积的符号位011,XY0.10110110,A采用双符号位，累加时可能产生的进位暂存于第二符号位，第一符号位始终指示部分积累加和的正负。,注意：,最后一步要移位，共移位n次（乘数的尾数为n位）。,移位时连同符号位一起右移，空位补第一符号位。,5/23,5,练习：X0.1101，Y0.1011，计算XY。,解：B|X|原0.1101，|Y|原0.1011部分积A乘数C00.0000.1011B00.110100.1101右移1位00.01101.101B00.110101.0011右移1位00.100111.10右移1位00.0100111.1B00.110101.0001右移1位00.10001111.,积的符号位011,XY0.10001111,6/23,6,有的机器为方便加减法运算，数据以补码形式存放。如采用原码乘法，则在相乘之前，要将负数还原成原码形式，相乘之后，如乘积为负数，又要将其转换成补码形式，这增加了操作步骤。为此，有不少计算机直接采用补码相乘。,(2)补码一位乘,7/23,7,校正法设：被乘数X补=X0.X1X2Xn，乘数Y补=Y0.Y1Y2Yn，则：XY补=X补(-Y0+Yi2-i),若先按原码那样直接乘；,若乘数Y为正，则结果不需校正；,若乘数Y为负，则结果加一个校正量（X补）。,8/23,8,比较法XY补=X补(-Y0+Yi2-i)=X补(Yi+1-Yi)2-i（布斯公式）,操作数与结果均以补码表示，连同符号位一起运算；,乘数的最低1位为Yn，在其后再添加1位Yn+1，值为0。,9/23,9,变换布斯公式：按机器执行顺序求出每一步的部分积。P0补=0P1补=P0补+(Yn+1-Yn)X补2-1(Yn+1=0)P2补=P1补+(Yn-Yn-1)X补2-1Pi补=Pi-1补+(Yn-i+2-Yn-i+1)X补2-1Pn补=Pn-1补+(Y2-Y1)X补2-1Pn+1补=Pn补+(Y1-Y0)X补=XY补,总结：在上一步的部分积上，加(Yi+1-Yi)X补(i=n,1,0)，再右移1位，得到新部分积。,10/23,10,Yi+1与Yi为相邻两位，(Yi+1-Yi)有三种取值，其运算规则如下：,Yi+1-Yi=0(Yi+1Yi=00或11)，部分积加0，右移1位；,Yi+1-Yi=1(Yi+1Yi=10)，部分积X补，右移1位；,Yi+1-Yi=-1(Yi+1Yi=01)，部分积-X补，右移1位；,最后一步(i=n+1)不移位。,11/23,11,例：X0.1101，Y0.1011，计算XY补。,解：B=X补=11.0011，B=00.1101，C=Y补=1.0101步数条件操作部分积A乘数C00.00001.0101010B00.110100.1101右移1位00.011011.010101B11.001111.1001右移1位11.1100111.01010B00.1101100.1001右移1位00.01001111.0101B11.001111.0111右移1位11.101111111.010B00.1101100.1000,XY补0.10001111,移位时空位补第一符号位。,注意：,最后一步不移位，共做n1步，共移位n次。,12/23,12,练习：X0.1010，Y0.0110，计算XY。,解：B=X补=00.1010，B=11.0110，C=Y补=1.1010步数条件操作部分积A乘数C00.00001.1010000右移1位00.000001.101010B11.011011.0110右移1位11.1011001.10101B00.1010100.0101右移1位00.00101001.1010B11.011011.1000右移1位11.110001001.1,XY补11.11000100,11右移1位11.1110001001.,XY0.00111100,13/23,13,两位乘根据乘数每两位的取值情况，决定做什么操作，从而一次求出对应于该两位的部分积。此时，只要增加少量逻辑电路，就可使乘法速度提高一倍。,二、定点数两位乘法,14/23,14,乘数和被乘数都用原码表示，符号位单独处理。,(1)原码两位乘,两位乘数有四种可能组合，对应以下操作：,YiYi1=00相当于0X。部分积Pi右移2位；,YiYi1=01相当于1X。部分积PiX，右移2位；,YiYi1=10相当于2X。部分积Pi2X，右移2位；,YiYi1=11相当于3X。部分积Pi3X，右移2位。,15/23,15,2X把X左移1位即得2X，在机器内通常采用向左斜送1位来实现。,实现：,3X不能一次完成，分两次又会降低计算速度。,3X用(4X-X)来运算，在本次运算中只执行-X，用一个欠账触发器CJ记下欠账，下一步再补+4X。,每一步累加后部分积要右移两位，移位前欠下的+4X已变成+X，下一步只需+X即可还账。,16/23,16,例：X0.111111，Y0.111001，计算XY原。,解：B=|X|=000.111111，B=111.000001，2B=001.111110C=|Y|=00.111001步数Cn-1CnCJ操作部分积A乘数CCJ欠账触发器000.00000000.1110010010B000.111111000.111111右移2位000.0011111100.111001002B001.111110010.001101右移2位000.100011011100.110110B111.000001111.100100右移2位111.11100100011100.1001B000.1111111000.111000,XY原1.111000000111,积的符号位101,17/23,17,A、B采用三符号位。2B本身可能进位到第三符号位，部分积2B操作后可能进位到第二符号位，而第一符号位始终指示部分积的正负。,注意：,共移位n/2次（乘数的尾数为n位）。,应使乘数的尾数为偶数位，若不是，在末尾补0凑足。,CJ不是由移位得到。,乘数C用双符号位，在最后一步还清欠账时充当判断位中的乘数。,18/23,18,练习：X0.1011，Y0.1101，用原码两位乘计算XY。,解：B=|X|=000.1011，B=111.0101，2B=001.0110C=|Y|=00.1101步数Cn-1CnCJ操作部分积A乘数CCJ000.000000.11010010B000.1011000.1011右移2位000.00101100.110110B111.0101111.0111右移2位111.1101111100.1001B000.10111000.1000,XY0.10001111,积的符号位000,19/23,19,乘数和被乘数都用补码表示，积的符号在运算时产生。,(2)补码两位乘,设上一步的部分积为Pi补，则本步的部分积应为：Pi+1补=Pi补(Yn-i+1Yn-i)X补2-1,下一步的部分积应为：Pi+2补=Pi+1补(Yn-iYn-i-1)X补2-1,综合上述两步可得：Pi+2补=Pi补(Yn-i+1Yn-i2Yn-i-1)X补2-2,根据前述的布斯算法，将两步合并成一步，即可推导出补码两位乘的公式。,20/23,20,三位乘数有8种可能组合，对应以下操作：,21/23,21,在进行第一步操作时，Yn+1为附加位。,当乘数尾数的位数为奇数时，乘数用1位符号位，最后一步只移1位。,乘数用1位符号位，在尾数末尾、附加位之前再加一个0，最后一步只移1位。共移位(n+1)/2次。,当乘数尾数的位数为偶数时，有两种处理方法：,乘数用2位符号位，最后一步不移位。共移位n/2次。,22/23,22,例：X0.1110，Y0.1101，用补码两位乘计算XY。,解：X补=000.1110，-X补=111.0010，2X补=001.1100，2-X补=110.0100，Y补=11.0011步数Yn-1YnYn+1操作部分积A乘数Y附加位Yn1000.000011.00110110-X补111.0010111.0010右移2位111.11001011.001001X补000.11101000.1010右移2位000.0010101011.0110-X补111.0010111.0100,XY0.10110110,XY补1.01001010,注意：区分附加位和欠账触发器。,23/23,23,练习：X补0.10011，Y补1.01101，补码两位乘计算XY补。,解：