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.
C
1' = K
0 + P
0C
0'
C
2' = K
1 + P
1C
1' = K
1
+ P
1K
0 + P
1P
0C
0'
C
3' = K
2 + P
2C
2' = K
2
+ P
2K
1 + P
2P
1K
0
+ P
2P
1P
0C
0'
C
4' = K
3 + P
3C
3' = K
3
+ P
3K
2 + P
3P
2K
1
+ P
3P
2P
1K
0 + P
3P
2P
1P
0C
0'
to which we can apply de Morgan's law and obtain:
C
1 = K
0'P
0' + K
0'C
0
C
2 = K
1'P
1' + K
1'C
1
= K
1'P
1' + K
1'K
0'P
0'
+ K
1'K
0'C
0
C
3 = K
2'P
2' + K
2'C
2
= K
2'P
2' + K
2'K
1'P
1'
+ K
2'K
1'K
0'P
0' + K
2'K
1'K
0'C
0
C
4 = K
3'P
3' + K
3'C
3
= K
3'P
3' + K
3'K
2'P
2'
+ K
3'K
2'K
1'P
1' + K
3'K
2'K
1'K
0'P
0'
+ K
3'K
2'K
1'K
0'C
0
These might look very different, but they are
really very much identical, functionally. Remember that K
i' = G
i
+ P
i and that G
i = K
i'P
i'.
If we make these substitutions into the equations above, we obtain:
C
1 = G
0 + (G
0 + P
0)C
0
C
2 = G
1 + (G
1 + P
1)(G
0
+ P
0)P
0' + (G
1 + P
1)(G
0
+ P
0)C
0
C
3 = G
2 + (G
2 + P
2)(G
1
+ P
1)P
1' + (G
2 + P
2)(G
1
+ P
1)(G
0 + P
0)P
0' + (G
2
+ P
2)(G
1 + P
1)(G
0 + P
0)C
0
C
4 = G
3 + (G
3 + P
3)(G
2
+ P
2)P
2' + (G
3 + P
3)(G
2
+ P
2)(G
1 + P
1)P
1' + (G
3
+ P
3)(G
2 + P
2)(G
1 + P
1)(G
0
+ P
0)P
0' + (G
3 + P
3)(G
2
+ P
2)(G
1 + P
1)(G
0 + P
0)C
0
which can be simplified to:
C
1 = G
0 + P
0C
0
C
2 = G
1 + P
1G
0P
0'
+ P
1(G
0 + P
0)C
0
C
3 = G
2 + P
2G
1P
1'
+ P
2(G
1 + P
1)G
0P
0'
+ P
2(G
1 + P
1)(G
0 + P
0)C
0
C
4 = G
3 + P
3G
2P
2'
+ P
3(G
2 + P
2)G
1P
1'
+ P
3(G
2 + P
2)(G
1 + P
1)G
0P
0'
+ P
3(G
2 + P
2)(G
1 + P
1)(G
0
+ P
0)C
0
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:
C
1 = G
0 + P
0C
0
C
2 = G
1 + P
1G
0 + P
1(G
0
+ P
0)C
0 = G
1 + P
1G
0
+ P
1P
0C
0
C
3 = G
2 + P
2G
1 + P
2(G
1
+ P
1)G
0 + P
2(G
1 + P
1)(G
0
+ P
0)C
0 = G
2 + P
2G
1
+ P
2P
1G
0 + P
2P
1(G
0
+ P
0)C
0 = G
2 + P
2G
1
+ P
2P
1G
0 + P
2P
1P
0C
0
C
4 = G
3 + P
3G
2 + P
3(G
2
+ P
2)G
1 + P
3(G
2 + P
2)(G
1
+ P
1)G
0 + P
3(G
2 + P
2)(G
1
+ P
1)(G
0 + P
0)C
0 = G
3
+ P
3G
2 + P
3P
2G
1
+ P
3P
2P
1G
0 + P
3P
2P
1P
0C
0
Which are the same as our original equations
using G
i and P
i.
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:
)