4.1 基本算术运算的实现

本节介绍计算机中实现算术运算的核心部件——加法器,并深入探讨了提高加法器运算速度的关键技术:并行进位。

核心概念

1. 基本运算部件:全加器 (Full Adder, FA)

定义:全加器是能够对两个二进制位 $A_{i}$ 、 $B_{i}$ 以及来自低位的进位 $C_{i - 1}$ 进行相加的基本逻辑电路。
输出:产生本位和 $S_{i}$ 与向高位的进位 $C_{i}$ 。
逻辑表达式:
- 本位和: $S_{i} = A_{i} \oplus B_{i} \oplus C_{i - 1}$
- 向高位的进位: $C_{i} = A_{i} B_{i} + (A_{i} \oplus B_{i}) C_{i - 1}$

2. 并行加法器与进位传递

并行加法器:由多个全加器组成,可同时对操作数的每一位进行运算。
关键问题:虽然各位是"并行"计算的,但高位的运算必须等待低位的进位信号传来后才能得到最终结果。这种逐位传递进位的过程称为行波进位 (Ripple-Carry),它限制了并行加法器的速度。

3. 快速进位:并行进位链 (Carry-Lookahead)

为了解决行波进位的速度瓶颈,引入了并行进位的思想。

进位产生函数 $G_{i}$ : $G_{i} = A_{i} B_{i}$
- 当 $A_{i}$ 和 $B_{i}$ 都为1时,本位必然产生一个进位,与 $C_{i - 1}$ 无关。
进位传递函数 $P_{i}$ : $P_{i} = A_{i} \oplus B_{i}$
- 当 $A_{i}$ 和 $B_{i}$ 中有一个为1时,本位能否向高位传递进位,取决于低位的进位 $C_{i - 1}$ 。
进位逻辑重写: $C_{i} = G_{i} + P_{i} C_{i - 1}$
并行展开:通过将 $C_{i - 1}$ 逐级展开,可以使每一位的进位 $C_{i}$ 只与初始进位 $C_{0}$ 以及各位的 $G_{i}$ 、 $P_{i}$ 相关。
- $C_{1} = G_{1} + P_{1} C_{0}$
- $C_{2} = G_{2} + P_{2} C_{1} = G_{2} + P_{2} (G_{1} + P_{1} C_{0}) = G_{2} + P_{2} G_{1} + P_{2} P_{1} C_{0}$
- $C_{3} = G_{3} + P_{3} C_{2} = \dots$
- 这种方式使得所有进位可以"同时"产生,因此称为先行进位或并行进位。
分组并行进位 (多级先行进位)
- 原因:当加法器位数很多时(如32位、64位),完全的并行进位逻辑会变得极其复杂。
- 方法:将加法器分成若干小组(如每4位一组)。组内采用并行进位,组间可以采用串行进位(单级先行进位)或更高层次的并行进位(多级先行进位)。
- 组进位函数:定义组的进位产生函数 $G^{*}$ 和传递函数 $P^{*}$ ,实现更高层次的并行进位。

Details

这个结构的核心思想是分层和并行。它将一个大的问题（16位加法）分解成小问题（4位小组的内部计算），并用一个更高层级的电路来并行处理小问题之间的关联（组间进位），从而避免了线性的、漫长的等待。

整个计算过程可以分解为以下三个连续的、内部并行的阶段：

阶段一：所有小组内部同时进行“预计算”

前提：16位的加数A（A₁₆~A₁）、B（B₁₆~B₁）和初始进位C₀都已准备好。

计算位进位函数 (Gᵢ 和 Pᵢ)：在所有四个4位小组（BCLA加法器）的内部，电路会同时为每一位计算两个关键参数：
- 进位产生函数 Gᵢ = Aᵢ · Bᵢ：表示仅根据本位的输入Aᵢ和Bᵢ，是否必然会产生一个进位。
- 进位传递函数 Pᵢ = Aᵢ ⊕ Bᵢ：表示本位是否能将来自低位的进位Cᵢ₋₁传递到高位。这个计算对全部16位是同时发生的。
计算组进位函数 (Gᵢ 和 Pᵢ)**：紧接着，在每个4位小组内部，电路会利用刚刚算出的Gᵢ和Pᵢ，同时计算出代表整个小组特性的两个更高层级的参数：
- 组进位产生函数 Gᵢ*：表示这个小组自身能否产生一个向下一个小组的进位。例如，对于第1小组（位1-4），其组进位产生函数G₁*的逻辑是 G₁* = G₄ + P₄G₃ + P₄P₃G₂ + P₄P₃P₂G₁。这个公式的含义是：只要这四位中的任何一种组合（例如G₄为1，或者G₃为1且P₄为1等）能够独立产生C₄，G₁*就为1。
- 组进位传递函数 Pᵢ*：表示这个小组能否将来自前一组的进位完整地传递过去。例如，第1小组的组进位传递函数P₁*的逻辑是 P₁* = P₄P₃P₂P₁。这个公式的含义是：只有当小组内的每一位都具备传递能力时（所有P都为1），整个小组才能确保将一个输入的进位C₀传递成输出进位C₄。

阶段一小结：

产出：所有16位的Gᵢ和Pᵢ，以及所有4个小组的Gᵢ*和Pᵢ*。
特性：此阶段的所有计算在各个小组内是完全并行的。第4小组计算G₄*和P₄*，与第1小组计算G₁*和P₁*互不依赖，同时进行。
耗时：根据文中所述，这个过程（从A/B输入到G*/P*稳定输出）的电路延迟约为2ty。

阶段二：高层级的“组间进位”并行计算

输入：中间那个独立的“CLA电路”（也叫作进位产生逻辑）接收来自所有4个小组的Gᵢ*和Pᵢ*，以及初始进位C₀。
并行计算组间进位：这个CLA电路的核心作用是并行地计算出每一个小组的最终输出进位。它使用的逻辑与第一阶段的并行进位公式完全相同，但操作对象是“组”而不是“位”。
- C₄ = G₁* + P₁*C₀
- C₈ = G₂* + P₂*C₄ = G₂* + P₂*(G₁* + P₁*C₀)
- C₁₂ = G₃* + P₃*C₈ = ... (表达式会继续展开)
- C₁₆ = G₄* + P₄*C₁₂ = ... (表达式会继续展开)
由于这个CLA电路的输入（所有的Gᵢ*、Pᵢ*和C₀）在阶段一结束后都已准备就绪，所以它能同时产生C₄, C₈, C₁₂, C₁₆这四个关键的组间进位信号。

阶段二小结：

产出：连接各个小组的进位信号C₄, C₈, C₁₂, 以及最终的C₁₆。
特性：这是实现速度飞跃的关键一步。它用一个专门的并行逻辑电路，消除了小组之间C₄ → C₈ → C₁₂的串行等待。
耗时：这个过程的电路延迟也约为2ty。

阶段三：所有小组内部同时进行“最终求和”

输入：
- 每个小组都接收到了来自阶段二的关键进位信号：第2小组得到C₄，第3小组得到C₈，第4小组得到C₁₂。（第1小组使用C₀）。
- 同时，每个小组内部在阶段一计算出的所有Gᵢ和Pᵢ仍然有效。
并行计算组内进位与和：现在，每个小组都拥有了计算自己内部结果所需的所有信息。因此，所有小组同时开始最终的计算。
- 计算内部进位：例如，在第2小组（位5-8）中，电路会利用输入的C₄和本组的G₅-G₈、P₅-P₈，并行计算出C₅, C₆, C₇。
  - C₅ = G₅ + P₅C₄
  - C₆ = G₆ + P₆C₅ = G₆ + P₆(G₅ + P₅C₄)
  - ...
- 计算和 Sᵢ：一旦某一位的进位Cᵢ₋₁确定，该位的和Sᵢ就可以立刻算出： Sᵢ = Pᵢ ⊕ Cᵢ₋₁。这个计算在每个小组内部也是并行展开的。

阶段三小结：

产出：最终的16位和S₁₆~S₁以及进位C₁₆。
特性：所有四个小组同时进行收尾计算，第4小组计算S₁₃~S₁₆，与第2小组计算S₅~S₈互不干扰，并行执行。
耗时：这个过程的电路延迟也约为2ty。

总结

多级先行进位加法器的总延迟是上述三个关键阶段延迟之和（2ty + 2ty + 2ty = 6ty）。因为每一阶段内部的操作都是高度并行的，所以总时间不再与加法器的总位数n成正比，而是一个相对固定的值，从而实现了高速加法。

易考点与难点

难点:并行进位(先行进位)的逻辑表达式推导是本节的核心难点。需要深刻理解进位产生函数 $G_{i}$ 和传递函数 $P_{i}$ 的概念,并掌握如何将串行进位链展开为并行形式。

易考点:
全加器的逻辑表达式是基础,必须掌握。
理解行波进位加法器的主要缺点是速度慢,其延迟与加法器位数 $n$ 成正比。
理解分组并行进位的思想:组内并行,组间串行/并行,是一种在速度和硬件成本之间的折中方案。习题中常出现计算多级先行进位加法器延迟的问题。

4.1 基本算术运算的实现 ​

核心概念 ​

1. 基本运算部件:全加器 (Full Adder, FA) ​

2. 并行加法器与进位传递 ​

3. 快速进位:并行进位链 (Carry-Lookahead) ​

阶段一：所有小组内部同时进行“预计算” ​

阶段二：高层级的“组间进位”并行计算 ​

阶段三：所有小组内部同时进行“最终求和” ​

总结 ​

易考点与难点 ​