Chapter 9 Arithmetic(3)

这一章是很难的，不过我打的就是精锐。😎

Contents of this lecture

英文	中文
1-bit Full Adder	1 位全加器
n-bit Ripple-Carry Adder	n 位波纹进位加法器
Hierarchical Adder	分层加法器
Addition/Subtraction Logic Unit	加减法逻辑单元

1 位全加器

注意记住一个进位，一个本位即可。

• 全加器（Full Adder）

一个全加器电路接受三个输入位，并生成两个输出位，分别是和（sum）和进位输出（carry out）。

输入：$ x_i,y_i, c_i $
输出：$ s_i, c_{i+1} $

全加器电路图：

如图 9.2 (a) 所示，单级全加器的逻辑。

• 逻辑真值表（Logic Truth Table）

$ x_i $	$ y_i $	$ c_i $	$ s_i $	$ c_{i+1} $
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

说明：

$ x_i $, $ y_i $ 是两个加数位，$ c_i $ 是进位输入，$ s_i $ 是和输出，$ c_{i+1} $ 是进位输出。

• 逻辑表达式和电路图

和（sum）的逻辑表达式： $ s_i = x_i y_i c_i $ 其中，$ $ 表示异或（XOR）运算。

• 进位输出（Carry Out）的逻辑表达式

进位输出 $ c_{i+1} $ 的逻辑表达式： $ c_{i+1} = (x_i y_i) + (x_i c_i) + (y_i c_i) $ 其中，$ $ 表示与（AND）运算，$ + $ 表示或（OR）运算。

n 位波纹进位加法器（Ripple-Carry Adder）

这是一种非常简单的加法器，只需要注意一下什么时候会溢出就可以了。

（1）4 位加法器

四个全加器组合在一起形成一个 4 位加法器。
总共有 9 个输入：
- 两个 4 位数，$ A_3 A_2 A_1 A_0 $ 和 $ B_3 B_2 B_1 B_0 $
- 一个初始进位输入，$ C_I $
输出有 5 个：
- 一个 4 位和，$ S_3 S_2 S_1 S_0 $
- 一个进位输出，$ C_O $

（2）4 位加法器

如上所述，4 位加法器通过将四个全加器连接在一起构成。每个全加器负责处理一位数相加，同时传递进位到下一个加法器。

（3）n 位波纹进位加法器的结构

n 位波纹进位加法器是通过将 n 个全加器连接在一起组成的，基本上是每个加法器的进位输出作为下一个加法器的进位输入。

输入：
$ X = x_{n-1} , x_{n-2} , , x_1 , x_0 $
$ Y = y_{n-1} , y_{n-2} , , y_1 , y_0 $
进位输入：$ C_0 $

输出：
和：$ S = s_{n-1} , s_{n-2} , , s_1 , s_0 $
进位输出：$ C_n $

（4）溢出检测

溢出的检测条件是根据最高位的进位和两个数的符号位来确定的。

溢出公式：
$ = C_{n-1} (c_{n-1}) $

同时结合给定的溢出真值表，我们可以推导出溢出的表达式。

溢出真值表

$ x_{n-1} $	$ y_{n-1} $	$ s_{n-1} $	Overflow
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	0

根据溢出真值表，溢出发生在以下两种情况下：

$ x_{n-1} = 0 $, $ y_{n-1} = 0 $, $ s_{n-1} = 1 $
$ x_{n-1} = 1 $, $ y_{n-1} = 1 $, $ s_{n-1} = 0 $

$ = (x_{n-1} y_{n-1} ) + ( s_{n-1}) $

其中：

$ $ 表示 $ s_{n-1} $ 的取反。
$ x_{n-1} y_{n-1} $ 对应溢出发生在 $ x_{n-1} = 1 $, $ y_{n-1} = 1 $, $ s_{n-1} = 0 $ 时。
$ s_{n-1} $ 对应溢出发生在 $ x_{n-1} = 0 $, $ y_{n-1} = 0 $, $ s_{n-1} = 1 $ 时。

精华：

n 位波纹进位加法器通过多个全加器依次计算每个位的和，并且进位由一个加法器传递给下一个加法器。
该加法器结构简单，但由于每个进位都要经过每个加法器，因此速度较慢，尤其是在处理大规模数字时。
溢出通过检测最高位的进位输出与输入符号位的关系来确定。

分层加法器 (Hierarchical Adder)

使用 4 位加法器设计 8 位加法器

例子图示
- 输入：两个 4 位加数 $ A_3A_2A_1A_0 $ 和 $ B_3B_2B_1B_0 $
- 输入：进位输入（Carry-in，CI）
- 输出：4 位和 $ S_3S_2S_1S_0 $ 和进位输出（Carry-out，CO）

使用 n 位加法器设计一个 kn 位加法器

例子图示
- 通过级联多个 n 位加法器来构建一个 k 个 n 位加法器的结构。
- 每个加法器的输出进位作为下一个加法器的进位输入，直到最终得到计算结果。

精华

4 位加法器：将两个 4 位的加数相加，得到一个 4 位的和和一个进位输出。
分层结构：通过级联多个 n 位加法器，可以扩展到更大的位数，如设计 8 位或更大的加法器。

门延迟 (Gate Delays)

门延迟定义

每个逻辑门在输入信号到输出信号正确出现之间都会有一个小的时间延迟，这段时间称为“门延迟”（Gate Delay）。
实际上，计算门延迟的方法是非常详细的，有时会很复杂，但在本课程中，我们假设所有门的延迟是相同的，并且是一个小的常数。

使用时序图展示门延迟

时序图（Timing Diagram）可以图形化地展示门延迟的过程。
- 在时序图中，输入信号变化与输出信号响应的时间间隔通过图形显示，可以清楚地看到每个门的延迟对整个电路的影响。

精华

门延迟：每个逻辑门的输入信号到输出信号之间的时间差。
时序图：用于图形化表示门延迟和信号传播过程的工具。

滚动进位加法器中的传播延迟 (Propagation Delays in the Ripple Carry Adder)

这里说明了滚动进位加法器的缺点，就是太慢了，后面就引入了并行进位加法器了。

至于两个延迟就是结合上面推导出来的公式得来的。

逻辑门延迟

通过一组逻辑门的延迟取决于用于制造这些门的集成电路电子技术，以及从输入到输出的路径中逻辑门的数量。
通过任何由逻辑门构成的组合逻辑网络的延迟，是通过将网络中最长信号传播路径上的逻辑门延迟加总来决定的。

滚动进位加法器中的传播延迟

在 n 位滚动进位加法器中，最长的传播路径是从输入的最低有效位（LSB） $x_0, y_0, c_0$ 到输出的最高有效位（MSB） $c_n$ 和 $s_{n-1}$。
也就是说，信号从 LSB 到 MSB 的传播延迟是整个加法器的传播延迟。

假设

假设与逻辑门相关的延迟是常数 T，适用于与、或、异或等所有逻辑门。

滚动进位加法器的延迟示意

对于一个全加器（Full Adder，FA），每个加法器的延迟如下：
- $ s_i $ 的延迟为 T。
- $ c_{i+1} $ 的延迟为 2T。
- $ c_i $ 的延迟为 T。

精华

传播延迟：通过由逻辑门构成的网络，信号传播所需的时间。
滚动进位加法器：信号从 LSB 到 MSB 的传播延迟是加法器的主要延迟来源，延迟的大小与逻辑门的数量和类型密切相关。

加法/减法逻辑单元 (Addition/Subtraction Logic Unit)

加法/减法逻辑单元的组织结构

Add/Sub 控制：用于选择执行加法或减法操作。
- 当 Add/Sub 控制 = 0 时，进位输入 $c_0 = 0$，执行加法操作。
- 当 Add/Sub 控制 = 1 时，进位输入 $c_0 = 1$，执行减法操作。
XOR 闭合：用于执行减法操作时的符号位变换。
- 当 控制为0 时，$ Y $ 不变。
- 当 控制为1 时，$ Y $ 会被进行按位异或（XOR）运算，改变其符号。
加法/减法控制：用来决定是否执行加法还是减法，控制信号直接影响运算的方式。
加法器：使用 n 位加法器（n-bit adder）来执行加法操作，输入包括 $ x_{n-1} x_0 $ 和 $ y_{n-1} y_0 $，输出为和 $ s_{n-1} s_0 $ 及进位输出 $ c_n $。

溢出检测

可以通过添加 XOR 门 来检测溢出。
溢出：当进行加法或减法时，如果结果无法被表示（超出了位数的范围），就会发生溢出。

延迟

所有和位（sum bits）在 2n 个门延迟内都可以得到，包括通过对 $ Y $ 输入执行 XOR 运算的延迟。

精华

加法/减法逻辑单元：通过控制信号选择加法或减法操作。
XOR 门：用于修改输入 $ Y $ 来实现减法，并能检测溢出。
延迟：所有和位的计算需要经过 2n 个逻辑门的延迟，包括 XOR 门的延迟。

小测验（Quiz）

问题 1:

在一个 1 位全加器中，$ s_i $ 的表达式是？

A. $ x_i + y_i $
B. $ x_i y_i $
C. $ x_i y_i $
D. $ x_i y_i c_i $

答案: D. $ x_i y_i c_i $

解释:
在 1 位全加器中，和 $ s_i $ 是通过按位异或运算得到的，它是输入 $ x_i $、$ y_i $ 和进位 $ c_i $ 的异或结果。因此，正确答案是 $ x_i y_i c_i $。

问题 2:

在一个 1 位全加器中，$ c_{i+1} $ 的表达式是？

A. $ x_i + y_i + c_i $
B. $ x_i y_i c_i $
C. $ x_i y_i + x_i c_i + y_i c_i $
D. $ x_i y_i c_i $

答案: C. $ x_i y_i + x_i c_i + y_i c_i $

解释:
进位输出 $ c_{i+1} $ 是由以下条件判断的：当 $ x_i $ 和 $ y_i $ 都为 1 时，进位发生；或者 $ x_i $ 和进位 $ c_i $ 或 $ y_i $ 和进位 $ c_i $ 发生进位时。因此，正确答案是 $ x_i y_i + x_i c_i + y_i c_i $。