2024-05-13

📅 Monday, May 13th, 2024

Honesty is the best policy.

— Benjamin Franklin

ECS154A Lecture: carry-lookahead adder (CLA)

Presentation of the CLA in the textbook: The purpose of the carry-lookahead adder is to do the adding simultaneously before the carry bit is available from previous adders (or really, CLA blocks).

$$\begin{array}{rl}{G}_i& =A_i{B}_i\\ P_i& =A_i\oplus B_i\end{array}$$

Only generate a carry if both $A_i$ and $B_i$ are set (1 + 1 = 0 with a carry). Only propagate a carry from previous CLA block if $A_i$ and $B_i$ are not the same (0 + 0 with carry = 1 without carry; 1 + 1 with carry = 1 with carry, but the carry is generated not propagated).

We want to reuse these two results we already have in $S_i$ and $C_i$

$$\begin{array}{rl}{S}_i& =A_i\oplus B_i\oplus C_{i-1}=P_i\oplus C_{i-1}\\ C_i& =\left(A_i\oplus B_i\right)C_{i-1}+A_i=A_i+P_i{C}_{i-1}\end{array}$$

Now, instead of computing $C_i$ one after the other, we can try to “parallelize” the computation at the cost of exponentially more gates:

$$\begin{array}{rl}{C}_0& =G_0+P_0{C}_{-1}\\ C_1& =G_1+P_1{C}_0=G_1+P_1\left(G_0+P_0{C}_{-1}\right)\\ & =G_1+P_1{G}_0+P_1{P}_0{C}_{-1}\\ C_2& =G_2+P_2{C}_1\\ & =G_2+P_2\left(G_1+P_1{G}_0+P_1{P}_0{C}_{-1}\right)\\ & =G_2+P_2{G}_1+P_2{P}_1{G}_0+P_2{P}_1{P}_0{C}_{-1}\end{array}$$

The drawing below is incomplete (Posnett didn't complete it in class) and I'm not bothered to do it.

Arithmetic right shifts shift in the same bit values as the original highest bit.