carry_lookahead_adder.md

For the calculation of the sum of integers $A, B$ in $N$-decimal, we divide the $(i-1):k$-digit part into $(i-1):j$-digit and $(j-1):k$-digit parts and consider whether the carry-over occurs for each. $(i \gt j \gt k)$

First, the integers $A, B$ are divided into $(i-1):j$ digits in $N$-decimal, and the values $A_{i-1:j}, B_{i-1:j}$ are added to determine whether carry-forward occurs for the digits above the interval, which are classified into three states as follows.

• $A_{i-1:j}+B_{i-1:j} \lt N^{i-j}-1$ ; None
• $A_{i-1:j}+B_{i-1:j} = N^{i-j}-1$ ; Propagate
• $A_{i-1:j}+B_{i-1:j} \gt N^{i-j}-1$ ; Generate

Example for a decimal number:

• $12345 + 12345 = 24690 \lt 99999$ ; None
• $12345 + 87654 = 99999 = 99999$ ; Propagate
• $12345 + 99999 = 112344 \gt 99999$ ; Generate

Consider the same for the $(i-1):k$ digits and the $(j-1):k$ digits. Then, we find the following relationship.

$(i-1):j$ (Upper)	$(j-1):k$ (Lower)	$(i-1):k$ (Combined)
None	None	None
None	Propagate	None
None	Generate	None
Propagate	None	None
Propagate	Propagate	Propagate
Propagate	Generate	Generate
Generate	None	Generate
Generate	Propagate	Generate
Generate	Generate	Generate

Example: $(i-1):j$ digits and $(j-1):k$ digits are both Propagate

• $A_{i-1:j} + B_{i-1:j} = N^{i-j}-1$ ; Propagate
• $A_{j-1:k} + B_{j-1:k} = N^{j-k}-1$ ; Propagate
• $A_{i-1:k} + B_{i-1:k} = (N^{i-j}-1)\cdot N^{j-k} + (N^{j-k}-1) = N^{i-k} - 1$ ; Propagate

To represent these states, we introduce the signals $G$ and $P$.

$G$	$P$	status
0	0	None
0	1	Propagate
1	0	Generate
1	1	Generate

If we are interested in the state of the integer $r$-th binary digit, the signal $G$ can be generated as follows

• $G_{r:r} = G_r = A_r \land B_r$

The signal $P$ can be generated in two ways as follows. If $G_r=1$, the former will result in $P_r=1$ and the latter will result in $P_r=0$.

• $P_{r:r} = P_r = A_r \lor B_r$
• $P_{r:r} = P_r = A_r \oplus B_r$

Note:

• $\land$ : and
• $\lor$ : or
• $\oplus$ : xor

The process of combining the signal $G$ for two adjacent sections can be described as follows

• $G_{i-1:k} = G_{i-1:j} \lor (P_{i-1:j} \land G_{j-1:k})$

The process of synthesizing the signal $P$ can also be described in two ways as follows. In most cases, the latter method is likely to be used.

• $P_{i-1:k} = G_{i-1:j} \lor (P_{i-1:j} \land P_{j-1:k})$
• $P_{i-1:k} = P_{i-1:j} \land P_{j-1:k}$