Combinational Logic Design

A combinational circuit is one whose output depends only on the current values of its inputs — at any instant, the same input combination always produces the same output, with no memory of anything that happened before. That's in contrast to a sequential circuit (covered later in this topic), whose output can depend on history as well. Every technique from the last three pages — truth tables, Boolean algebra, K-map minimization — exists specifically to design circuits of this combinational kind; this page turns that toolkit into a repeatable design methodology, then applies it to build the single most important combinational building block: the adder.

A general design methodology

Given a word-description of a problem, the same four-step process gets you to a minimal gate-level circuit every time:

1. Define the problem precisely — identify every input and output signal and what each one represents.
2. Derive the truth table — for every input combination, determine the correct output. This is where the actual design thinking happens; everything after this step is mechanical.
3. Minimize — extract SOP (or POS) expressions from the truth table and minimize them with a K-map (Logic Minimization), don't-cares included wherever they apply.
4. Implement — draw or code the gate-level circuit directly from the minimized expression.

The value of following these steps explicitly, rather than jumping straight to gates from intuition, is that steps 2 and 3 are where mistakes get caught cheaply — a wrong truth-table row is trivial to fix on paper; the same mistake found after a circuit is built is far more expensive.

Half adder

The half adder adds two single bits, A and B, producing a sum bit and a carry bit — "half" because it has no way to accept a carry-in from a previous, less-significant bit position.

A B | Sum Carry
0 0 |  0    0
0 1 |  1    0
1 0 |  1    0
1 1 |  0    1

Reading the truth table directly: Sum = A ⊕ B (recognizable immediately as XOR — the "differ" gate from Boolean Algebra & Logic Gates), and Carry = A · B. No K-map is even needed here; both expressions are already minimal by inspection. A half adder is exactly two gates: one XOR, one AND.

Full adder

A full adder extends this to three inputs — A, B, and Cin (carry-in from the previous bit position) — which is what actually makes multi-bit addition possible, since every bit position past the least significant one needs somewhere for the previous column's carry to go.

A B Cin | Sum Cout
0 0  0  |  0    0
0 0  1  |  1    0
0 1  0  |  1    0
0 1  1  |  0    1
1 0  0  |  1    0
1 0  1  |  0    1
1 1  0  |  0    1
1 1  1  |  1    1

Minimizing each output separately:

Sum  = A ⊕ B ⊕ Cin
Cout = AB + BCin + ACin

Sum being a 3-input XOR chain, rather than something more elaborate, is the same "differ" logic as the half adder, just extended by one more input — this is a useful example of how the K-map on Sum's truth table (try it) actually degenerates to no adjacent-group savings at all, because XOR's output alternates with every single bit flip and has no larger-than-2 groups to find. Cout, by contrast, minimizes from a naive 4-minterm SOP down to the 3-term expression above — a genuine, K-map-verifiable simplification.

A full adder is often built structurally from two half adders plus an OR gate instead of directly from its minimized SOP — Sum = HA1.Sum ⊕ Cin, Cout = HA1.Carry + (HA2 term) — a decomposition that trades a small increase in gate count for a reusable half-adder building block, which is a common real trade-off: the minimal gate-level circuit and the most practical to build from existing parts circuit aren't always the same one.

Ripple-carry adder

Chaining n full adders — each one's Cout wired to the next one's Cin — builds an n-bit ripple-carry adder, the circuit-level realization of the binary addition process from Binary Arithmetic.

The name describes its real, physical weakness: the carry out of bit 0 has to ripple through every subsequent full adder's carry logic before the most significant sum bit is valid — the worst-case delay of an n-bit ripple-carry adder grows linearly with n. For a 4-bit adder that's negligible; for a 64-bit adder in a real processor's ALU, it's a genuine performance bottleneck, which is exactly why production ALUs use faster (and more complex) structures like carry-look-ahead adders that compute all the carries in parallel from the inputs directly, rather than waiting for each one to ripple in from the previous stage. Ripple-carry is covered here because its structure is the clearest way to see why carry propagation is a real hardware delay and not just an abstraction — the faster designs exist specifically to solve the problem ripple-carry makes visible.

Subtraction, reused

As established in Binary Arithmetic, subtraction doesn't need its own circuit — A − B is computed as A + B' + 1 (two's complement of B, then add). A single adder/subtractor circuit implements both operations by XOR-ing every bit of B with a Mode control signal before it reaches the adder (which inverts B when Mode=1) and feeding that same Mode signal in as Cin (supplying the "+1" of the complement). One ripple-carry adder, four extra XOR gates, and a control bit — no second circuit required.

What's next

Adders are the combinational block most directly tied to arithmetic; the next page covers the other core combinational building blocks — multiplexers, decoders, encoders, and comparators — that handle routing and selection rather than arithmetic, and are just as fundamental to any real digital design.