乘法器

Les architectures dédiées avec multiplicateurs
带乘法器的专用架构

有些处理器或数字电路会专门设计一个硬件乘法器，用来快速完成乘法，而不是只靠普通的加法器慢慢算。

2. 早期微处理器没有硬件乘法器

在最早的微处理器中，没有专门的硬件结构来处理乘法。

也就是说，早期 CPU 里面通常只有比较基础的：

  • 加法器
  • 累加器
  • ALU，也就是算术逻辑单元

没有专门的 multiplier，也就是乘法器。

所以乘法不能一步完成，只能转化成一连串的加法。

比如：

5 × 4 = 5 + 5 + 5 + 5

这就叫：

additions successives dans l’accumulation
在累加器中进行连续加法

3. 这种方法的问题

笔记里列了两个限制：

第一，处理时间很长

如果用连续加法做乘法，那么乘数越大，加法次数越多。

例如：

45 × 21

可以理解成：

45 + 45 + 45 + ... + 45

一共加 21 次。

如果数字更大，比如：

45 × 1000

就要加 1000 次，速度非常慢。

第二，执行时间依赖数据

dépendance à la nature de la donnée
执行时间取决于数据本身

意思是：不同的数据会导致不同的运行时间。

例如：

45 × 2

很快。

但：

45 × 200

就慢得多。

这会带来一个问题：

Impossible de contrôler les timing d’exécution
很难控制执行时间

在某些系统里，比如实时系统、信号处理、嵌入式控制系统，执行时间必须稳定可预测。如果乘法时间忽长忽短，就很难设计系统时序。

所以需要：

développer du hardware spécifique
开发专门的硬件

也就是专门的硬件乘法器。

4. 二进制乘法的基本思想

La multiplication binaire
二进制乘法

例子是：

101101 × 10101

所以这个乘法等价于：

45 × 21 = 945

而：

945₁₀ = 1110110001₂

所以最终结果应该是：

101101 × 10101 = 1110110001

5. 二进制竖式乘法怎么做

二进制乘法和十进制竖式乘法很像，只不过每一位只可能是 0 或 1。

所以结果是：

1110110001₂

也就是十进制的：

945₁₀

硬件逻辑电路

如果我要用门电路实现一个 2 位 × 2 位的乘法器，每一个输出位应该怎么由输入位算出来？

1. 单个 bit 的乘法

这正好就是逻辑与门 AND 的功能。

2. 两个 2 bit 数相乘

Multiplication de 2 mots de 2 bits

两个 2 位二进制数相乘。

如果两个二进制字长分别是 m 和 n，那么结果需要 m + n 位。

所以：

2 bit × 2 bit → 4 bit

3. 用竖式看 2 位乘法

这些叫做部分积，法语produits partiels。

logique avec anticipation de retenu

带进位提前的逻辑，或者叫进位预判逻辑。

进位传播

C0 = (a1 · b0) · (a0 · b1)

又因为：

C1 = (a1 · b1) · C0

把 C0 代进去：

C1 = (a1 · b1) · (a1 · b0) · (a0 · b1)
C1 = a1b0 · a0b1 · a1b1

这就是把进位直接展开成输入信号的逻辑表达式。

好处是：可以更快得到最高位 m3，不用等进位一级一级传递。

4. 用一个例子验证

假设：

A = 11₂ = 3
B = 10₂ = 2

也就是：

a1 = 1, a0 = 1
b1 = 1, b0 = 0

真实结果应该是：

3 × 2 = 6 = 0110₂

代入公式：

m0 = a0b0 = 1 · 0 = 0

m1 = a1b0 ⊕ a0b1
   = 1·0 ⊕ 1·1
   = 0 ⊕ 1
   = 1

C0 = a1b0 · a0b1
   = 0 · 1
   = 0

m2 = a1b1 ⊕ C0
   = 1·1 ⊕ 0
   = 1

C1 = a1b1 · C0
   = 1 · 0
   = 0

所以：

m3 m2 m1 m0 = 0 1 1 0

结果是：

0110₂ = 6

正确。

硬件结构图

2 位二进制乘法器的内部结构表示

1. 上半部分：门级逻辑图

Représentation structurelle de l’architecture interne
内部架构的结构表示

(a1 a0) × (b1 b0) = m3 m2 m1 m0


m0 = a0b0

m1 = a1b0 ⊕ a0b1

C0 = a1b0 · a0b1

m2 = a1b1 ⊕ C0

m3 = a1b1 · C0

2. 下半部分：用 HA 简化结构图

Représentation structurelle à partir de la représentation arithmétique

从算术表示出发得到结构图

2 位乘法器 扩展到 3 位 × 3 位二进制乘法器

(a2 a1 a0) × (b2 b1 b0) = m5 m4 m3 m2 m1 m0

1. 先生成所有部分积

les produits partiels ax by sont obtenus par des AND

所有部分积 ai bj 都可以通过 AND 门得到。

Pij = ai · bj

m5 = P22C3 + P22C4 + C3C4
m4 = P22 + C3
m3 = P21 + C1 + P12
m2 = P20 + P11 + C0 + P02
m1 = P10 + P01
m0 = P00

2. RCA 结构

RCA structure

Ripple Carry Adder
串行进位加法器 / 行波进位加法器

Cette structure est un multiplieur parallèle.

这个结构是一个并行乘法器。

因为所有部分积 Pij 可以同时由 AND 门算出来，而不是像早期处理器那样重复加很多次。

L’objectif est de limiter les ressources matériel

目标是限制硬件资源。

也就是不要无限堆很多复杂电路，要在速度和硬件数量之间折中。

On cherche également à réduire le chemin critique.

同时也希望减少关键路径。

关键路径就是信号从输入到输出经过的最长逻辑路径。
关键路径越长，电路最大频率越低，速度越慢。

在 RCA 结构里，问题是进位要一级一级传：

C0 → C1 → C2 → C3 → C4 → m5

所以关键路径可能比较长。

9. 你最后中文提到的 CSA

还有一个 CSA 结构，关键路径经过的门少。

这里的 CSA 是：

Carry Save Adder
进位保存加法器

它和 RCA 的区别是：

RCA：每一级马上把进位传到下一列

CSA：先不立刻传播进位，而是把 sum 和 carry 分开保存

所以 CSA 可以减少中间进位传播的等待时间，关键路径更短，速度更快。

但是 CSA 通常会需要更多一点硬件，最后还需要一个 RCA 或类似加法器，把保存的 carry 和 sum 加成最终结果。