单位加法
单位加法（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。关于如何从图中数出布线轨道数：一条垂直的线在