SI100B EE Part

Tutorial 2

@Yunxiang He | heyx1@shanghaitech.edu.cn
@Chaofan Li | lichf1@shanghaitech.edu.cn
@Qihan Ding | dingqh@shanghaitech.edu.cn

Homework

Exercise 3: Multiplier

Exercise 3: Multiplier

基本的乘法运算逻辑，hw2文档里已经作了介绍：

## Exercise 3: Multiplier

**我们需要用full_adder作为子电路完成ex3**，TA已经为大家导入，**请保证，ex3，full_adder两个文件在同一个文件夹路径下**

我们已经实现了加法和减法。现在我们要尝试一些更复杂的运算：乘法。

乘法的实现有很多种：我们可以通过不断进行移位的乘法和加法来实现，也可以通过引入更多的硬件资源，在一个组合电路中直接实现乘法运算。

在 Exercise 3 里，我们实现一个比较简单的版本：直接通过模拟乘法的运行规律来实现一个四位+四位->八位的乘法器。不必感到有压力，我们会在这一部分设置足够的铺垫内容。

### 3.1. 乘法运算过程
试想，在十进制下，我们列竖式将两个数字相乘时的思路：

我们将两数中的被乘数完整保留，与被逐位拆分的乘数分别进行乘法运算，从而获得**部分积**，再为每个**部分积**追加**位权**（这也就是为什么竖式要求将部分积错位相加），最终相加得到乘积。

依照常识，我们约定：

> 1. **被乘数**指四则运算的乘法中被乘的数字，一般来说放在算式的前面。如：4×2=8: 上述算式中，4是**被乘数**，2是**乘数**

> 2. 在乘法中，如果乘数是两位或两位以上的数，乘的时候，就要用乘数的每一位去乘被乘数，每次乘得的积，叫做**部分积**，或叫做不完全积。

> 3. **位权**指数码在不同位置上的权值。在进位计数制中，处于不同数位的数码代表的数值不同：如十进制数111，个位数上的1 的权值为 $10^1$ ，十位数上的1 的权值为 $10^2$ ，百位数上的1 的权值为 $10^3$ 。

例如，三位数 `abc` 与 `xyz` 相乘（每一个字母代表相应数位上的数字）：

`abc * xyz = x * abc * 100 + y * abc * 10 + z * abc * 1`

Exercise 3: Multiplier

考虑两位二进制数相乘：

010 * 010 = 100 
= 10 * 1 * 10 + 10 * 0 * 1 = 100 + 0;

010 * 011 = 110 
= 10 * 1 * 10 + 10 * 1 * 1 = 100 + 10;

011 * 010 = 110 
= 11 * 1 * 10 + 11 * 0 * 1 = 110 + 0;

011 * 011 = 1001 
= 11 * 1 * 10 + 11 * 1 * 1 = 110 + 11;

对二进制数进行相乘操作，本质上是：

  1. 将乘数逐位拆分，与被乘数的各个位进行逻辑与运算，然后得到一组二进制部分积；
  2. 乘数的每一位有不同的位权，因此需要为部分积追加位权；
  3. 将经过追加位权的部分积加起来，得到结果。

部分积追加位权的细节

因为高一位的乘数乘得的部分积与低一位的乘数乘得的部分积相比，对于二进制来说，前者是后者的两倍，所以对应的高一位的部分积要乘以2，也就是二进制下的“10”。对于二进制来说，一个数乘以“10”，实际上就是将这个二进制数左移了一位，并为最后一位补上0（例如：11 110）。我们可以通过一个Python位运算的例子来理解移位操作。

Exercise 3: Multiplier

Python中的二进制乘法可以通过位运算符实现。
例如，将二进制数1010左移两位，即可得到101000，相当于将原数乘以2的2次方。

运算符 含义 运算规则
& 按位与 将两个二进制数的对应位相与，只有当两个位都为1时，结果位才为1，否则为0
| 按位或 将两个二进制数的对应位相或，只有当两个位都为0时，结果位才为0，否则为1
^ 按位异或 将两个二进制数的对应位进行异或运算，如果两个位不同，则结果位为1，否则为0
~ 按位取反/非 将翻转二进制数每个位的值，将0变为1，将1变为0

Exercise 3: Multiplier

def binary_multiply(a: int, b: int) -> int:
    result: int = 0
    while (b > 0):
        if (b & 1):
            result += a
        a <<= 1
        b >>= 1
    return result

a 和 b 分别表示要相乘的两个二进制数，result 表示最终的乘积。在循环中，每次判断 b 的最低位是否为1，如果是，则将 a 加到 result 中；然后将 a 左移一位，b 右移一位，继续循环，直到 b == 0。

Exercise 3: Multiplier

四位阵列乘法器

Exercise 3: Multiplier

4 Booth乘法器

Radix编码

如图所示，红框中的数即为部分积。我们知道：

01110 = 10000 - 00010

因此，上述5个数相加就可化简为2个数相减：

110100000-110100

减法可以用加补码表示:

110100000+001100

部分积的零值是不影响加法结果的，在计算中可以忽略，上述四个部分积的相加，实际上可以简化成两个非零部分积相加，从而减少加法器的数目。要注意，当有连续的“1”时，这种方法效果最佳。

Exercise 3: Multiplier

Booth变换/Booth编码

Booth变换/Booth编码

Radix-2 Boooth Multiplier

Radix-4 Boooth Multiplier

Booth变换/Booth编码

这种变换，就是(改进的)布斯变换，或称布斯编码。布斯变换可以对连续1的位数大于等于3的二进制数起到化简作用，连续1的位数越多，化简效果越好。基4编码相当于每次用乘数的两位与被乘数相乘产生部分积，从而使部分积个数减少一半，也可以看成是将乘数转化为4进制表达，故称为基4(Radix-4 Booth Encoding)。


一般情况下，将部分积通过华莱士压缩树进行压缩，将压缩出的最后的carry和sum做全加就得到了我们想要的结果。

Main Task

Build an Multiply-Accumulated Systolic Array!