加法器

---

1. 半加器：Addition de 2 bits

---

2. 半加器的逻辑公式

从真值表可以看出：

逻辑公式
s = a ⊕ b
r = a · b

---

3. 半加器电路图

---

全加器

additionneur complet

full adder

1. 为什么需要全加器？

做多位二进制加法时，每一位不仅要加 a 和 b，还要加上一位传来的进位。

例如：

  1011
+ 0111

从低位往高位算时，某一位实际要算：

ai + bi + ri-1

ri-1

就是前一位传来的进位。

faut ajouter la 3ème entrée pour la retenue de l'étage précédent

必须增加第 3 个输入，用来接收前一级的进位

2. 全加器的输入和输出

S = A ⊕ B ⊕ ri-1

也可以分两步看：

第一步：

A ⊕ B

第二步：

S = (A ⊕ B) ⊕ ri-1

得到 S

3. 进位 rᵢ 的公式

进位输出是：

ri = A·B + ri-1·(A ⊕ B)

这个公式非常重要。

4. 最后一句：可以处理减法

On peut traiter les ops de soustraction en travaillant en complément 2

可以用二进制补码来处理减法运算

也就是说，计算机里通常不单独做一个复杂的减法器，而是把减法变成加法。

例如：

A - B

可以写成：

A + (-B)

而 -B 用二进制补码表示。

所以加法器不仅能做加法，也能配合补码做减法。

---

4 位全加器、7483 加法器芯片，以及最后一种更快的加法结构：进位选择加法器 carry-select adder。

1.用 1 bit 全加器组成 4 bit 加法器

4 个 1 bit full adder 串起来。

所以 4 bit 加法结果是：

S3 S2 S1 S0

最后的 C4 是最高位之后的进位，也常被看作 carry out，有时也用来判断无符号数溢出。

2. 7483 是 4 bit 全加器芯片

7483 是一个经典的 4 bit 二进制全加器。

它内部其实就相当于已经封装好了 4 个 full adder。

也就是说，一个 7483 的功能是：

A[3:0] + B[3:0] + C0 = C4 S3 S2 S1 S0

3. 两个 7483 级联成 8 bit 加法器

左边的 7483 处理低 4 位：

它的输入进位接：

C0 = 0

输出：

S0...S3
C4

这个 C4 会接到右边 7483 的输入进位端。

右边的 7483 处理高 4 位：

它输出：

S4...S7

最后还有一个最高进位：

C8 overflow

这种结构叫 ripple-carry adder，也就是串行进位加法器。

4. ripple-carry 的问题：慢

这种普通级联方式有一个问题：

高 4 位必须等低 4 位算出进位以后才能开始得到正确结果

也就是说，右边的 7483 需要等左边的 C4 稳定之后，才能确定高 4 位结果。

如果是 16 bit、32 bit，进位要一段一段传过去，延迟会越来越大。

5. 下面：优化方法，进位选择加法器

carry-select adder
进位选择加法器

既然高 4 位不知道低 4 位传来的进位到底是 0 还是 1，那就两个结果都先算出来。

低 4 位

左下角这个 7483 计算：

A0...A3 + B0...B3 + 0

输出低 4 位结果：

S0...S3

同时产生一个进位：

C4

这个 C4 决定高 4 位应该采用哪一种结果。

高 4 位提前算两遍

右上角有两个 7483，它们都计算高 4 位：

A4...A7 + B4...B7

但是输入进位不同。

输入进位不同	计算	结果
第一个假设低位进位是 0：	A4...A7 + B4...B7 + 0	得到一组结果，记作：R0
第二个假设低位进位是 1：	A4...A7 + B4...B7 + 1	得到另一组结果，记作：R1

然后下面用一个选择器，根据真正的 C4 来选择结果。

---

超前进位加法器

Additionneur à retenue anticipée

Carry Look-Ahead Adder, CLA

1. 超前进位的思想

我们可以提前计算每一级的进位。

然后每一位的和：

S0, S1, S2, S3

再根据对应的进位算出来。

2. 先看一位全加器的进位公式

Ci+1 = Ai·Bi + Ai·Ci + Bi·Ci

推导后得到：

Ci+1 = AiBi + Ci(Ai + Bi)

pi = AiBi

也可以叫 generate。

si = Ai + Bi

表示：如果前面有进位 Ci = 1，当前位是否会把这个进位继续传下去。

所以公式变成：

Ci+1 = pi + Ci·si

含义是：下一位进位 = 当前位自己产生进位 OR 当前位传播前一级进位

C1 怎么算？

C1 = p0 + C0s0
C1 = A0B0 + C0(A0 + B0)

C2 怎么提前算？

C2 = p1 + C1s1

所以把 C1 的公式代进去：

C2 = p1 + (p0 + C0s0)s1

展开：

C2 = p1 + p0s1 + C0s0s1

C3 和 C4 继续展开

C3 = p2 + p1s2 + p0s1s2 + C0s0s1s2
C4 = p3 + C3s3

代入 C3：

C4 = p3 + p2s3 + p1s2s3 + p0s1s2s3 + C0s0s1s2s3

这就是超前进位的关键公式。

3. 这些公式怎么理解？

以 C4 为例：

C4 = p3 + p2s3 + p1s2s3 + p0s1s2s3 + C0s0s1s2s3

4. 为什么它更快？

elles ne tiennent pas compte de la retenue de l'étage précédent

这些表达式不依赖前一级进位的等待传播

准确说，是不需要等前一级进位算出来以后再算下一级，而是用输入位直接提前算出所有进位。

10. 和位 S 怎么算？

每一位的和仍然是：

S0 = A0 ⊕ B0 ⊕ C0
S1 = A1 ⊕ B1 ⊕ C1
S2 = A2 ⊕ B2 ⊕ C2
S3 = A3 ⊕ B3 ⊕ C3

超前进位电路负责快速给出：

C1, C2, C3, C4

然后各位的和就可以快速算出来。