Full-adder

Gate-Level CPU Simulator

The half-adder handles a single column. Try anything bigger and the limitation shows up immediately. Walk through $3 + 5 = 8$ by hand, in 4-bit binary:

      1 1 1       ← carries
    0 0 1 1       (= 3)
  + 0 1 0 1       (= 5)
   ─────────
    1 0 0 0       (= 8)

Reading right to left, column by column:

Column 0 (rightmost): 1 + 1 = 0, carry 1. Two inputs in, sum and carry out — the half-adder handles this column fine.
Column 1: 1 + 0 + 1 (carry from column 0) = 0, carry 1. Three inputs now: $a$ 's bit, $b$ 's bit, and the carry that came in from the column on the right.
Column 2: 0 + 1 + 1 (carry) = 0, carry 1. Same shape — three inputs.
Column 3: the carry from column 2 becomes the leftmost bit of the answer.

Every column past the rightmost takes three inputs, not two. The half-adder has only two. So we need a circuit that takes three bits in ( $a$ , $b$ , and an incoming carry) and produces sum and carry-out. That's the full-adder.

A full-adder takes three input bits — the two operand bits plus an incoming carry from the column to the right — and produces two output bits: the sum and a carry to the next column. There are eight rows in its truth table now ( $2^{3}$ ). You could derive it from scratch, but the cleaner construction is to reuse what you already have: two half-adders.

First half-adder combines $a$ and $b$ . Second half-adder takes that sum bit and the incoming carry, producing the final sum. Either half-adder might emit a carry; if either does, the full-adder carries out. So: $cout = c_{1} OR c_{2}$ .

def full_adder(a, b, cin):
    """Add three single bits. Returns (sum_bit, carry_out)."""
    s1, c1 = half_adder(a, b)        # combine a and b
    s,  c2 = half_adder(s1, cin)     # then add the incoming carry
    cout = OR(c1, c2)                # carry out if either half-adder carried
    return s, cout

Full-addertwo half-adders + one OR · sum = a ⊕ b ⊕ cin · cout = (a·b) + ((a⊕b)·cin)

demo:

set a, b, cin, then pulse — gates fire in order: half-adder 1 → half-adder 2 → OR

Why two half-adders, not one big circuit?

You could derive a full-adder straight from its 8-row truth table — plenty of textbooks do — but the cleaner construction is to notice that adding three bits is just two additions stacked. The first half-adder takes a + b and produces a partial sum and a partial carry. The second adds that partial sum to the incoming carry. Whatever falls out at the end is the real sum and the real carry-out. Try the 1+1+1 demo: both half-adders carry, and you'll see the two stages fire one after the other.

Why is the final OR safe?

At a glance, combining two carries with OR looks risky. What if both half-adders carry on the same input? Wouldn't that double-count? It can't happen, and the proof is one line: if c1 = 1, then a = b = 1, which means s1 = a XOR b = 0; and with s1 = 0 the second half-adder's AND can't fire, so c2 = 0. At most one of the two half-adders ever carries. OR is exactly the gate that says "did either of them?" — no adder needed for the carries.

What's the propagation delay of a full-adder?

Two gate-delays for the sum, three for the carry-out. Trace the path: at $t = 0$ all inputs are stable. After one gate-delay the first half-adder has produced s1 and c1. After two, the second half-adder has produced sum (using s1 and cin) and c2 — sum is ready. After three, the OR has combined c1 and c2 into cout. The carry-out path is one gate longer than the sum path, and that extra gate is what limits how fast a chain of full-adders can run.

Three inputs but only two outputs — why?

Because the answer fits in two bits. Three single bits added together give a value between 0 and 3, and 0–3 needs two bits to encode. The full-adder splits its two-bit answer across two output wires: a units bit (the sum) and a carry-out bit (the bit that walks forward to the next column). Same shape as the half-adder, scaled up by one input.

What changes when you chain $n$ full-adders for multi-bit addition?

You wire FA[i].cout to FA[i+1].cin. The first full-adder's cin is hard-wired to 0; the last full-adder's cout becomes the $(n + 1)$ -th bit of the sum (overflow lives there). The catch: each FA has to wait for the previous one's carry before it can produce its own. The chain takes roughly $3 n$ gate-delays in the worst case — that's the carry rippling, and the next page is named after it.

Many phrasings, many angles

Five aspects of the full-adder, five phrasings each. Same Frege idea as the half-adder page: same reference, different senses. Scan down a cluster until something clicks.

Each heading is a different facet of the full-adder. Each line under it is a different way to say the same thing about that facet. Scan down a cluster until something clicks; once any one phrasing lands, the others retroactively make sense.

Why a third input (cin)

The half-adder fails on multi-bit addition because every column past the rightmost has three things to combine: the column's two operand bits and a carry that walked in from the column on the right.
The third input is the link that lets full-adders chain. Without cin, every column would have to be an isolated half-adder, which doesn't compose.
cin is just cout from the previous column, renamed. Same wire, two endpoints.
Long-form decimal addition has the same structure: each column has two operand digits plus a carry-in from the column to its right. The full-adder is the binary version of that column-shape.
For the rightmost column, cin = 0. That's the only column where the half-adder's two-input shape is enough.

Why two outputs (sum and cout)

Adding three bits can give a value between 0 and 3, and 0–3 needs two bits to encode. The full-adder's two outputs carry those two bits.
1+1+1 = 3, which is binary 11 — two digits — and a single output bit can't hold both.
Same argument as the half-adder, scaled up by one input: the codomain still doesn't fit in one bit, so two output wires are needed.
The two outputs go to different places: sum becomes that column's bit of the final answer; cout becomes the next column's cin.
A single boolean gate has 1 bit of output, so no single gate can be a full-adder. The minimum output width is 2 bits.

Sum is parity (XOR of three)

The sum bit is a XOR b XOR cin — high when an odd number of inputs are 1.
0 inputs high → 0 (even). 1 high → 1 (odd). 2 high → 0 (even). 3 high → 1 (odd). The pattern is exactly XOR-of-three.
The half-adder's sum was 2-input parity (a XOR b). The full-adder's is 3-input parity. Same function, one more input.
XOR(XOR(a, b), cin) — that's two XORs in series, exactly what two stacked half-adders give you.
Trace the eight-row truth table: the sum column reads 01101001 (LSB → MSB). That's the parity column. XOR computes parity by definition.

Cout is majority

The carry-out fires when at least two of the three inputs are 1 — the majority of a, b, cin.
Boolean form: (a AND b) OR (a AND cin) OR (b AND cin). The OR of all pairwise ANDs.
The two-half-adder construction's c1 OR c2 computes the same thing: c1 catches "both a and b are 1," c2 catches "their sum is 1 AND cin is 1." Algebra confirms equivalence.
The carry-out column of the truth table reads 00010111 (LSB → MSB). That's the majority column.
The half-adder's carry was a AND b — the 2-input "majority" (both must be 1). The full-adder's carry is the 3-input majority. Function generalizes.

Composition: two half-adders + an OR

The full-adder is two half-adders stacked plus a single OR. First half-adder: a + b. Second: result + cin. OR: combine the two carries.
Five gates total per bit-position. Two XORs, two ANDs, one OR.
Critical path: sum is ready in two gate-delays; carry-out takes three (the OR is one stage past the second half-adder).
The composition is one possible synthesis. Direct truth-table synthesis (a 3-input gate per output) gives the same function in different layout.
The two half-adders share inputs (the second receives s1 from the first), but they don't share intermediate gates. They're stacked sequentially, not interleaved.

Five gates total per bit position — two XORs (one inside each half-adder), two ANDs, one OR. That's the cost of adding one bit-position. The next page chains $n$ of these to build an $n$ -bit adder.