乘法器

复习

第五章：由基础逻辑门（与或非三门）搭建了更复杂的逻辑门：异或门，同或门，多路选择器
第六章：设计完成了半加器，可以完成两个一位二进制数的加法，但不能处理来自低位的进位
第七章：设计完成了加法器，可以处理三个输入（两个加数和一个进位），并可以串联构成多位加法器
第八章：掌握了原码、反码和补码的概念，理解了补码可以统一加减法运算
第九章：设计完成了减法器，本质是加上一个负数（补码）

TL;DR

乘法可以转换为多次加法
通过移位和加法可以实现乘法
乘法器的核心是加法器和移位器

正文

本质

　　加减法有了，乘除法呢？加法有了，逆运算的减法也就有了，只要有了乘法，而除法是乘法的逆运算，问题应该也不大。

　　回忆小学怎样算乘法。列竖式，相加。

  23
×  5
----
 115

　　而乘法本质是反复加法。所以这实际上是：

  23 × 5 = 23 + 23 + 23 + 23 + 23

　　十进制可以这样算，二进制呢？

逐位相乘

　　不妨来试试： 3 × 5 = 15。简单起见，使用无符号数，没有符号位。

    0011   （3 的无符号二进制）
×   0101   （5 的无符号二进制）
--------    <-- # 表示占位符，没有意义
    0011    (被乘数 × 1)
   0000#    (被乘数 × 0，左移一位)
+ 0011##    (被乘数 × 1，左移两位)
 0000###    (被乘数 × 0，左移三位)
--------
    1111   （15 的无符号二进制）

　　可见竖式也能得出正确结果：0011 × 0101 = 1111_{2 进制无符号}，也即 15₁₀。

　　那就好办了，让一个二进制数，与另一个二进制数的每一位相乘，然后进行竖式一样的移位操作，最后加在一起就好了。因为补码可以参与运算，所以负数的乘法也解决了，下面就是实现了。

　　相乘，仔细观察可以用 and（与门）解决，那—— 移位呢？该怎么办？

移位

　　我们没有介绍过移位，但应该能想到，上面逐位相乘的移位，最简单的方式，就是在最后一位后面补零，同时丢掉最高位（以上述竖式的中间结果为例）：0011 不补零，0000 补一个，0011 补两个。

　　而在对有符号数进行移位时，特别是右移，最高位需要补上符号位，不然负数就变成正数了。也就是说：对 1010 进行右移，结果应该为 1101。

思考题 1

　　我们现在只有加法器，应该怎样移位和补位？以及， 设计一个最简单的乘法器，真的需要移位吗？

乘法器的构成

　　根据上面的分析，乘法器需要以下部件：

与门阵列：
- 用于判断乘数的每一位是否为 1
- 如果为 1，输出被乘数
- 如果为 0，输出全 0
移位器：
- 对每一步的结果进行左移
- 移位的位数取决于当前处理的是乘数的第几位
加法器：
- 用于累加每一步的结果
- 可以复用之前设计的加法器

具体实现

　　以 3(0011) × 5(0101) 为例，看看乘法器是如何工作的：

第一步（乘数最低位为 1，乘积结果为 0011，不移位，结果为本身）：
```
0011 × 1 = 0011
```
第二步（乘数次低位为 0，乘积结果为 0000，左移一位结果为 0000）：
```
0011 × 0 << 1 = 0000
```
第三步（乘数第三位为 1，乘积结果为 0011，左移两位结果为 1100）：
```
0011 × 1 << 2 = 1100
```
第四步（乘数最高位为 0，乘积结果为 0000，左移三位结果为 0000）：
```
0011 × 0 << 3 = 0000
```

最后，将所有结果相加：

  0011
+ 0000
+ 1100
+ 0000
-------
  1111 (15)

优化思路

　　上述逐位相乘有一个问题：

　　如果是 M × 0100 这样就还好，只用加一个数字——因为只要乘数的某一位为 0，结果就必定为 0。所以逐位相乘，结果就是 0 + M + 0 + 0，实际上只用加 M 这一个数字。

　　如果是 M × 1111 这样的呢？就需要加四个数字——M + M + M + M。这在乘数位数变多（比如 64 位）的时候，连续的 1 将极为致命，会严重拖慢计算速度，效率变低。

　　目前学者想出了两种优化思路：

Booth 算法：
- 利用连续的 1 可以转换为减法来减少计算步骤
- 比如 "1111" 可以看作 "10000 - 1"
华莱士树：
- 并行处理多个部分积
- 减少加法器的级联深度
- 因为有些复杂，所以本指南略过

Booth 算法

　　Booth 算法优化了连续的 1 这种情况。Booth 算法的核心思想是：对于二进制补码的每一位，我们可以通过判断它与它前一位的关系，来决定是否进行加减操作。

　　看不懂？来个例子。

　　设 X_补码 = X_sX_nX_n-1...X₁X₀, Y_补码 = Y_sY_nY_n-1...Y₁Y₀，有 M × 00111000。

　　而 M × 00111000 = M × ( 2³ + 2⁴ + 2⁵ ) = M × (01000000 - 00001000) = M × ( 2⁶ - 2³ ) = 2⁶ × M - 2³ × M。

　　原乘数 00111000 中，10 表示连续 1 的开始，对应 - M × 2³，01 表示连续 1 的结束，对应 M × 2⁶，那么可以得出移位的规则：

Y_n+1	Y_n	操作规则
0	0	部分积右移一位
0	1	【部分积 + X_补码】，部分积右移一位
1	0	【部分积 - X_补码】，部分积右移一位
1	1	部分积右移一位

为什么要右移？
- 往上划到逐位相乘的例子，计算部分积的时候，低位往往不受高位的数值影响（看上面的竖式更容易理解）：
  - 计算完 0011，此时部分积为 0011，此后最右边的 1 不受后面计算的影响。
  - 计算完 0011 + 0000#，此时部分积为 0011，此后最右边的 11 不受后面计算的影响。
  - 计算完 0011 + 0000# + 0011##，此时部分积为 1111，此后最右边的 111 不受后面计算的影响。
  - 以此类推。
- 因为不受高位的影响，所以可以右移将低位挤掉，使部分积与被乘数对齐，这样可以直接计算。
【部分积 - X_补码】怎样计算？
- 回忆一下第四章：减法在二进制计算机里的定义是，加上减数取反后的数值，再加一
为什么移位规则里， 01 和 10 的规则，一个正一个负？
- 因为 10 表示连续 1 的开始，对应 - M × 2³，01 表示连续 1 的结束，对应 M × 2⁶
- 而上述 2³ 和 2⁶，已经在移位中解决了，所以只用加减 X_补码