CSE370 Quiz 3 (7 November) Solution

In the carry-lookahead adders you designed for your previous homework assignment, you used carry propagate (P) and generate (G) signals to form the carry equations.  Design a 4-bit adder that instead uses carry propagate (P) and kill (K) signals.  Recall that K = (Ai + Bi)'.  Write equations for the four carrys (C4, C3, C2, and C1) in terms of Pi, Ki, and C0.

Recall that:

generate (Gi) = AiBi, if both Ai and Bi are 1, there the carry-out will be 1 independently of the carry-in;
propagate (Pi) = AiBi' + Ai'Bi, if either Ai or Bi are 1 then a carry-in of 1 will lead to a carry-out of 1 and a carry-in of 0 will lead to a carry-out of 0;
kill (Ki) = Ai'Bi', if both Ai and Bi are 0 then the carry-out will be 0 independently of the carry-in.

Note that Gi + Pi + Ki = 1, also Gi = (Pi + Ki)', Ki = (Gi + Pi)', Pi = (Gi + Ki)'

To write our lookahead equations for the carrys in terms of Pi and Ki, we can simply substitute Gi = (Pi + Ki)' in our original equations:

C1 = G0 + P0C0
C2 = G1 + P1C1 = G1 + P1G0 + P1P0C0
C3 = G2 + P2C2 = G2 + P2G1 + P2P1G0 + P2P1P0C0
C4 = G3 + P3C3 = G3 + P3G2 + P3P2G1 + P3P2P1G0 + P3P2P1P0C0

to yield:

C1 = (P0 + K0)' + P0C0
C2 = (P1 + K1)' + P1C1 = (P1 + K1)' + P1(P0 + K0)' + P1P0C0
C3 = (P2 + K2)' + P2C2 = (P2 + K2)' + P2(P1 + K1)' + P2P1(P0 + K0)' + P2P1P0C0
C4 = (P3 + K3)' + P3C3 = (P3 + K3)' + P3(P2 + K2)' + P3P2(P1 + K1)' + P3P2P1(P0 + K0)' + P3P2P1P0C0

which simplify to:

C1 = P0'K0' + P0C0
C2 = (P1 + K1)' + P1C1 = P1'K1' + P1P0'K0' + P1P0C0
C3 = (P2 + K2)' + P2C2 = P2'K2' + P2P1'K1' + P2P1P0'K0' + P2P1P0C0
C4 = (P3 + K3)' + P3C3 = P3'K3' + P3P2'K2' + P3P2P1'K1' + P3P2P1P0'K0' + P3P2P1P0C0

We could derive the equations directly from the Pis and Kis by thinking about when the carry-out is to be set to 0.

C1' = K0 + P0C0'
C2' = K1 + P1C1' = K1 + P1K0 + P1P0C0'
C3' = K2 + P2C2' = K2 + P2K1 + P2P1K0 + P2P1P0C0'
C4' = K3 + P3C3' = K3 + P3K2 + P3P2K1 + P3P2P1K0 + P3P2P1P0C0'

to which we can apply de Morgan's law and obtain:

C1 = K0'P0' + K0'C0
C2 = K1'P1' + K1'C1 = K1'P1' + K1'K0'P0' + K1'K0'C0
C3 = K2'P2' + K2'C2 = K2'P2' + K2'K1'P1' + K2'K1'K0'P0' + K2'K1'K0'C0
C4 = K3'P3' + K3'C3 = K3'P3' + K3'K2'P2' + K3'K2'K1'P1' + K3'K2'K1'K0'P0' + K3'K2'K1'K0'C0

These might look very different, but they are really very much identical, functionally.  Remember that Ki' = Gi + Pi and that Gi = Ki'Pi'.  If we make these substitutions into the equations above, we obtain:

C1 = G0 + (G0 + P0)C0
C2 = G1 + (G1 + P1)(G0 + P0)P0' + (G1 + P1)(G0 + P0)C0
C3 = G2 + (G2 + P2)(G1 + P1)P1' + (G2 + P2)(G1 + P1)(G0 + P0)P0' + (G2 + P2)(G1 + P1)(G0 + P0)C0
C4 = G3 + (G3 + P3)(G2 + P2)P2' + (G3 + P3)(G2 + P2)(G1 + P1)P1' + (G3 + P3)(G2 + P2)(G1 + P1)(G0 + P0)P0' + (G3 + P3)(G2 + P2)(G1 + P1)(G0 + P0)C0

which can be simplified to:

C1 = G0 + P0C0
C2 = G1 + P1G0P0' + P1(G0 + P0)C0
C3 = G2 + P2G1P1' + P2(G1 + P1)G0P0' + P2(G1 + P1)(G0 + P0)C0
C4 = G3 + P3G2P2' + P3(G2 + P2)G1P1' + P3(G2 + P2)(G1 + P1)G0P0' + P3(G2 + P2)(G1 + P1)(G0 + P0)C0

note
that whenever Gi is true, then Pi will be false, therefore we can eliminate the Pi' literal whenever Gi is in the same term.  In addition, we know that PiGi-1 + PiGi-1Ci-1 = PiGi-1.  This yields:

C1 = G0 + P0C0
C2 = G1 + P1G0 + P1(G0 + P0)C0 = G1 + P1G0 + P1P0C0
C3 = G2 + P2G1 + P2(G1 + P1)G0 + P2(G1 + P1)(G0 + P0)C0 = G2 + P2G1 + P2P1G0 + P2P1(G0 + P0)C0 = G2 + P2G1 + P2P1G0 + P2P1P0C0
C4 = G3 + P3G2 + P3(G2 + P2)G1 + P3(G2 + P2)(G1 + P1)G0 + P3(G2 + P2)(G1 + P1)(G0 + P0)C0 = G3 + P3G2 + P3P2G1 + P3P2P1G0 + P3P2P1P0C0

Which are the same as our original equations using Gi and Pi.

There are many other ways to arrive at equations for the carrys using only propagate and kill. This solution shows two derivations and proves they are in fact equivalent.

Comments to: cse370-webmaster@cs.washington.edu (Last Update: 11/08/03 )