計算機中最基本的算術運算是加法運算，加、減、乘、除運算最終都可以歸結為加法運算。

4.1.1加法器

一、加法器的基本單元

加法器的核心單元是 全加器（Full Adder, FA），而所有加法器都由 半加器（Half Adder, HA） 組合實現。

1. 半加器（HA）

功能：實現兩個1位二進制數相加（不考慮低位進位）。
輸入：A（加數）、B（被加數）
輸出：Sum（和）、Carry（進位）
真值表：

A	B	Sum	Carry
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

邏輯表達式：
$$\begin{gathered} \text{Sum}=A\oplus B \\ \text{Carry}=A?B \end{gathered}$$

電路圖：

2. 全加器（FA）

功能：實現兩個1位二進制數與一個低位進位相加。
輸入：A（加數）、B（被加數）、C_in（低位進位）
輸出：Sum（和）、C_out（進位）
真值表：

A	B	C_in	Sum	C_out
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

邏輯表達式：
$$\begin{gathered} \text{Sum}=A\oplus B\oplus C_{in} \\ {C}_{out}=A?B+(A\oplus B)?C_{in} \end{gathered}$$

電路結構示意圖（由兩個半加器組合）：

二、加法器的類型與工作原理

1. 串行加法器

結構：通過移位寄存器依次處理每一位，每次計算1位。
電路圖：

特性：

• 優點：電路簡單，成本低。
• 缺點：速度極慢，需n個時鐘周期完成n位加法。
• 關鍵問題：進位信號需逐級傳遞（行波進位）。

2. 并行加法器

所有位同時計算，但進位傳遞是關鍵瓶頸。分為兩類：

(1) 串行進位加法器

結構：多個全加器串聯，前級的C_out作為后級的C_in。
電路示意圖：

延遲分析：

• 若每級進位延遲為2t，則n位加法總延遲為2n t。
• 例：32位加法需要64t耗時。

(2) 超前進位加法器（CLA）

核心思想：提前計算各級進位，消除級聯依賴。
進位生成公式：
$$\begin{gathered} C_i=G_i+P_i?C_{i?1} \\ \text{其中：}{G}_i=A_i?B_i(\text{生成進位}) \\ {P}_i=A_i\oplus B_i(\text{傳播進位}) \end{gathered}$$

4位CLA示例：

優點：極快完成所有位的計算，但電路復雜度高。

三、關鍵對比

特性	串行加法器	并行串行進位	超前進位
速度	極慢（O(n)）	較快（O(n)）	極快（O(1)）
硬件復雜度	極簡	中等	復雜
適用場景	嵌入式低功耗設備	通用CPU	高性能計算
典型延遲	32位需64t	32位需64t	4位僅需4t

四、應用實例

現代CPU中，ALU的加法器采用 分組超前進位 結構：

• 16位加法器：4個4位CLA模塊 + 一級CLA控制。
• 延遲：僅需計算組內和組間的并行進位。

通過這種分層設計在速度和復雜度之間取得平衡。

4.1.2進位的產生和傳遞

進位邏輯是加法器設計中影響運算速度的核心部分。

一、進位信號的基本邏輯

全加器的進位輸出由兩部分構成：

1. 本地進位（本地生成）：$G_i=A_i?B_i$
   當 $A_i$ 和 $B_i$ 均為1時，必然產生進位（與低位無關）。
2. 傳遞進位（傳遞依賴）：$P_i=A_i\oplus B_i$
   當 $A_i$ 或 $B_i$ 為1時，低位進位可傳遞至高位。

進位表達式可簡化為：
$$C_i=G_i+P_i?C_{i?1}$$

邏輯電路圖：

二、并行進位技術

1. 完全并行進位（CLA）

所有進位直接由原始輸入和最低位進位 $C_0$ 同時生成，不依賴相鄰進位。
4位CLA的進位表達式：
$$\begin{array}{rl}{C}_1& =G_1+P_1{C}_0\\ C_2& =G_2+P_2{G}_1+P_2{P}_1{C}_0\\ C_3& =G_3+P_3{G}_2+P_3{P}_2{G}_1+P_3{P}_2{P}_1{C}_0\\ C_4& =G_4+P_4\text{(嵌套前3位進位生成邏輯)}\end{array}$$
優點：延遲固定為 $2t_y$（1級$G_i/P_i$計算 +1級邏輯門）。
缺點：硬件復雜度隨位寬指數增長，實際應用中需分組實現。

2. 分組并行進位

兩層設計思想：組內并行（Group Carry Lookahead）+ 組間并行。

• 組內并行（如4位一組）：組內所有進位同時生成。
• 組間并行：通過“組生成函數” $G^{?}$ 和“組傳遞函數” $P^{?}$ 加速跨組進位。

關鍵公式：
$$\begin{array}{rl}\text{組生成函數}{G}^{?}& =G_4+P_4{G}_3+P_4{P}_3{G}_2+P_4{P}_3{P}_2{G}_1\\ \text{組傳遞函數}{P}^{?}& =P_4{P}_3{P}_2{P}_1\\ \text{組進位輸出}{C}_4& =G^{?}+P^{?}{C}_0\end{array}$$

流程圖（16位兩級分組CLA）**：

三、分組方式對比

進位方式	硬件復雜度	最大延遲	適用場景
串行進位	低（簡單級聯）	$O(n)$	低速低成本芯片
單級分組CLA	中等（組內并行）	$O(\sqrt{n})$	通用CPU（如32位處理器）
多級分組CLA	高（多級邏輯）	$O(\log n)$	高性能計算（如GPU）

四、典型應用與優化

1. 示例：16位兩級CLA

• 組內延遲：每組4位的CLA生成 $C_4$ 需 $2t_y$。
• 組間延遲：通過高層CLA生成跨組進位，再傳遞回組內，總延遲 $4t_y$。

關鍵優化點：

• 增量進位計算：組內生成 $G_i$ 和 $P_i$ 后，直接用于高層邏輯，避免重復計算。
• 專用邏輯電路：使用74181（4位ALU）和74182（CLA擴展器）實現快速級聯。

五、總結

• 并行進位核心：通過預先計算進位生成與傳遞關系，消除等待相鄰進位時間。
• 工程權衡：硬件資源與速度的平衡，分組策略需根據芯片制程和應用場景調整。
• 實際應用：現代CPU多采用多級分組（如64位加法器分為4×16位組），配合動態調度優化效率。

4.1.3并行加法器的快速進位

一、快速進位的必要性

傳統串行進位的并行加法器（行波進位）進位延遲與位數成正比（如16位加法器延遲32ty）。快速進位技術通過并行化處理減少進位傳播時間，核心思路是通過邏輯預判提前生成所有進位。

二、并行進位邏輯表達式

對于每位進位 $C_i$ ，通過進位生成函數 $G_i$ 和進位傳遞函數 $P_i$ 遞歸展開：

1. 單級先行進位（完全并行）
   $$\begin{array}{rl}{C}_1& =G_1+P_1{C}_0\\ C_2& =G_2+P_2{G}_1+P_2{P}_1{C}_0\\ C_3& =G_3+P_3{G}_2+P_3{P}_2{G}_1+P_3{P}_2{P}_1{C}_0\\ C_4& =G_4+P_4{C}_3(\text{依此類推})\end{array}$$

2. 硬件實現矛盾：

   • 優點：所有進位僅依賴 $G_i/P_i$ 和 $C_0$，可同時生成。
   • 缺點：公式復雜度隨位數指數增長（n位數需$n$級邏輯門），實際需分組分層處理。
     

三、分組進位技術

1. 單級分組并行進位（組內并行、組間串行）

• 分組示例：將16位分為4組，每組4位。

• 每組生成4位進位：
  

  優點：硬件簡單，延遲降低為 $8ty$（4組 × 2ty/組）。

2. 多級分組并行進位（組間并行）

• 核心邏輯：
  • 每組（如4位）生成組進位生成函數 $G^{?}$ 和組進位傳遞函數 $P^{?}$：
    $$\begin{gathered} G^{?}=G_4+P_4{G}_3+P_4{P}_3{G}_2+P_4{P}_3{P}_2{G}_1 \\ {P}^{?}=P_4{P}_3{P}_2{P}_1 \end{gathered}$$
  • 高層CLA電路計算跨組進位：
    $$C_{4(k+1)}=G_k^{?}+P_k^{?}{C}_{4k}(k=0,1,2,3)$$
• 示例（以16位雙重分組為例）：

- **延遲**：僅 $6ty$（組內2ty + 組間2ty + 二次組內2ty）

四、硬件電路實現

使用 CLA電路生成器（如74182芯片）與 基本加法單元（如74181）：

五、典型對比

類型	硬件復雜度	最大延遲	適用場景
行波進位	低	$32ty$	低速設備
單級分組（4位一組）	中等	$8ty$	通用CPU
多級分組雙	高	$6ty$	高性能計算（GPU）

六、關鍵流程圖

單級分組硬件結構

多級分組信號流

通過上述機制，快速進位技術顯著降低了加法運算的延遲，在現代CPU與高性能計算中廣泛應用。