SI100B Spring 2025 EE Part

Week 2: Homework 2

@Qihan Ding
dingqh@shanghaitech.edu.cn
@Quanyu Chen
chenqy2022@shanghaitech.edu.cn

Contents

Contents

Exercise 1: Multiplier

Tutorial 2:Homework 2

Exercise 1: Multiplier

1.1. 一位乘法

在上一次习题课中，我们曾经学习过一位二进制数的加法：

  • 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = (1)0
    • 如果不考虑进位，我们会发现，加法的本质上是按位异或运算！

类似的，一位二进制数的乘法也非常简单：

  • 0 * 0 = 0, 0 * 1 = 0, 1 * 0 = 0, 1 * 1 = 1
    • 观察可以发现，乘法的本质上是按位与运算！
A B A XOR B A + B
0 0 0 0
0 1 1 1
1 0 1 1
1 1 0 0
A B A AND B A * B
0 0 0 0
0 1 0 0
1 0 0 0
1 1 1 1
Tutorial 2:Homework 2

Exercise 1: Multiplier

1.2. 多位乘法

核心思路

将复杂的多位数乘法拆解为多个简单的"一位数乘法"，再通过"位权"调整后相加。

基本概念（以十进制为例）

  • 被乘数：乘法算式中被乘的数字（通常写在前面）。
    • 例：4 × 2 = 8 中，4是被乘数，2是乘数。
  • 部分积：用乘数的每一位单独乘被乘数得到的中间结果。
    • 例：12 × 3 中，10 × 3 = 30 和 2 × 3 = 6 都是部分积。
  • 位权：数字在不同位置上代表的不同价值（十进制中：个位=×1，十位=×10，百位=×100…）。
    • 例：111中，个位的1实际是1×1，十位的1是1×10，百位的1是1×100。
Tutorial 2:Homework 2

Exercise 1: Multiplier

1.2. 十进制多位乘法

  1. 拆解乘数：把乘数 按位数拆开 → （百位）、（十位）、（个位）。
  2. 逐位相乘，计算位权，得到部分积：
    • 百位： （因为 在百位，权值是 ）
    • 十位： （权值是 ）
    • 个位： （权值是 ）
  3. 错位相加：将上述部分积按权值对齐后相加，即得到最终乘积。
Tutorial 2:Homework 2

Exercise 1: Multiplier

1.2. 十进制多位乘法

计算 ：

  1. 拆解乘数 → （十位）、（个位）。
  2. 计算部分积：
    • ，实际是 （因为 在十位）。
    • ，实际是 （个位）。
  3. 相加：。
Tutorial 2:Homework 2

Exercise 1: 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.3. 两位二进制数的乘法

对二进制数进行相乘操作，可以被归结为如下三个步骤：

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

Exercise 1: Multiplier

1.4. 二进制乘法和移位操作

二进制乘法的部分积计算与十进制乘法类似，最大的区别是二进制数的位权是 ，而不是 。

  • 例如：二进制的“十位”的位权是 ，而不是 。
  • 当然，如果用二进制记录位权，“”也可以表示为“”！

值得注意的是，二进制的“”操作实际上相当于二进制的“左移”操作！我们可以看一个例子：

  • 数
  • 其左移一位后变成 ，即
  • 其乘以 后变成 ，即
  • 也就是说，二进制的“左移一位”操作实际上就是乘以 ！
  • 进一步的，我们可以发现，二进制的“左移 位”操作实际上就是乘以 ！
Tutorial 2:Homework 2

Exercise 1: Multiplier

1.5. 使用 Python 模拟二进制乘法

Python中的二进制乘法可以通过位运算符实现。具体来说，就是使用 & 运算符进行按位与操作，使用 << 运算符进行左移操作。

我们尝试在 Python 中实现一个简单的二进制乘法函数，来理解乘法器的原理：

  • a 和 b 分别表示要相乘的两个二进制数
  • result 表示最终的乘积
  • 在每次循环中，我们需要判断 b 的最低位是否为1
    • 如果是，我们将 a 加到 result 中；否则，我们什么也不做。
    • 然后，我们将 a 左移一位，b 右移一位，进入下一次循环，直到 b == 0。
  • 你可以通过 print 函数来输出中间结果。
Tutorial 2:Homework 2

Exercise 1: Multiplier

1.5. 使用 Python 模拟二进制乘法

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
Tutorial 2:Homework 2

Exercise 1: Multiplier

1.6. 阵列乘法器

阵列乘法器模拟了上述 Python 程序的二进制乘法运算过程：

  • 将乘数逐位拆分，与被乘数的各个位进行逻辑与运算，得到一组二进制部分积。
  • 部分积作为每一位的被加数输进加法器中，与下一级的部分积进行相加操作，加法器会输入上一位的进位，然后将本级进位输出到下一位的加法器中。
  • 随着部分积的位权由低到高，通过逐级左移一位排布的加法器阵列，可以模拟乘法的过程，并且输出结果。
Tutorial 2:Homework 2

Exercise 1: Multiplier

1.6. 阵列乘法器

图为我们的阵列乘法器的示意图。

  • 可以注意到，乘法器的电路比较规整
  • 我们可以通过合理的 Tunnels 的使用，清晰整齐的完成这次作业。

#c

Tutorial 2:Homework 2

1.7. 输入、输出和实现要求

  • 输入： 乘法器接受两个 4 位的二进制数 A 和 B。
  • 输出： 乘法器输出一个 8 位的二进制数 result，表示 A 和 B 的乘积。
  • 实现要求： 你需要使用 Logisim 实现这个乘法器，其中你可以使用 Logisim 自带的加法器实现加法和移位操作，但不允许使用 Logisim 自带的乘法器。
Tutorial 2:Homework 2

【彩蛋】An Example of Multiplier！

#c

Exercise 2: 简易 ALU

Tutorial 2:Homework 2

Exercise 2: 简易 ALU

在这个 Exercise 里，我们需要用结合之前所学的知识（选择器、加法器、减法器等），搭建一个 ALU。

  • ALU 的乘法器部分需要使用你在 Exercise 1 中实现的乘法器，不允许使用 Logisim 自带的乘法器。

Tutorial 2:Homework 2

Exercise 2: 简易 ALU

2.1 ALU 介绍

ALU（Arithmetic & Logic Unit，算术逻辑单元）是计算机中进行所有数字计算和逻辑操作的核心部件。它根据选择信号执行不同的操作，包括算术运算、位逻辑运算和移位运算等。在本题中，我们需要设计一个 共 11 位输入的 ALU：

  • 输入端：

    • 数据输入 A：一个 4 位数（A[3:0]）
    • 数据输入 B：一个 4 位数（B[3:0]）
    • 选择信号 ALU_sel：一个 3 位数，用于选择 8 种不同的操作（ALU_sel[2:0]）。

  • 输出端：

    • 数据输出 result：一个 4 位数，根据选择信号的不同，ALU 执行以下 8 种操作：
Tutorial 2:Homework 2

Exercise 2: 简易 ALU

2.2 ALU 操作表

ALU_sel 信号的 3 位二进制数可以选择 8 种不同的操作。

  • 在电路中，我们通常的实现逻辑是：我们并行的实现所有的操作，然后通过选择器来选择输出。
  • 除了乘法之外，其他的操作都可以通过内置的电路模块来进行实现。
ALU_sel 操作 输出结果 result
000 加法 result = A + B
001 减法 result = A - B
010 乘法（低四位） result = (A * B)[3:0]
011 乘法（高四位） result = (A * B)[7:4]
100 比较（A > B） result = (A > B) ? 1 : 0
101 左移（A） result = A << 1
110 右移（A） result = A >> 1
111 按位与 result = A & B
Tutorial 2:Homework 2

Exercise 2: 简易 ALU

2.3 ALU 操作细节说明

  • 加法： 当 ALU_sel = 000 时，ALU 执行加法运算，result = A + B。
  • 减法： 当 ALU_sel = 001 时，ALU 执行减法运算，result = A - B。
  • 乘法： 当 ALU_sel = 010 时，ALU 输出乘法结果的低四位，即 (A * B)[3:0]；当 ALU_sel = 011 时，ALU 输出乘法结果的高四位，即 (A * B)[7:4]。
  • 比较（A > B）： 当 ALU_sel = 100 时，ALU 比较 A 和 B 的大小。如果 A 大于 B，输出 1，否则输出 0。
    • 我们的比较操作是无符号比较。你需要修改 Logisim 中内置比较器的默认设置来实现无符号比较。
    • “无符号”的英文是 unsigned，而默认的操作是补码比较，其英文为 complement。
  • 左移： 当 ALU_sel = 101 时，ALU 对 A 执行左移操作，result = A << 1。
  • 右移： 当 ALU_sel = 110 时，ALU 对 A 执行右移操作，result = A >> 1。
  • 按位与： 当 ALU_sel = 111 时，ALU 执行按位与操作，result = A & B。
Tutorial 2:Homework 2

Exercise 2: 简易 ALU

2.4 输入、输出和实现要求

  • 输入： ALU 接受两个 4 位的数字 A 和 B，以及一个 3 位的选择信号 ALU_sel。
  • 输出： ALU 输出一个 4 位的结果 result，它是根据选择信号 ALU_sel 所指定的运算结果。
  • 实现要求： 你需要使用 Logisim 实现这个 ALU，其中乘法器部分需要使用你在 Exercise 1 中实现的乘法器；除此之外，你可以使用 Logisim 自带的加法器、减法器、比较器、移位器和 MUX 等组件。

Optional Themes: ShanghaiTech_Tutorial / NaiLoong / QYGG