Carry-Lookahead Adder

logic-circuits

Definition

Carry-Lookahead Adder

The problem of ripple-carry adders is that they need to run the entire ripple (chain) sequentially since every column depends on its predecessor.

The idea of carry-lookahead adders is to subdivide the columns into blocks and precompute certain values in parallel. The previous column’s information is still needed, however, more can be done in parallel.

Carry-lookahead adders include two new signal bits:

1. Generate $G_i=A_i\cdot B_i$. The $i$th column is said to generate a carry if it produces a carry out independent of the carry in.
2. Propagate $P_i=A_i+B_i$. The $i$th column is said to propagate a carry if it produces a carry out whenever there is a carry in. The $i$th column will propagate a carry in, $C_{i-1}$, if either $A_i$ or $B_i$ is $1$.

Thus, the $i$th column of an adder will generate a carry out $C_i$ if it either generates a carry, $G_i$ or propagates a carry in $P_i\cdot C_{i-1}$:

$$C_i=A_i\cdot B_i+(A_i+B_i)\cdot C_{i-1}=G_i+P_i\cdot C_{i-1}$$

The delay of a carry-lookahead adder divided into $k$-bit blocks has a delay:

$$t_{CLA}=t_{pg}+t_{p{g}_{block}}+\left(\frac{N}{k}-1\right)\cdot t_{AND\_OR}+k\cdot t_{FA}$$

where $t_{pg}$ is the delay of the column propagate and generate gates to generate $P_i,G_i$, $t_{pg\_block}$ is the delay to find the block propagate and generate signals $P_{i:j},G_{i:j}$ for a $k$-bit block, and $t_{AND\_OR}$ is the delay from $C_{in}$ to $C_{out}$ through the final AND/OR logic of the $k$-bit CLA block. ¹

Blocks

The generate and propagate definitions extend to multiple-bit blocks. A block is said to generate a carry if it produces a carry out independent of the carry in to the block. The block is said to propagate a carry if it produces a carry out whenever there is a carry in to the block. We defined $1$-bit block generate and propagate signals, $G_{i:j}$ and $P_{i:j}$, for block spanning columns $i$ through $j$.

A block generates a carry if the most significant column generates a carry, or if the previous column previous column generated a carry and the most significant column propagates it, and so forth.

For example, the generate logic for a block spanning columns 3 through 0 is:

$$G_{3:0}=G_3+P_3\cdot (G_2+P_2\cdot (G_1+P_1\cdot G_0))$$

A block propagates a carry if all the columns in the block propagate the carry. For example, the propagate logic for a block spanning columns 3 through 0 is:

$$P_{3:0}=P_3\cdot P_2\cdot P_1\cdot P_0$$

Using the block $i:j$ generate and propagate signals, we can quickly compute the carry out of the block $C_i$ using the carry in tot he block $C_{j-1}$:

$$C_i=G_{i:j}+P_{i:j}\cdot C_{i-1}$$

¹

Footnotes

1. Digital Design and Computer Architecture - RISC-V Edition ↩ ↩²