4-6.htm

浙江大学计算机学院计算机组成教材《计算机组成与设计》（潘学增）的课堂教学课件。

1.&nbsp; <b>原码乘法运算:</b></span></span></p>

<p><span style='mso-bookmark:带符号乘法运算'><span lang=EN-US style='font-size:13.5pt'>&nbsp;&nbsp;&nbsp;
我们一直处理的都是正数，将以上的算法转换成适合于带符号位的数的最好方法是，首先将两个操作数转化成其相应的正数，同时记录下两个操作数的符号位。这个算法将只循环31次，最高一位为符号位，将两个操作数的符号位异或产生的值置为结果的符号位。</span></span></p>

<p><span style='mso-bookmark:带符号乘法运算'><span lang=EN-US style='font-size:13.5pt'>&nbsp;
这种算法叫原码乘法运算.</span></span></p>

<p><span style='mso-bookmark:带符号乘法运算'><sup><span lang=EN-US style='font-size:
13.5pt'>&nbsp;&nbsp;</span></sup></span></p>

<p><span style='mso-bookmark:带符号乘法运算'><span lang=EN-US style='font-size:13.5pt'>&nbsp;&nbsp;&nbsp;
2.&nbsp; <a name="Booth's_Algorithm布斯算法"><b>Booth's Algorithm布斯算法</b></a><b> (补码乘法运算</b></span></span><b><span
style='font-size:13.5pt'>）</span></b></p>

<p><span lang=EN-US style='font-size:13.5pt'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
试想着我们计算0010<sub>two</sub>×0110<sub>two</sub>,<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
0010<sub>two</sub><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
×&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp; 0110<sub>two</sub><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
---------<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
+&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
0000&nbsp;&nbsp; shift (0 in multiplier)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
+&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp; 0010&nbsp;&nbsp;&nbsp; add (1 in multiplier)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
+&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
0010&nbsp;&nbsp;&nbsp;&nbsp; add (1 in multiplier)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
+&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
0000&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; shift (0 in multiplier)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
----------<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
00001100<sub>two</sub>k&nbsp;&nbsp;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 可以发现ALU可以通过加减得到上面计算的同样结果。<br>
&nbsp;&nbsp;&nbsp; For example, 6<sub>ten</sub> =-2<sub>ten</sub> + 8<sub>ten</sub>
, or&nbsp; 0010<sub>two</sub> = -0010<sub>two</sub> +1000<sub>two</sub>d<br>
&nbsp;&nbsp;&nbsp; 所以有下面的算法：<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
0010<sub>two<br>
</sub>&nbsp;&nbsp;&nbsp;<sub>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp; </sub>×&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 0110<sub>two</sub><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; -----------<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
+&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 0000&nbsp; shift (0 in multiplier)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
-&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 0010&nbsp;&nbsp; sub&nbsp;&nbsp; (first 1 in multiplier)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
+&nbsp;&nbsp;&nbsp; 0000&nbsp;&nbsp;&nbsp; shift (middle of string of 1s)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; +
0010&nbsp;&nbsp;&nbsp;&nbsp; add&nbsp;&nbsp; (prior step had last 1)&nbsp;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ------------<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 00001100<sub>two</sub>k</span></p>

<p><span lang=EN-US style='font-size:13.5pt'>&nbsp;&nbsp;&nbsp; Booth的这个算法速度要比以前版本的算法快，因为移位比加法要快，Booth算法最关键的就是看最后两位数字的值。例图如下：</span></p>

<p align=center style='text-align:center'><span lang=EN-US style='font-size:
13.5pt'><img border=0 width=298 height=52 id="_x0000_i1037"
src="images\4-6-pic4.gif"></span><span lang=EN-US><o:p></o:p></span></p>

<div align=center>

<table border=1 cellspacing=0 cellpadding=0 width="84%" style='width:84.0%;
 mso-cellspacing:0cm;mso-padding-alt:0cm 0cm 0cm 0cm' bordercolordark="#CC9966"
 bordercolorlight="#FFCC66">
 <tr>
  <td width="21%" style='width:21.0%;background:#CCFF99;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>Current bit</span></p>
  </td>
  <td width="25%" style='width:25.0%;background:#CCFF99;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>Bit to the right</span></p>
  </td>
  <td width="32%" style='width:32.0%;background:#CCFF99;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>Explanation</span></p>
  </td>
  <td width="25%" style='width:25.0%;background:#CCFF99;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>Example</span></p>
  </td>
 </tr>
 <tr>
  <td width="21%" style='width:21.0%;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>1</span></p>
  </td>
  <td width="25%" style='width:25.0%;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>0</span></p>
  </td>
  <td width="32%" style='width:32.0%;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>Beginning of a run of 1s</span></p>
  </td>
  <td width="25%" style='width:25.0%;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>00001111000</span></p>
  </td>
 </tr>
 <tr>
  <td width="21%" style='width:21.0%;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>1</span></p>
  </td>
  <td width="25%" style='width:25.0%;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>1</span></p>
  </td>
  <td width="32%" style='width:32.0%;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>Middle of a run of 1s</span></p>
  </td>
  <td width="25%" style='width:25.0%;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>00001111000</span></p>
  </td>
 </tr>
 <tr>
  <td width="21%" style='width:21.0%;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>0</span></p>
  </td>
  <td width="25%" style='width:25.0%;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>1</span></p>
  </td>
  <td width="32%" style='width:32.0%;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>End of a run of 1s</span></p>
  </td>
  <td width="25%" style='width:25.0%;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>00001111000</span></p>
  </td>
 </tr>
 <tr>
  <td width="21%" style='width:21.0%;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>0</span></p>
  </td>
  <td width="25%" style='width:25.0%;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>0</span></p>
  </td>
  <td width="32%" style='width:32.0%;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>Middle of a run of 0s</span></p>
  </td>
  <td width="25%" style='width:25.0%;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>00001111000</span></p>
  </td>
 </tr>
</table>

</div>

<p><span lang=EN-US style='font-size:13.5pt'>&nbsp;&nbsp;&nbsp; 第一步：有以下四种情况，这依赖于后两位的值。<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
00：a. Middle of a string of 0s, so no arithmetic operation.<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
01: b. End of a string of 1s, so add the multiplicand to the left half of the<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp; product.<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
10: c. Beginning of a string of 1s, so&nbsp; subtract the multiplicand from the<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp; left half of the product.<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;
11: d. Middle of a string of 1s, so no arithmetic operation.<br>
&nbsp;&nbsp;&nbsp; 我们需要在最右边加一个新的附加位 ，并且初始化为0。另外一个要求是在将product右移时，保持符号位的值右移。这样就可以处理带符号位的数字。例如将1110
0111 0<sub>two</sub>右移一位后是1111 0011 1<sub>two</sub>,而不是<br>
0111 0011 1<sub>two</sub>。这种位移称为<b>arithmetic right shift</b>，不同于a logical right
shift。<br>
&nbsp;&nbsp;&nbsp; Example: Lets try Booth's algorithm with negative numbers: 2<sub>ten</sub>×-3<sub>ten</sub>=-6<sub>ten</sub>
or&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 0010<sub>two</sub>×1101<sub>two</sub>=1111
1010<sub>two</sub>.<br>
<br>
&nbsp;&nbsp;&nbsp; Answer:&nbsp;&nbsp;&nbsp;&nbsp;</span><span lang=EN-US><o:p></o:p></span></p>

<div align=center>

<table border=1 cellspacing=0 cellpadding=0 width="79%" style='width:79.0%;
 mso-cellspacing:0cm;mso-padding-alt:0cm 0cm 0cm 0cm' bordercolordark="#CC9966"
 bordercolorlight="#FFCC66">
 <tr>
  <td width="15%" style='width:15.0%;background:#CCFF99;padding:0cm 0cm 0cm 0cm'>
  <p class=MsoNormal align=center style='text-align:center'><span lang=EN-US>Iteration</span></p>
  </td>
  <td width="36%" style='width:36.0%;background:#CCFF99;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>Step</span></p>
  </td>
  <td width="19%" style='width:19.0%;background:#CCFF99;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>Multiplicand</span></p>
  </td>
  <td width="30%" style='width:30.0%;background:#CCFF99;padding:0cm 0cm 0cm 0cm'>
  <p class=MsoNormal><span lang=EN-US>Product</span></p>
  </td>
 </tr>
 <tr>
  <td width="15%" style='width:15.0%;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>0</span></p>
  </td>
  <td width="36%" style='width:36.0%;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>Initial Values</span></p>
  </td>
  <td width="19%" style='width:19.0%;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>0010</span></p>
  </td>
  <td width="30%" style='width:30.0%;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>0000 1101 0</span></p>
  </td>
 </tr>
 <tr>
  <td width="15%" rowspan=2 style='width:15.0%;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>1</span></p>
  </td>
  <td width="36%" style='width:36.0%;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>1.c: 10=&gt;Prod=Prod-Mcand</span></p>
  </td>
  <td width="19%" style='width:19.0%;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>0010</span></p>
  </td>
  <td width="30%" style='width:30.0%;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>1110 1101 0</span></p>
  </td>
 </tr>
 <tr>
  <td width="36%" style='width:36.0%;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>2: Shift right Product</span></p>
  </td>
  <td width="19%" style='width:19.0%;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>0010</span></p>
  </td>
  <td width="30%" style='width:30.0%;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center'><span lang=EN-US style='font-size:
  13.5pt'>1111 0110 1</span></p>
  </td>
 </tr>
 <tr>
  <td width="15%" rowspan=2 style='width:15.0%;padding:0cm 0cm 0cm 0cm'>
  <p align=center style='text-align:center