Parallel Binary Adder

A parallel (ripple-carry) adder adds two n-bit numbers by cascading n full adders, with each stage's carry-out wired to the next stage's carry-in.

   Stage i:   S(i)    = A(i) ⊕ B(i) ⊕ C(i)
              C(i+1)  = A(i)B(i) + C(i)(A(i) ⊕ B(i))

   4-bit adder: C0 = 0 (for addition), output = C4 S3 S2 S1 S0
   IC 7483 is exactly this: a 4-bit binary full adder.

Worked 4-bit addition

   A = 1011 (11),  B = 0111 (7),  C0 = 0

   Stage 0: 1 + 1 + 0  ->  S0 = 0, C1 = 1
   Stage 1: 1 + 1 + 1  ->  S1 = 1, C2 = 1
   Stage 2: 0 + 1 + 1  ->  S2 = 0, C3 = 1
   Stage 3: 1 + 0 + 1  ->  S3 = 0, C4 = 1

   Result = C4 S3S2S1S0 = 1 0010 = 18  ✓  (11 + 7 = 18)

1. The Ripple-Carry Problem

The carry must physically travel through every stage before the last sum bit is valid.

   Each full adder: carry delay = 2 gate delays (AND then OR level)

   n-bit ripple carry adder:
      Total carry delay  = 2n . t
      Total sum delay    = (2n - 1) . t   approximately  (last XOR after final carry)

   For n = 4  and t = 10 ns  ->  carry settles after 80 ns
   For n = 32 and t = 10 ns  ->  carry settles after 640 ns   <- unacceptable

This is the carry propagation delay, and it is the single biggest reason a naive adder is slow.

2. Carry Look-Ahead Adder (CLA)

The idea: compute all carries in parallel from the inputs, instead of waiting for them to ripple.

Generate and Propagate

   G(i) = A(i) . B(i)         "GENERATE" — this stage makes a carry regardless of Cin
   P(i) = A(i) ⊕ B(i)         "PROPAGATE" — this stage passes an incoming carry along

   Then:  C(i+1) = G(i) + P(i).C(i)
          S(i)   = P(i) ⊕ C(i)

Expanding the recursion

   C1 = G0 + P0.C0
   C2 = G1 + P1.C1 = G1 + P1.G0 + P1.P0.C0
   C3 = G2 + P2.G1 + P2.P1.G0 + P2.P1.P0.C0
   C4 = G3 + P3.G2 + P3.P2.G1 + P3.P2.P1.G0 + P3.P2.P1.P0.C0

Every carry is now a two-level AND-OR expression of the inputs — so all four carries appear after the same 2 gate delays, no matter how many bits.

CLA delay

   1 gate delay   : compute all P(i) and G(i)
   2 gate delays  : compute all carries in parallel
   1 gate delay   : compute all sums S(i) = P(i) ⊕ C(i)
   ------------------------------------------------
   Total = 4 gate delays, INDEPENDENT of n

The practical compromise: build 4-bit CLA blocks and ripple between blocks (block carry look-ahead). This is what the 74181 ALU and most real designs do — fan-in beyond 4 or 5 inputs becomes physically impractical.

3. Parallel Binary Adder / Subtractor — the key circuit

One circuit does both operations, selected by a single control line M (mode).

How it works

   Each B input passes through an XOR gate with M:

      M = 0  ->  B(i) ⊕ 0 = B(i)      and  C0 = 0   ->  result = A + B
      M = 1  ->  B(i) ⊕ 1 = B(i)'     and  C0 = 1   ->  result = A + B' + 1
                                                          = A + (2's comp of B)
                                                          = A - B

The whole trick: M is fed to both the XOR gates (to complement B) and to C0 (to supply the +1). That is the entire cost of adding subtraction to an adder: n XOR gates and one wire.

Worked example — subtraction

   A = 1001 (9), B = 0011 (3), M = 1

   B ⊕ 1111 = 1100      (1's complement of B)
   C0 = 1

     1001
   + 1100
   +    1
   --------
   1 0110        Cout = 1 -> discard;  result = 0110 = 6   ✓ (9 - 3 = 6)

   A = 0011 (3), B = 1001 (9), M = 1

   B' = 0110,  C0 = 1
     0011
   + 0110
   +    1
   --------
   0 1010        Cout = 0 -> result is NEGATIVE and is in 2's complement form.
                 2's complement of 1010 = 0110 = 6   ->  answer = -6  ✓

Overflow detection in the adder/subtractor

   V = C(n) ⊕ C(n-1)        (XOR of the last two carries)

   V = 1  ->  signed overflow: the result does not fit in n bits.

   Example (4-bit): 0111 (+7) + 0001 (+1) = 1000
      C4 = 0, C3 = 1  ->  V = 1  ->  OVERFLOW (answer should be +8, out of range)

4. BCD Adder (bonus — often asked)

Adding two BCD digits with a binary adder gives a wrong answer whenever the sum exceeds 9.

   Correction rule: if sum > 9 OR a carry was produced, ADD 0110 (6).

   Detect:  C = K + Z8.Z4 + Z8.Z2
            where Z8 Z4 Z2 Z1 is the 4-bit binary sum and K is its carry-out.

   Example: 7 + 8 = 0111 + 1000 = 1111 (15)  -> greater than 9
            1111 + 0110 = 1 0101  ->  carry 1, digit 0101 = 5
            Answer: 15 in BCD  ✓

5. Magnitude Comparator (bonus)

   1-bit:   A > B  =  A.B'
            A < B  =  A'.B
            A = B  =  A ⊙ B  (XNOR)

   4-bit A = B  =  x3.x2.x1.x0   where x(i) = A(i) XNOR B(i)
   4-bit A > B  =  A3B3' + x3.A2B2' + x3x2.A1B1' + x3x2x1.A0B0'
                   (compare the MSBs first; only if equal look lower)

Summary

Unit I is complete: you can now simplify any function and build the arithmetic hardware from it. Unit II moves to the other family of combinational blocks — and then to circuits that remember.