乘法器
1.1 加法的叠加
乘法本质上是多次加法运算的叠加。在二进制运算中，乘法则是简单的移位操作。例如 \(101_2=5_{10}\)，\(1010_2=10_{10}\)。
如果要将两个无符号 \(n\) 位二进制数 \(a_{n-1},\cdots,a_0\) 和 \(b_{n-1},\cdots,b_0\) 相乘，我们可以将 \(a\) 的副本移位并加到 \(b\) 中为 1 的位置上。即
\text{result}=\sum_{i=0}^{n-1}b_i(a<<i)
例如：计算 \(101_{2}\times110_2(5_{10}\times6_{10})\)，我们可以用下面的竖式运算过程完成。
可以看到，乘法计算过程共分为三步：
- 第一步计算移位，即将乘数的副本左移 \(0\sim n-1\) 位；
- 第二步将移位结果 \(\text{AND}\) 被乘数对应位置的数值；
- 第三步计算每一位的最终和。
因此，四位无符号二进制数乘法电路的结构可以如下图所示：
★ 1.2 移位乘法器
基于组合逻辑实现的乘法器电路较为复杂，且消耗的硬件资源也较多。因此，我们可以采用时序逻辑电路实现乘法运算的过程。下图展示了一个基础的乘法器结构：
整个电路包含三个寄存器（被乘数 Multiplicand、乘数 Multiplier、乘积 Product）、一个加法器和一个控制单元。我们用一个简单的二进制乘法作为例子：\(1000\times1001\)。这是两个四位的二进制数相乘，为此我们要实现一个四位的乘法器。
-
被乘数寄存器（Multiplicand Reg）是一个 8 位的寄存器，且带有左移的功能。它有一个左移的控制信号输入，当外部的控制单元（Control）将这个信号置为有效时，在下一个时钟上升沿到来时被乘数寄存器当中的内容就会向左移动一位。
-
乘积寄存器（Product Reg）也是一个 8 位的寄存器，用来保存当前运算的结果。该寄存器包含一个写使能信号，由控制单元给出。
-
乘数寄存器（Multiplier Reg）是一个 4 位的寄存器，且带有右移的功能。该信号同样由外部的控制单元给出。此外，控制单元会读取乘数寄存器最低位的数值，以决定下一阶段的运算过程。
-
被乘数寄存器和乘积寄存器当中的内容需要进行加法运算，因此我们就需要一个 8 位的加法器，它会将被乘数寄存器和乘积寄存器当中的内容进行相加，并将结果再送到乘积寄存器当中。
现在，我们就来看一看这样的一个乘法器是如何工作的。首先，我们对乘法器进行初始化。置乘数为 Multiplier = 4'B1001，被乘数为 Multiplicand = 8'B0000_1000，乘积寄存器设置为 Product = 8'B0000_0000。
下面开始计算，请大家回忆我们用纸笔时是如何进行这个运算的。首先，我们检查乘数寄存器的最低位，看其是否为 1。现在发现它是 1，那么就需要将被乘数寄存器当中的内容和当前乘积寄存器当中的内容进行相加。控制单元向乘积寄存器发出写使能信号 enable，乘积寄存器便会写入当前加法器的运算结果（我们用黄色字体表示当前时钟上升沿已完成的操作）。
在一步运算结束之后，我们需要将被乘数左移一位，进入下一次计算。
此时，由于最低位是 0，因此乘积寄存器不会进行写入操作。
接下来重复上述的操作过程。因为乘数的位数是 4，所以我们需要重复执行上述操作共 4 次，才能在乘积寄存器中读取到最终的结果。
最终乘积寄存器的结果为 \(01001000_2=72\)，而 \(1000_2\times1001_2=8\times9=72\)，表明我们的运算过程是正确的。
总结一下，N 位乘法器（被乘数和乘数为 N 位，乘积为 2N 位）的工作流程如下：
一个简单的判断标准是：被乘数寄存器和乘数寄存器都需要移位 N 次。
★ 1.3 乘法器优化版
在购买一台计算机时，我们不仅希望它的性能足够好，还希望它的价格足够低。那对于 CPU 这样的集成电路而言，其价格的一个重要因素就是其中晶体管的数量，或者说是芯片的面积。因此，在我们设计各个功能部件的时候，如何减小芯片的面积也是一个重要的优化方向。
那么，上面的移位乘法器有没有可以优化的地方呢？我们再次回到计算的初始状态：
不难发现：
-
对于被乘数寄存器（Multiplicand Reg），由于我们的被乘数只有 4 位，因此该寄存器中的高 4 位是无用的。
疑问
有的同学可能会说，这高四位是用来移位的呀！确实如此！但我们在左移的同时往低位也补了 0，如果从循环移位的角度来看，为了移位而设置额外的寄存器空间也是一种浪费。我们将在下面揭开谜底。
-
对于乘数寄存器（Multiplier Reg），虽然一开始是没有浪费的，但是在运算的过程中，每个周期其内部有效的数字便会减少 1 位。因此，这也是一种潜在的浪费。
-
最后，乘积（Product）确实需要 8 位才能保存，但是乘积寄存器在不断的保存中间结果，而中间结果一开始并不是 8 位的。当被乘数还集中在最低四位的时候，这个运算结果实际的有效数字只有最低的 4 位，只是随着被乘数寄存器不断的左移，乘积寄存器当中的有效数字才不断地增加，最后才达到了 8 位。所以说，对于乘积寄存器，虽然最终它没有浪费，但是在计算的过程中是存在资源浪费的。
我们应当如何基于上述的分析对移位乘法器进行优化呢？
首先，被乘数寄存器是一个 8 位带有左移功能的寄存器，但其内部的有效数字始终只有 4 位。我们可以直接使用一个 4 位的寄存器。并取消其左移功能。这样，被乘数的 4 位就可以一直要参与运算，寄存器也就变成了一个普通的寄存器。
其次，乘积寄存器是 8bits 位宽的，但是初始时有效数字只有 4 位，且每周期增加 1 位。我们不能削减乘积寄存器的宽度，因为乘法运算的结果需要 8bits 位宽。但在运算过程中，我们需要保持成绩寄存器和被乘数寄存器之间的对齐关系。既然被乘数寄存器不能左移了，我们让乘积寄存器右移也可以达到同样的效果。此时，乘积寄存器的初始值就需要放在寄存器的高四位，以便于接下来的右移过程。
现在，参与加法运算的有效数字实际上只有 4 位（因为被乘数寄存器已经被削减到了 4 位，而乘积寄存器初始值放在了高 4 位的地方），所以我们只需要一个 4 位的 ALU。
最后，我们还需要一个 4 位带有右移功能的乘数寄存器。仔细思考一下，我们真的还有必要设置这个寄存器吗？你可能已经注意到了：乘积寄存器的低四位还是空余的，并且它正好是一个最开始位宽为 4bits 且带有右移功能的寄存器！此外，乘积的结果每个周期会右移 1 位，因此乘积寄存器低位的空余每个周期会减少一位，而这正好是乘数寄存器所需要的功能。所以，我们可以把乘数放在乘积寄存器的低 4 位，从而取消乘积寄存器这个部件。
基于上面的分析过程，我们可以得到以下优化版的乘法器，该乘法器相比于基础版减少了一定的空间开支。
同样的计算过程如下：
但是！上面介绍的乘法器结构存在一个 Bug。当我们在计算 \(1111\times1111\) 时就会发现，加法器在加法运算时出现了溢出！如果直接丢弃这些溢出会导致结果运算错误。因此，我们需要在乘积寄存器中额外增加 1 位的空间，用于储存可能溢出的结果。
思考
为什么没优化前的移位乘法器不会出现溢出的情况呢？
对于经过优化后的 N 位乘法器。我们需要一个 N 位的寄存器保存被乘数，还需要一个 N 位的加法器进行中间结果的运算，以及一个 2N+1 位的带右移功能的寄存器同时保存乘积和乘数。
1.4 有符号乘法
到目前为止，我们只处理了无符号数乘法的情况。对于如何处理带符号乘法，最简单的方式是先把乘数和被乘数转换为正数（取反加一），然后记住它们的初始符号。这样，将之前的算法迭代执行 31 次，符号位不参与计算（也可以不做改动执行 32 次，因为乘数不管转换与否符号位总为 0，但会多造成一个周期的资源浪费）。正如我们在小学学到的那样，只有在乘数和被乘数符号相反时，对积取反。
你可以使用 Lab6 中的减法器模块完成上面的取相反数操作。
Tips：仿真波形
在测试有符号乘法器时，你可以在仿真时将显示的进制设置为有符号十进制（Signed Decimal）。
参考资料
暂无