组成原理第4章-2.ppt

第四章 运算方法和运算器,4.2 定点数的乘法运算及实现,实现乘除法运算，可以有三种方式： 用软件实现通过编制一段子程序来实现乘除运算这种方式运算速度较慢，但硬件设计简单 用硬件乘法器和除法器实现这种方式相对软件实现方法，运算速度提高，但硬件设计也相对复杂 用高速的阵列乘法器和阵列除法器来实现乘除法指令实现的硬件基础是专用的、并行运算的阵列乘法器和阵列除法器这种方式，硬件相当复杂，但牺牲硬件代价，赢得了速度一、原码乘法算法及实现 1、手工乘法算法 手工计算1011×1101，步骤： 手工算法是：对应每一位乘数求得一项位积，并将位积逐位左移，然后将所有的位积一次相加，得到最后的乘积 乘法的机器算法：从乘数的最低位开始，每次根据乘数位得到其位积，乘数位为0，位积为0，乘数位为1，则位积为被乘数；用本次位积左移一位加上原部分积，得新部分积；初始部分积为02、原码一位乘法 假设[X]原=XS X1 X2 ……Xn ， [Y]原=YS Y1 Y2 ……Yn ， P=X·Y，PS是积的符号： 符号位单独处理 Ps=Xs ⊕ Ys 绝对值进行数值运算 |P|=|X|*|Y|,例如：X=+1011，Y=-1101，用原码一位乘法计算P=X·Y。

解：[X]原=0，1011 [Y]原=1，1101 Ps=Xs ⊕ Ys =0⊕1=1，|P| = |X|·|Y| [P]原=1，10001111,,3、原码乘法的硬件实现 原码一位乘法硬件实现,原码一位乘法,0 0 0 0 0 0,1 0 1 1,0 0 0 0 0 0,0 0 1 1 0 1,1 0 1 1,,,,为各寄存器给初值,原码一位乘法,0 0 0 0 0 0,1 0 1 1,0 0 0 0 0 0,0 0 1 1 0 1,1 0 1 1,0 0 1 1 0 1,0 0 0 1 1 0,1 0 1 1,0 0 0 1 1 0,1,1 0 1,,,,0 0 1 1 0 1,第一次求部分积,,原码一位乘法,0 0 0 0 0 0,1 0 1 1,0 0 0 0 0 0,0 0 1 1 0 1,1 0 1 1,0 0 0 1 1 0,0 1 0 0 1 1,0 1 0 0 1 1,1 1 0 1,0 0 1 0 0 1,0 0 0 1 1 0,0 0 1 0 0 1,1 0,1 1,1,1 0 1,,,,第二次求部分积,,原码一位乘法,0 0 0 0 0 0,1 0 1 1,0 0 0 0 0 0,0 0 1 1 0 1,1 0 1 1,0 0 0 1 1 0,0 0 1 0 0 1,0 0 0 1 1 0,0 0 1 0 0 1,1 0,1 1,0 0 0 1 0 0,0 0 0 1 0 0,1,1 0 1,1 1 1,1,0 0 0 1 0 0,,,,0 0 1 0 0 1,0 0 1 0 0 1,第三次求部分积,原码一位乘法,0 0 0 0 0 0,1 0 1 1,0 0 0 0 0 0,0 0 1 1 0 1,1 0 1 1,0 0 0 1 1 0,0 0 1 0 0 0,0 0 1 0 0 1,0 0 0 1 1 0,0 0 1 0 0 1,1 0,1 1,0 0 0 1 0 0,0 0 0 1 0 0,1,1 0 1,1 1 1,1,0 0 1 0 0 0,低位积,,,,0 1 0 0 0 1,0 1 0 0 0 1,第四次求部分积,高位积,原码一位乘法,0 0 0 0 0 0,1 0 1 1,0 0 0 0 0 0,0 0 1 1 0 1,1 0 1 1,0 0 0 1 1 0,0 0 1 0 0 0,0 0 1 0 0 1,0 0 0 1 1 0,0 0 1 0 0 1,1 0,1 1,0 0 0 1 0 0,0 0 0 1 0 0,1,1 0 1,1 1 1,1,0 0 1 0 0 0,低位积,,,,高位积,符号位异或， 积符号得负， 结果为： 1 10001111,,,控制逻辑电路,原码一位乘法,,原码一位乘法流程 ：,原码的两位乘法及其实现,二、补码乘法及实现 1、补码一位乘法——校正法 假设[X]补 = X0 .X1……Xn ，[Y]补 = Y0 .Y1……Yn ，则有： [X·Y]补 = [X]补·（0.Y1……Yn）+ Y0·[-X]补 证明如下： 当被乘数X的符号任意，Y为正数时： 根据补码定义有： [X]补 =2 + X = 2n+1+ X （mod 2） [Y]补 =Y 则：[X]补·[Y]补 =（2n+1+ X）·Y = 2n+1·Y + X·Y = 2 n+1·（0 .Y1……Yn）+ X·Y = 2·（Y1……Yn）+ X·Y = 2 + X·Y （mod 2）= [X·Y]补 即：Y 0 时，[X·Y]补 = [X]补·[Y]补 =[X]补·（0.Y1……Yn） 当被乘数X的符号任意，Y为负数时： [Y]补 = 2 + Y = 1 .Y1……Yn则：Y = [Y]补 – 2 = 0.Y1……Yn -1 [X·Y]补 = [ X·0.Y1……Yn –X] 补 = [ X·0.Y1……Yn ] 补 +[–X] 补 因为0.Y1……Yn 0，所以：[ X·0.Y1……Yn ] 补 =[X]补·（0.Y1……Yn） 所以：Y0时，[X·Y]补 =[X]补·（0.Y1……Yn）+ [-X]补,例如：X=+0.1011，Y=-0.1101，用补码一位乘法的校正法计算P=X·Y。

[X]补=00.1011 [Y]补=11.0011 [-X]补=11.0101,,[X·Y]补 = 1.0111 0001 X·Y = -0.1000 1111,例：设X=-0.1101,Y=-0.1011,即：[X]补=11.0011,[Y]补=11.0101,求[X*Y]补 解：计算过程如下：,计算结果： [X*Y]补=0.10001111,2、补码一位乘法——Booth算法 做出如下推导 ： [X·Y]补 = [X]补·（0.Y1……Yn）+ Y0·[-X]补 = [X]补·（Y1·2-1 + Y2·2-2 + ……+ Yn·2-n -Y0） = [X]补·[Y1·（20 - 2-1）+ Y2·（2-1 - 2-2）+ ……+ Yn·（2-n+1 - 2-n）-Y0·20] = [X]补·[Y1·20 - Y1·2-1 + Y2·2-1 - Y2·2-2 + ……+ Yn·2-n+1 - Yn·2-n -Y0·20] = [X]补·[（Y1-Y0）·20 +（Y2- Y1）·2-1 +（Y3- Y2）·2-2 + ……+ （Yn- Yn-1）·2-n+1 - Yn·2-n] = [X]补·[（Y1-Y0）·20 +（Y2- Y1）·2-1 +（Y3- Y2）·2-2 + ……+ （Yn- Yn-1）·2-n+1 +（Yn+1 - Yn）·2-n] = [X]补·（a0·20 + a1·2-1 + a2·2-2 + ……+ an-1·2-n+1 + an·2-n） 其中，将乘数Y的补码在最末位添加一位附加位Yn+1（初始为0），ai= Yi+1- Yi ，i=0，1，……，n-1，n。

0,,被乘数X和乘数Y均以补码的形式参加乘法运算，运算的结果是积的补码 部分积和被乘数X采用双符号位，乘数Y采用单符号位 [Y]补后添加附加位Yn+1初值为0（Yn Yn+1判断操作） 右移时遵循补码的移位规则 累加右移n次，最后累加不右移,例如：X=+0.1011，Y=-0.1101，用补码一位乘法的Booth算法计算P=X·Y 解：[X]补=00.1011 [Y]补=11.0011 [-X]补=11.0101,,[X·Y]补 = 1.0111 0001 X·Y = -0.1000 1111,3、Booth乘法的硬件实现,,,控制逻辑电路,,补码乘法的Booth算法流程,补码的两位乘法,三、阵列乘法器 1、绝对值阵列乘法器,,位积的每一位XiYj都可以用一个与门实现，而每一位的相加均可以使用一个全加器来实现4位×4位绝对值阵列乘法器,2、补码阵列乘法器 原码的阵列乘法器 在绝对值阵列乘法器的基础上，添加一个异或门，以产生积的原码的符号位 补码的阵列乘法器， 先通过一个补码求绝对值的逻辑电路变为绝对值后，送入绝对值阵列乘法器，运算得到积的绝对值，然后再通过一个绝对值求补码的逻辑电路，根据积的符号求出积的补码形式。

例10001),,补码求绝对值电路,,（n+1）位×（n+1）位补码阵列乘法器框图,4.3 定点数除法运算及实现,一、原码除法及实现 1、原码除法算法 手工除法算法,,改进手工算法即可适合机器运算： （1）计算机通过做减法测试来实现判断：结果大于等于0，表明够减，商1；结果小于0，表明不够减，商0 （2）计算机将余数左移一位，再直接与不右移的除数相减原码恢复余数算法 假设[X]原=XS .X1 X2 ……Xn ，[Y]原=YS .Y1 Y2 ……Yn ，Q是X÷Y的商，QS是商的符号，R是X÷Y的余数，RS是余数的符号 原码除法运算的规则是： QS = XS ⊕YS ，RS = XS，|Q| = |X|÷|Y|-|R|÷|Y| 余数和被除数、除数均采用双符号位；初始余数为|X| 每次用余数减去|Y|（通过加上[-|Y|]补来实现），若结果的符号位为0，则够减，上商1，余数左移一位；若结果的符号位为1，则不够减，上商0，先加|Y|恢复余数，然后余数左移一位 循环操作步骤（3），共做n+1次，最后一次不左移，但若最后一次上商0，则必须+|Y|恢复余数；若为定点小数除法，余数则为最后计算得到的余数右移n位的值。

例如： X=+0.1011，Y=-0.1101，用原码恢复余数算法计算X÷Y 解：[X]原=0.1011 [Y]原=1.1101 |X|=0.1011 |Y|=0.1101 [-|Y|]补=11.0011 QS = XS ⊕YS = 1 RS = 0,,得[Q]原=1.1101 [R]原=0.00000111,原码不恢复余数算法（加减交替法） 加减交替法是对恢复余数除法的一种修正当某一次求得的差值（余数Ri)为负时，不是恢复它，而是继续求下一位商，但用加上除数（+Y）的办法来取代（-Y）操作，其他操作依然不变其原理证明如下： 在恢复余数除法中，若第一次i-1次求商的余数为Ri-1，下一次求商的余数为Ri，则： Ri=2Ri-1-Y 如果Ri0,商的第i位上0，并执行操作：恢复余数（+Y），将余数左移一位，再减Y，得Ri+1其过程可用公式表示如下： Ri+1=2（Ri+Y）-Y=2Ri+2Y-Y=2Ri+Y由此得到证明 所以可得出加减交替法的规则如下： 当余数为正时，商上1，求下一位商的办法，是余数左移一位，再减去除数；当余数为负时，商上0，求下一位商的办法，是余数左移一位，再加上除数。

此办法不用恢复余数，所以又叫不恢复余数法但若最后一次上商为0，而又需得到正确余数，则在这最后一次仍需恢复余数例如：X=+0.1011，Y=-0.1101，用原码不恢复余数算法计算X÷Y 解：[X]原=0.1011 [Y]原=1.1101 |X|=0.1011 |Y|=0.1101 [-|Y|]补=11.0011 QS = XS ⊕YS = 1 RS = 0,。