Combinational Circuits
Logic Gates · Foundations track
4 min read
In this module
Building Useful Circuits
Individual gates are a bit like individual letters: largely meaningless on their own, but combine them and you can express anything. A combinational circuit is a network of gates whose output depends only on its current inputs, with no memory of past values. Let's build some.
The Half Adder
The simplest arithmetic circuit adds two single bits. It produces a sum and a carry:
| A | B | Sum | Carry |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Stare at the truth table for a moment. The Sum column is exactly XOR. The Carry column is exactly AND. So a half adder is one XOR and one AND working side by side.
The Full Adder
A half adder can't handle a carry coming in from a previous column. A full adder fixes that by accepting three inputs: A, B, and a carry-in (Cin). It produces a sum and a carry-out (Cout).
You build a full adder from two half adders and an OR gate. The first half adder adds A and B. The second adds that partial sum to Cin. If either half adder produced a carry, the OR passes it on as Cout:
Chain multiple full adders together, each one's Cout feeding the next one's Cin, and you get a ripple-carry adder, a circuit that adds multi-bit numbers exactly the way you did by hand in Binary & Number Systems.
Four full adders give you a 4-bit adder. Here it is adding 0101 (5) and 0011 (3), one column at a time from the right:
| Bit | A | B | Cin | Sum | Cout |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 |
| 2 | 1 | 0 | 1 | 0 | 1 |
| 3 | 0 | 0 | 1 | 1 | 0 |
Reading the Sum column from bit 3 down gives 1000, which is 8. Notice that bit 3 can't settle until the carry has passed through bits 0, 1 and 2. In a 64-bit adder that carry may have to ripple through 64 stages, which is why real CPUs use cleverer adders that work out carries in parallel.
Combinational circuits have no memory; their outputs are determined entirely by their current inputs. Sequential circuits (coming later in the course) use feedback and storage elements to remember previous states. Both types are foundational to how a computer works.
Multiplexers
A multiplexer (or mux) is a circuit that selects one of several inputs and forwards it to the output. A 2-to-1 mux has two data inputs (D0 and D1), one select line (S), and one output:
- When
S = 0, the output equals D0. - When
S = 1, the output equals D1.
The Boolean expression: Output = S' * D0 + S * D1. Multiplexers are everywhere in CPU design. They route data between registers, memory, and the ALU based on control signals.
Inside the ALU
The Arithmetic Logic Unit is the part of the CPU that performs calculations. Underneath, an ALU is a carefully designed combinational circuit built from the same gates and adders we've been studying. Control signals tell it which operation to perform (add, subtract, AND, OR, XOR), and multiplexers pick the correct result to send out.
A simple way to picture it: every operation circuit works on the inputs at the same time, and a 4-to-1 mux, driven by the operation code, chooses which answer leaves the ALU.
Computing four answers to keep one sounds wasteful, but gates are cheap and waiting is not. You'll open this box up properly in CPU Basics.
Every time your computer executes an instruction, the ALU is doing its job using exactly the building blocks from this module.
Try It Yourself
The interactive canvas below lets you wire up logic gates and see how they behave. Try building a half adder (one XOR gate for the sum, one AND gate for the carry), or experiment with other combinations.