加法器

单位加法

单位加法（single bit addition）。

半加器（half adder）处理无低位进位的情况，常用在最低位上。

• 和 $S=A\oplus B$
• 向高位进位（carry out）$C_{out}=AB$

全加器（full adder）

• $S=A\oplus B\oplus C$
• $C_{out}=AB+BC+AC$

PGK。

• 产生进位 generate：$G=AB$，若 $G=1$，$C_{out}=1$，与 $C$ 无关
• 传播进位 propagate：$P=A\oplus B$，若 $P=1$，此时 $C_{out}=C$
• 阻断进位 kill：$K=\overline{A}\cdot\overline{B}$，若 $K=1$，$C_{out}=0$，与 $C$ 无关

grouped PG。

base case：

• $G_{0:0}=G_0=C_{in}, P_{0:0}=P_{0}=0$
• $G_{i:i}=A_iB_i, P_{i:i}=A_i\oplus B_i$

一个区间 DP 形式的转移（LSB 在最右边）： $G_{i:j}=G_{i:k}+P_{i:k}G_{k-1:j}, P_{i:j}=P_{i:k}P_{k-1:j}$

最终的和是 $S_i=P_i\oplus C_i=P_i\oplus G_{i-1:0}$

行波进位加法器

行波进位加法器（Carry-Ripple Adder, CPA）。

根据递推公式 $C_i=G_{i-1:0}=G_{i-1}+P_{i-1}G_{i-2:0}=G_{i-1}+P_{i-1}C_{i-1}$，计算每一位的进位 $C_i$，最后的 $S_i=C_i\oplus A_i\oplus B_i$。

使用分层全加器（cascade full adders）实现，critical path 长度为 $n$。

超前进位加法器

超前进位加法器（Carry-Lookahead Adder，CLA）。

引入高价单元（high-valency cell），分组并行计算多位的 grouped PG。

$m$-valency cell CLA 计算 $n$ 位加法的 critical path 长度为 $n/m$。

进位选择加法器

进位选择加法器（Carry-Select Adder，CSA）。

CPA/CLA 加和的过程中，高位的计算依赖低位的进位。但进位只可能有两种 0/1，所以每组预先计算好两种情况下的结果，等到低位的进位传上来的时候直接通过 MUX 选择正确的和与进位，能够节省一些时间。

进位递增加法器

进位递增加法器（Carry-Increment Adder，CIA？），对 CSA 的改进。

CSA 对低位进位为 0/1 的情况各自计算一遍结果，会重复算 $P_i=A_i\oplus B_i,G_i=A_iB_i$。

CIA 则只预先计算 $C_{in}=0$ 的情况，如果低位进位为 1，就用累加器（increment）在结果上加 1。比起 CSA 速度更快，面积更小。

还可以采用 variable group size：低位组小，高位组大，从而平衡进位到达的时间与组内计算的时间。

树形加法器

树形加法器（tree adders）很好理解，就是递归的超前进位（recursive lookahead），组织成树结构。那么 $m$-valency cell 树形加法器的 critical path 长度为 $\log_m n$。

对于 $n$ 位加法，理想的树深度为 $L=\log_2 n$，扇出不超过 2，且每两层之间最多只有一条布线轨道。

按照三个指标给不同的加法器分类（tree adder taxonomy）：

• $l=$ 逻辑级数（logic levels）$-L$
• $f=\log_2 ($扇出数$-1)$
• $t=\log_2$ 布线轨道数（wiring tracks）

三个经典的树形加法器均满足 $l+f+t=L-1$：逻辑层数，扇出数与布线轨道数三者需要做 balance。关于如何从图中数出布线轨道数：一条垂直的线在某两相邻层间穿过的布线数的最大值。