Carry propagation when adding multiple bits

This is a clarification from Johan Kwisthout:

See slide 14 of the intro lecture. The schematic shows you how to add up two single bits (A and B) with an incoming carry (C-in), resulting in a sum S and outgoing carry C-out. Of course, one would want to add up more than just two one-bit numbers. Lets assume you want to add up two four-bit numbers. Doing this on paper, you would get something like:

     C3 C2 C1 C0
     A3 A2 A1 A0
     B3 B2 B1 B0
-----------------
  C4 S3 S2 S1 S0

For example, adding A = 1011 and B = 0101 with C-in = 0 gives

C     1 1 1 0
A     1 0 1 1
B     0 1 0 1
-----------------
    1 0 0 0 0

If you do this on paper this is a serial process: you first add A0 and B0 and C0, generating S0 and C1, then you add A1 and B1 and C1, generating S1 and C2, etcetera. We need to wait for the carry bits to be generated before we can continue. Can we speed up this process and do the computations in parallel? Yes, we can! For that we need to look at the underlying logic in the right picture of slide 14:

  • S = (A XOR B) XOR C-in

  • C-out = (A AND B) OR ((A XOR B) AND C-in)

We define P = A XOR B and G = A AND B. P stands for 'carry propagation', G for 'carry generation'. For multiple bits, the formulas now become:

  • S0 = P0 XOR C0
  • C1 = G0 OR (P0 AND C0)

  • S1 = P1 XOR C1

  • C2 = G1 OR (P1 AND C1)

  • S2 = P2 XOR C2

  • C3 = G2 OR (P2 AND C2)

etc. As you see we need C1 to compute S1, C2 to compute S2 etc. Let's try to plug in C1 into the formula of C2:

  • C2 = G1 OR (P1 AND (G0 OR (P0 AND C0)))

And C2 into the formula of C3:

  • C3 = G2 OR (P2 AND (G1 OR (P1 AND (G0 OR (P0 AND C0)))))

and for the fourth carry:

  • C4 = G3 OR (P3 AND (G2 OR (P2 AND (G1 OR (P1 AND (G0 OR (P0 AND C0))))) ))

Recall that P = (A XOR B) and G = (A AND B) and so we can compute C1, C2, C3 and C3 solely using the input bits from A and B and C0 (simulatenously, in parallel). This is what we see on slide 15, fixing the error (ORs should be XORs) on the slide.