Chapter 9 Arithmetic(4)
Chapter 9 Arithmetic(4)
这一章是很难的，不过我打的就是精锐。😎
Contents of this lecture
| 英文内容 | 中文内容 |
|---|---|
| Drawback of n-bit Ripple-Carry Adder | n 位 Ripple-Carry 加法器的缺点 |
| Carry-Lookahead Addition | 进位提前加法 |
| 4-bit Carry-Lookahead Adder | 4 位进位提前加法器 |
n-bit Ripple-Carry Adder中的门延迟
注意看图，进位需要的延迟会更多一点。
- n-bit Ripple Carry Adder 延迟分析
- 输出 \(s_{n-1}\) 的延迟: \(s_{n-1}\) 的延迟为 \(2(n-1)T + T = (2n-1)T\)
- 输出 \(c_n\) 的延迟: \(c_n\) 的延迟为 \(2(n-1)T + 2T = (2n)T\)
这里，\(T\) 表示单个逻辑门的延迟。
n-bit Ripple-Carry Adder 的缺点
- 缺点
- 在输出 \(s_0\) 到 \(s_{n-1}\) 和 \(c_n\) 时，可能会有过多的延迟。
- \(s_{n-1}\) 的延迟为 \((2n-1)T\)
- \(c_n\) 的延迟为 \(2nT\)
- 解决方案
- 使用尽可能最快的电子技术来实现 ripple-carry 逻辑设计或其变种。
- 使用增强的逻辑门网络结构。
超前进位加法器（Carry-Lookahead Addition）
1. 生成函数与传播函数
- 求和公式:
$ s_i = x_i y_i c_i $ - 进位公式:
$ c_{i+1} = G_i + P_i c_i $
其中：- 生成函数（Generate Function）:
$ G_i = x_i y_i $ - 传播函数（Propagate Function）:
$ P_i = x_i + y_i $
- 生成函数（Generate Function）:
2. 更简化的单位级电路
- 进位公式重新表达：
$ c_{i+1} = G_i + P_i c_i $
这表明当前位的进位仅由生成函数和传播函数决定。
3. 逻辑函数扩展
多位进位公式： $ c_1 = G_0 + P_0 c_0 $ $ c_2 = G_1 + P_1 G_0 + P_1 P_0 c_0 $ $ c_3 = G_2 + P_2 G_1 + P_2 P_1 G_0 + P_2 P_1 P_0 c_0 $ 类推至 \(c_{n-1}\)，可用递归计算。
求和公式： $ s_i = x_i y_i c_i $
4. n 位 CLA 的延迟
- 所有进位信号延迟: 输入信号 \(X, Y, c_0\) 应用后 3
个逻辑门延迟 可以得到所有进位位。
- 所有和位延迟: 输入信号 \(X, Y, c_0\) 应用后 4 个逻辑门延迟 可以得到所有和位。
CLA 的设计通过减少进位链的延迟显著提升了加法器性能，克服了 Ripple-Carry Adder 的主要缺点。
4 位超前进位加法器（4-bit Carry-Lookahead Adder）
1. 4 位超前进位加法器的逻辑函数
4 位超前进位加法器的进位和和位的计算公式如下：
进位信号计算
$ c_1 = G_0 + P_0 c_0 $ $ c_2 = G_1 + P_1 G_0 + P_1 P_0 c_0 $ $ c_3 =
G_2 + P_2 G_1 + P_2 P_1 G_0 + P_2 P_1 P_0 c_0 $ $ c_4 = G_3 + P_3 G_2 +
P_3 P_2 G_1 + P_3 P_2 P_1 G_0 + P_3 P_2 P_1 P_0 c_0 $
- 生成函数：\(G_i = x_i
\cdot y_i\)
- 传播函数：\(P_i = x_i + y_i\)
和位信号计算
$ s_i = x_i y_i c_i, , i = 0,1,2,3 $
2. 4 位超前进位加法器电路图
4 位超前进位加法器通过 \(G_i\) 和 \(P_i\) 的逻辑组合计算所有进位 \(c_1\) 至 \(c_4\)，随后根据 \(c_i\) 计算各位的和 \(s_i\)。
- 电路中采用层级式设计，将生成函数和传播函数的逻辑组合集中处理，以减少延迟。
- 超前进位逻辑使高位进位无需依赖低位的逐次传递，从而显著提升速度。
3. 延迟比较
| 加法器类型 | 进位延迟 $ c_n $ | 和位延迟 $ s_i $ | 总延迟（进位+和位） |
|---|---|---|---|
| 4 位 Ripple-Carry Adder | $ 8T $ | $ 7T $ | $ 8T + 7T = 15T $ |
| 4 位 Carry-Lookahead Adder | $ 3T $ | $ 4T $ | $ 3T + 4T = 7T $ |
- Ripple-Carry Adder（逐位进位加法器）
- 进位延迟：需要依次通过 4 个完整加法器，每个加法器的进位计算需 2
个逻辑门延迟，因此进位延迟为 \(2 \cdot 4 =
8T\)。
- 和位延迟：最后一位和信号需等待进位信号，延迟为 \(7T\)。
- 进位延迟：需要依次通过 4 个完整加法器，每个加法器的进位计算需 2
个逻辑门延迟，因此进位延迟为 \(2 \cdot 4 =
8T\)。
- Carry-Lookahead Adder（超前进位加法器）
- 进位延迟：超前进位逻辑通过 3 个逻辑门延迟计算所有进位信号 \(c_1, c_2, c_3, c_4\)。
- 和位延迟：在进位信号计算完成后，再通过 1 个 XOR 门延迟得到和信号，总延迟为 \(4T\)。
- 进位延迟：超前进位逻辑通过 3 个逻辑门延迟计算所有进位信号 \(c_1, c_2, c_3, c_4\)。
结论：
超前进位加法器通过并行计算进位，显著减少延迟，对高性能需求场景更加适用。
构建更长的超前进位加法器（Build Longer Carry-Lookahead Adder）
注意延迟，两种加法器各自的延迟都需要会推理。
第一种加法器很容易记住，一个是\((2*n-1)\)，一个是\(2*n\)。
第二个注意一开始是3，后面加的是2，因为已经预处理好了一开始需要的数据。
1. 4 位超前进位加法器的局限性
- 局限性
4 位超前进位加法器的设计不能直接扩展至更大的位数，因为随着位数的增加，逻辑门的输入数量（Fan-In）和输出驱动数量（Fan-Out）会迅速增加，导致延迟显著提升。
2. Fan-In 和 Fan-Out 的限制
- 定义
- Fan-In: 一个逻辑门的输入端数量。
- Fan-Out: 一个逻辑门输出端驱动的输入端数量。
- Fan-In: 一个逻辑门的输入端数量。
- 限制影响
- 实际电路中，过大的 Fan-In 和 Fan-Out
会增加信号传播延迟，降低电路速度。
- 举例：计算 \(c_{i+1}\) 时，最后一个 AND 门和 OR 门的 Fan-In 为 \(i+2\)，即信号需要逐级传递，延迟增加。
- 实际电路中，过大的 Fan-In 和 Fan-Out
会增加信号传播延迟，降低电路速度。
3. 使用 4 位加法器构建 32 位超前进位加法器
- 设计结构
将 8 个 4 位超前进位加法器级联，以实现 32 位加法器：- 低位 4 位加法器计算前 4 位的和位和进位信号。
- 高位加法器利用前级输出的进位信号计算更高位的和位与进位信号。
- 低位 4 位加法器计算前 4 位的和位和进位信号。
- 级联连接
- \(c_0\) 是初始进位，\(c_4, c_8, ..., c_{32}\)
是中间进位信号。
- 每个 4 位加法器的输入依次是 \(x_{i:i+3}\) 和 \(y_{i:i+3}\)，输出为 \(s_{i:i+3}\) 和进位 \(c_{i+4}\)。
- \(c_0\) 是初始进位，\(c_4, c_8, ..., c_{32}\)
是中间进位信号。
4. 32 位超前进位加法器的延迟计算
- 高位 4 位加法器的关键延迟
- \(c_{28}\)
的延迟:
由低位向高位逐步传播，延迟为 \(6 \times 2T + 3T = 15T\)。
- \(c_{32}\)
的延迟:
在 \(c_{28}\) 基础上再增加 \(2T\)，即 \(15T + 2T = 17T\)。
- \(s_{31}\)
的延迟:
和位需要额外 1 个逻辑门延迟，总计 \(17T + T = 18T\)。
- \(c_{28}\)
的延迟:
- Ripple-Carry Adder 的对比
- \(s_{31}\) 的延迟：\((2n-1)T = 63T\)。
- \(c_{32}\) 的延迟：\(2nT = 64T\)。
- \(s_{31}\) 的延迟：\((2n-1)T = 63T\)。
总结
通过将 4 位超前进位加法器级联，可以显著降低延迟：
- 超前进位加法器：\(s_{31} =
18T\)，\(c_{32} = 17T\)。
- Ripple-Carry Adder：\(s_{31} =
63T\)，\(c_{32} = 64T\)。
超前进位加法器的级联设计在大位宽加法运算中显著提升了速度。
测验 1
1. 题目 1
一个 16 位 Ripple-Carry Adder
- 问题：16 位 Ripple-Carry Adder 用于对两个数 \(X(x_{15}x_{14}...x_1x_0)\) 和 \(Y(y_{15}y_{14}...y_1y_0)\) 相加，生成 16
位和 \(S(s_{15}s_{14}...s_1s_0)\)。计算
\(s_{13}\)
所需的逻辑门延迟是多少？
- 选项：
- A. 8
- B. 25
- C. 27
- D. 31
- A. 8
答案：B. 25
解释：
- \(s_{13}\) 的延迟需在此基础上加上 1 个逻辑门延迟，即 \(2*13-12 = 25T\)。
2. 题目 2
超前进位加法器的优点
- 问题：超前进位加法器的优势是什么？
- 选项：
- A. 优化加法器结构
- B. 节省硬件部件
- C. 增强加法器结构
- D. 加速进位的生成
- A. 优化加法器结构
答案：D. 加速进位的生成
解释：
- 超前进位加法器（Carry-Lookahead
Adder）的核心思想是通过并行计算快速生成进位，从而降低延迟。
- 相比 Ripple-Carry Adder，CLA 的主要优势是
显著加快了进位信号的生成速度，从而减少整体计算延迟。
- 选项 D 准确描述了其主要优势。
总结
- Ripple-Carry Adder
的延迟：依赖进位的逐位传播，延迟较高。
- Carry-Lookahead Adder 的优势：通过并行生成进位信号，极大缩短了延迟。
测验 2
1. 题目 1
在超前进位加法器中，哪一个表达式是阶段 \(i\) 的传播函数 \(P_i\)？
- 选项：
- A. \(x_i + y_i\)
- B. \(x_i \oplus y_i\)
- C. \(x_i y_i\)
- D. \(x_i \oplus y_i \oplus c_i\)
- A. \(x_i + y_i\)
答案：A. \(x_i +
y_i\)
解释：
- 传播函数 \(P_i\)
的定义是表示进位是否会从当前位传播到下一位。
- 数学表达式为 \(P_i = x_i + y_i\)，表示如果 \(x_i\) 或 \(y_i\) 任意一个为 1，则可能产生进位传播。
2. 题目 2
在超前进位加法器中，哪一个表达式是阶段 \(i\) 的生成函数 \(G_i\)？
- 选项：
- A. \(x_i + y_i\)
- B. \(x_i \oplus y_i\)
- C. \(x_i y_i\)
- D. \(x_i \oplus y_i \oplus c_i\)
- A. \(x_i + y_i\)
答案：C. \(x_i
y_i\)
解释：
- 生成函数 \(G_i\)
的定义是表示当前位是否能够单独生成进位。
- 数学表达式为 \(G_i = x_i y_i\)，表示当 \(x_i\) 和 \(y_i\) 都为 1 时，必然会生成一个进位。
3. 题目 3
判断题：在 4 位超前进位加法器中，所有进位可以在输入信号 \(X, Y\) 和 \(c_0\) 应用后 3 个逻辑门延迟内获得。
答案：True（正确）
解释：
- 超前进位加法器（Carry-Lookahead
Adder）的关键特性是通过并行计算进位信号。
- 根据设计，所有进位可以在输入信号应用后 3 个逻辑门延迟 内完成计算，这显著减少了 Ripple-Carry Adder 中串行进位传播的延迟。
精华
- 传播函数 \(P_i = x_i +
y_i\) 表示当前位是否允许进位的传播。
- 生成函数 \(G_i = x_i
y_i\) 表示当前位是否能够单独生成进位。
- 4 位 CLA 延迟优势：所有进位信号可以在 3 个逻辑门延迟 内完成计算。
