Building an adder - combinational circuits from gates

What makes a circuit "combinational"

A combinational circuit is one whose output depends only on its current inputs, with no memory of the past. Feed it the same inputs a thousand times, in any order, and you always get the same output. This is different from sequential circuits (covered next lesson), which remember previous states — think of the difference between a light switch (combinational: its position alone decides on/off) and a coin-operated turnstile that only unlocks after being fed a coin (it needs to remember whether a coin arrived).

Adders, multiplexers, and decoders are the combinational circuits every CPU is built from. Let's build the most important one: an adder.

The half adder: adding two single bits

Let's write out every single possible input combination and what the correct Sum and Carry should be — this complete list is called a truth table:

Now compare this Sum column against the gate truth tables from the previous lesson: it's 0 when both inputs match, and 1 when they differ — that's exactly the XOR truth table. Compare the Carry column: it's 1 only in the very last row, when both inputs are 1 — that's exactly the AND truth table. So we don't need to design any new circuit at all — we just wire together two gates we already have:

$\text{Sum} = A \oplus B \qquad \qquad \text{Carry} = A \cdot B$

        A ---+----[XOR]---- Sum
             |    /
        B ---+---+
             |
             +---[AND]---- Carry

That's the entire half adder: one XOR gate feeding the Sum output, one AND gate feeding the Carry output, both reading the same two inputs $A$ and $B$. It's called "half" because it has no way to accept a carry arriving from a previous column — it only ever handles two raw bits, never three.

The full adder: adding with an incoming carry

Adding a single pair of bits is rarely enough. When you add multi-digit binary numbers by hand (as in the number systems lesson), every column past the first one has to add in whatever carry arrived from the column to its right. So we need a circuit with three inputs — $A$, $B$, and $C_{in}$ (carry-in) — producing Sum and $C_{out}$ (carry-out).

With three 1-bit inputs, there are $2^3 = 8$ possible combinations to check. Here's the complete truth table, worked out by literally adding all three bits together for each row and seeing what comes out:

Two patterns jump out immediately. First, Sum is 1 in exactly the rows with an odd number of 1s among A, B, $C_{in}$ (rows 2, 3, 5, 8) — this is precisely what chaining two XORs computes, since XOR outputs 1 when an odd number of its inputs are 1:

$\text{Sum} = A \oplus B \oplus C_{in}$

Second, $C_{out}$ is 1 in exactly the rows where at least two of the three inputs are 1 (rows 4, 6, 7, 8) — in other words, a carry-out happens if A and B are both 1 (regardless of $C_{in}$), OR if $C_{in}$ is 1 and exactly one of A/B is also 1:

$C_{out} = (A \cdot B) + \big(C_{in} \cdot (A \oplus B)\big)$

Putting it together, a full adder is built from these two formulas — concretely, from two half adders plus one extra OR gate:

                +---------------+
   A -----------|               |
                |  Half Adder 1 |---Sum1---+
   B -----------|               |          |     +---------------+
                +---------------+          +-----|               |
                                                  |  Half Adder 2 |---- Sum (final)
   C_in -----------------------------------------|               |
                                            +-----+---------------+
                                            |            |
                                         Carry1        Carry2
                                            |            |
                                            +----[OR]----+---- C_out

The first half adder combines A and B, producing an intermediate sum and carry. The second half adder combines that intermediate sum with $C_{in}$, producing the final Sum. Either half adder's carry output being 1 means a carry-out occurred, so the two carry bits are OR'd together for the final $C_{out}$. This is a genuinely satisfying result: we don't need any new fundamental circuit for a full adder — it's just two of the half adders we already built, plus one OR gate.

Chaining full adders: the ripple-carry adder

To add two 4-bit numbers, chain four full adders together, feeding each one's $C_{out}$ into the next one's $C_{in}$, exactly like carrying a digit to the next column when adding by hand:

   A3 B3      A2 B2      A1 B1      A0 B0
    |  |       |  |       |  |       |  |
  [Full Adder][Full Adder][Full Adder][Full Adder]  <- Cin of first = 0
    |     \    |     \    |     \    |
   S3    Cout->Cin   S2  Cout->Cin  S1  Cout->Cin  S0
                (etc, carry ripples left to right)

The rightmost full adder (handling bit 0, the least significant bit) always receives a $C_{in}$ of 0, since there's no column to its right to carry from. Its $C_{out}$ then becomes the $C_{in}$ for the next full adder to its left, and so on, all the way up. This chain is why it's called a ripple-carry adder: the carry has to physically "ripple" through every single stage, one at a time, before the final (leftmost) sum bit can be trusted as correct.

Worked example: add $A = 0110$ (6) and $B = 0011$ (3) using this 4-bit ripple-carry adder, column by column, right to left:

This ripple is a real speed limitation, covered properly once we discuss the ALU: a 32-bit ripple-carry adder is slower than we'd like precisely because of this chain (the last bit must wait for 31 other carries to finish first), which is why faster, more complex adder designs (like the carry-lookahead adder, covered later in the datapath module) exist in real CPUs.

The multiplexer: choosing between inputs

A multiplexer (MUX) is a circuit that selects exactly one of several inputs to pass through to its output, based on a separate select signal — like a railway switch operator choosing which of two tracks an incoming train gets routed down. A 2-to-1 MUX has two data inputs ($D_0$, $D_1$), one select line $S$, and one output $Y$. Its truth table is refreshingly simple, since $Y$ just copies whichever input $S$ points at:

This behavior is built from two AND gates and one OR gate:

$Y = (\overline{S} \cdot D_0) + (S \cdot D_1)$

Read this formula as two competing terms, only one of which can ever "win" at a time. When $S=0$: $\overline{S}=1$, so the first term becomes $1 \cdot D_0 = D_0$; meanwhile the second term becomes $0 \cdot D_1 = 0$, contributing nothing. The OR of $D_0$ and $0$ is just $D_0$. When $S=1$, the exact opposite happens, and $Y=D_1$. This tiny circuit is the reason a CPU can, for example, choose whether the ALU's next input comes from a register or from a constant embedded in the instruction — a decision we'll see constantly once we build the datapath.

Common mistakes

1. Confusing half adder and full adder. A half adder has no carry-in and only ever adds two raw bits; using one where a carry needs to flow in from a previous column will silently drop that carry and produce a wrong sum.
2. Forgetting a full adder needs 8 truth table rows, not 4. With three inputs (A, B, $C_{in}$), there are $2^3=8$ combinations to account for, not the 4 combinations a two-input half adder needs.
3. Assuming ripple-carry addition is instant. Each bit's correct sum genuinely depends on every carry to its right finishing first — this is real, measurable delay in hardware, not just a theoretical concern.
4. Forgetting a MUX needs $\log_2(n)$ select lines for $n$ inputs. A 4-to-1 MUX needs 2 select lines ($2^2=4$ choices), not 1.

Summary

Combinational circuits produce outputs based purely on current inputs, with no memory. A half adder (one XOR gate for Sum, one AND gate for Carry) adds two raw bits; its complete truth table has 4 rows. A full adder adds two bits plus an incoming carry (Sum = A⊕B⊕Cin, Cout = AB + Cin(A⊕B)), built from two half adders plus one OR gate, with a complete truth table of 8 rows. Chaining full adders together (a ripple-carry adder) adds multi-bit numbers the same way you add by hand, column by column, with each column's correct answer depending on the carry from the column before it. A multiplexer uses a select signal to choose between multiple inputs, and is the basic building block for every "choose this or that" decision inside a CPU's datapath.