In Logic Gates & Boolean Algebra we learned to build and simplify single functions. A processor, however, is not designed gate by gate. Engineers think in bigger building blocks: an adder that adds two words, a multiplexer that picks one of several inputs, a decoder that selects one memory chip out of eight. These blocks are the bricks of the ALU, the register file and the memory system.
A combinational circuit is a circuit whose outputs at any moment depend only on its current inputs. It has no memory, no clock and no feedback loops.
Contrast this with sequential circuits (the next chapter), whose outputs also depend on what happened before. A combinational circuit is completely described by a truth table; a sequential one is not.
In this chapter we build half and full adders, the ripple-carry adder and why it is slow, the carry-lookahead adder that fixes it, the adder-subtractor, a comparator, multiplexers, demultiplexers, decoders and encoders, and we see how to implement any function with a multiplexer or a decoder. Every equation in this chapter was verified by simulating all input combinations in Python.
Designing a Combinational Circuit
The design procedure is always the same:
Decide the inputs and outputs and give them names.
Write the truth table.
Derive a simplified expression for each output (K-map or algebra).
Draw the circuit.
We will follow these steps for the adders.
Half Adder
Adding two bits A and B gives a 2-bit result: a sum bit S and a carry bit C.
A | B | C (carry) | S (sum) |
|---|---|---|---|
0 | 0 | 0 | 0 |
0 | 1 | 0 | 1 |
1 | 0 | 0 | 1 |
1 | 1 | 1 | 0 |
Reading the columns directly: S = A ⊕ B and C = AB. One XOR gate and one AND gate.
It is called "half" because it cannot accept a carry coming in from a lower bit position, so it is only good for the least significant bit.
Full Adder
A full adder adds three bits: A, B and the incoming carry Cin.
A | B | Cin | Cout | S |
|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 | 1 |
0 | 1 | 0 | 0 | 1 |
0 | 1 | 1 | 1 | 0 |
1 | 0 | 0 | 0 | 1 |
1 | 0 | 1 | 1 | 0 |
1 | 1 | 0 | 1 | 0 |
1 | 1 | 1 | 1 | 1 |
S = Σm(1, 2, 4, 7) = A ⊕ B ⊕ Cin (1 when an odd number of inputs are 1)
Cout = Σm(3, 5, 6, 7) = AB + ACin + BCin (majority function: 1 when at least two are 1)
= AB + Cin(A ⊕ B) (equivalent form, reuses A ⊕ B)
The second form of Cout shows that a full adder is two half adders and an OR gate:
+-------+ A⊕B +-------+
A ------>| |--------->| |------------------------> S = A⊕B⊕Cin
| HA1 | | HA2 |
B ------>| | Cin -->| |
+-------+ +-------+
| AB | Cin·(A⊕B)
| |
+----->[ OR ]<---+
|
+---------------------------------------> Cout
Intuition for the two carry terms: a carry comes out either because A and B are both 1 (the stage generates a carry by itself), or because exactly one of them is 1 and a carry came in (the stage propagates the incoming carry). Remember these two words; they are the key to fast adders.
Half and Full Subtractor
Subtractors follow the same pattern, computing A − B with a borrow:
Half subtractor: D = A ⊕ B Bout = A′B
Full subtractor: D = A ⊕ B ⊕ Bin Bout = A′B + A′Bin + B·Bin
= A′B + Bin·(A ⊕ B)′
The difference bit is identical to the sum bit. Only the borrow differs from the carry, by complementing A. In practice, processors rarely build separate subtractors: they subtract by adding the 2's complement, as we will see shortly.
Ripple-Carry Adder
To add two n-bit numbers, chain n full adders. Each stage's Cout feeds the next stage's Cin:
A3 B3 A2 B2 A1 B1 A0 B0
| | | | | | | |
+------+ C3 +------+ C2 +------+ C1 +------+
C4| FA3 |<----| FA2 |<----| FA1 |<----| FA0 |<-- C0
+------+ +------+ +------+ +------+
| | | |
S3 S2 S1 S0
It is simple and uses only n full adders, but it is slow: stage i cannot finish until the carry has rippled through all stages below it. The worst case is something like 0111...1 + 0000...1, where a carry starts at bit 0 and travels all the way to the top.
Delay of a Ripple-Carry Adder
We count delay in gate delays. Assume Cout = AB + ACin + BCin is built as a two-level AND-OR circuit (2 gate delays from Cin), and the sum is one XOR gate (1 gate delay after Cin arrives). All A and B inputs are ready at time 0.
C1 at 2, C2 at 4, C3 at 6, ..., Ci at 2i
Sum S(i) = needs C(i), then 1 XOR: S(i) at 2i + 1
n-bit ripple-carry adder:
final carry C(n) at 2n gate delays
top sum bit S(n-1) at 2(n-1) + 1 = 2n - 1 gate delays
16-bit: C16 at 32, S15 at 31 32-bit: C32 at 64, S31 at 63
The delay grows linearly with n. For a 64-bit processor running at several GHz, waiting 128 gate delays for every addition is not acceptable.
Carry-Lookahead Adder (CLA)
The idea: instead of waiting for carries to ripple, compute every carry directly from the inputs, in parallel.
For each bit position define:
Generate Gi = AiBi: stage i produces a carry on its own.
Propagate Pi = Ai ⊕ Bi: stage i passes an incoming carry through.
Then Ci+1 = Gi + PiCi and Si = Pi ⊕ Ci.
Now expand the recurrence by substituting each carry into the next:
C1 = G0 + P0·C0
C2 = 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
Read C4 in plain words: "there is a carry into bit 4 if bit 3 generates one, or bit 2 generates one and bit 3 propagates it, or ... or the input carry C0 is propagated by all four stages." Every carry is now a two-level sum of products of G's, P's and C0, so no carry waits for another.
Delay of a 4-bit CLA
All Gi, Pi: 1 gate delay (one AND / one XOR, all in parallel)
All carries C1..C4: 1 + 2 = 3 (one AND level + one OR level)
All sums Si = Pi ⊕ Ci: 3 + 1 = 4
The delay is constant, independent of where the carry starts.
The Catch: Fan-in
C4 already needs a 5-input OR gate and a 5-input AND gate. For 32 bits, C32 would need 33-input gates, which are impractical (large fan-in gates are slow and big). So real adders are built hierarchically: 4-bit CLA blocks, joined either by rippling the carry between blocks or by a second level of lookahead using block generate and propagate signals:
Block propagate P* = P3·P2·P1·P0
Block generate G* = G3 + P3·G2 + P3·P2·G1 + P3·P2·P1·G0
Carry out of the block = G* + P*·C0
With the same delay model, four 4-bit CLA blocks connected in ripple fashion give, for a 16-bit adder: C4 at 3, C8 at 5, C12 at 7, C16 at 9 and S15 at 10 gate delays, versus 32 and 31 for the plain ripple-carry adder.
(Some books define Pi = Ai + Bi instead of Ai ⊕ Bi. The carry equations remain correct, because when Ai = Bi = 1 the Gi term already produces the carry; but the sum then needs Si = Ai ⊕ Bi ⊕ Ci.)
Point | Ripple-carry adder | Carry-lookahead adder |
|---|---|---|
Carry computation | Sequential, stage by stage | Parallel, from G and P |
Delay | O(n) (2n gate delays for the carry) | O(1) per block; O(log n) for a full lookahead tree |
Hardware | n full adders, minimal | Extra lookahead logic; large fan-in |
Use | Small or low-power designs | Processor ALUs |
Adder-Subtractor
In 2's complement, A − B = A + B′ + 1 (see Signed Numbers: Sign-Magnitude, 1's & 2's Complement). An adder can therefore subtract if we invert B and set the input carry to 1. Both can be controlled by one mode bit M using XOR gates as controllable inverters (B ⊕ 0 = B, B ⊕ 1 = B′):
B3 B2 B1 B0
| | | |
M ---+--- XOR -- XOR -- XOR -- XOR each XOR computes Bi ⊕ M
| | | | |
| [4-bit ripple-carry adder] <-- C0 = M
| | | | |
S3 S2 S1 S0
M = 0: S = A + B + 0 (addition)
M = 1: S = A + B′ + 1 = A - B (subtraction)
Overflow (signed): V = C4 ⊕ C3
The overflow rule V = Cn ⊕ Cn−1 (carry into the sign bit differs from carry out of it) was explained in Binary Arithmetic & Overflow. This one circuit, with a few more gates for AND, OR and so on, is the heart of an ALU.
Magnitude Comparator
A comparator outputs whether A > B, A = B or A < B. For one bit:
(A > B) = AB′ (A = B) = (A ⊕ B)′ = A′B′ + AB (A < B) = A′B
For multi-bit numbers, compare from the most significant bit: the first position where the bits differ decides. With xi = (Ai ⊕ Bi)′ meaning "bit i equal", a 2-bit comparator is:
(A = B) = x1·x0
(A > B) = A1B1′ + x1·A0B0′
(A < B) = A1′B1 + x1·A0′B0
The same pattern extends to any width (the classic 7485 chip is a 4-bit comparator that can be cascaded).
Multiplexer (MUX)
A multiplexer (data selector) has 2n data inputs, n select lines and one output. The select lines choose which data input is connected to the output.
Think of a railway switch, or the input selector on a TV that picks HDMI1, HDMI2 or the antenna.
4-to-1 MUX
S1 | S0 | Y |
|---|---|---|
0 | 0 | I0 |
0 | 1 | I1 |
1 | 0 | I2 |
1 | 1 | I3 |
Y = S1′S0′·I0 + S1′S0·I1 + S1S0′·I2 + S1S0·I3
Each AND term contains one select minterm, so exactly one data input is "enabled" at any time. In a processor, MUXes choose the ALU's second operand (register or immediate), the next PC (PC + 4 or branch target) and the value written back to a register. They also build the read ports of the register file.
Building Larger MUXes
A 16-to-1 MUX can be built as a tree of 4-to-1 MUXes: four in the first level (each handles 4 inputs, selected by S1 S0) and one in the second level (selected by S3 S2). That is 5 MUXes.
To build an N-to-1 MUX from k-to-1 MUXes (N a power of k), you need (N − 1)/(k − 1) of them. From 2-to-1 MUXes: N − 1. Examples: 8-to-1 from 2-to-1 needs 7; 16-to-1 from 4-to-1 needs 5; 64-to-1 from 4-to-1 needs 16 + 4 + 1 = 21.
Implementing a Function with a MUX
A 2n-to-1 MUX can implement any function of n variables (connect the variables to the select lines and put the truth-table column, 0s and 1s, on the data inputs). Better still, a 2n−1-to-1 MUX is enough: use n − 1 variables as selects and feed the last variable, its complement, 0 or 1 into the data inputs.
Example 1: F(A, B, C) = Σm(1, 3, 5, 6) with a 4-to-1 MUX
Use A and B as select lines (S1 = A, S0 = B). For each value of AB, look at the two rows of the truth table and see how F depends on C:
AB rows (C=0, C=1) F values F as a function of C MUX input
00 m0, m1 0, 1 C I0 = C
01 m2, m3 0, 1 C I1 = C
10 m4, m5 0, 1 C I2 = C
11 m6, m7 1, 0 C′ I3 = C′
Possible entries: (0,0) → 0 (1,1) → 1 (0,1) → C (1,0) → C′
So F is a 4-to-1 MUX with S1 = A, S0 = B, I0 = I1 = I2 = C and I3 = C′. No other gates are needed besides an inverter for C′.
Demultiplexer (DEMUX)
A demultiplexer does the reverse: one data input, n select lines, 2n outputs. The input is routed to the output chosen by the selects; all other outputs are 0. For a 1-to-4 DEMUX with data input D:
Y0 = S1′S0′·D Y1 = S1′S0·D Y2 = S1S0′·D Y3 = S1S0·D
Compare with a 2-to-4 decoder with enable (below): the equations are identical with D playing the role of the enable. That is why chip catalogues sell "decoder/demultiplexer" as one part.
Decoder
An n-to-2n decoder has n inputs and 2n outputs; for each input combination exactly one output is 1. Output i is the minterm mi of the inputs.
2-to-4 Decoder with Enable
E | A1 | A0 | D0 | D1 | D2 | D3 |
|---|---|---|---|---|---|---|
0 | x | x | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 1 | 0 | 0 | 0 |
1 | 0 | 1 | 0 | 1 | 0 | 0 |
1 | 1 | 0 | 0 | 0 | 1 | 0 |
1 | 1 | 1 | 0 | 0 | 0 | 1 |
Decoders are everywhere in a computer: the instruction decoder turns an opcode into "this is an ADD" signals, address decoders select which memory chip or I/O device responds to an address, and a decoder selects which register in the register file is written.
Building Larger Decoders
3-to-8 from two 2-to-4 decoders: feed A1 A0 to both; enable the first with A2′ and the second with A2. The first produces D0 to D3, the second D4 to D7.
4-to-16 from 2-to-4 decoders: four decoders for the outputs (inputs A1 A0), plus one more 2-to-4 decoder driven by A3 A2 whose four outputs enable them. Total 5 decoders.
4-to-16 from two 3-to-8 decoders: enable one with A3′ and the other with A3.
Implementing Functions with a Decoder
Since a decoder produces every minterm, any function in Σm form is just an OR of the right decoder outputs. A full adder needs one 3-to-8 decoder and two OR gates:
Inputs A, B, Cin → 3-to-8 decoder → outputs m0 ... m7
S = m1 + m2 + m4 + m7 (4-input OR)
Cout = m3 + m5 + m6 + m7 (4-input OR)
If a function has more 1s than 0s, it can be cheaper to OR the minterms of F′ and then invert (a NOR gate).
Encoder and Priority Encoder
An encoder is the inverse of a decoder: it has 2n inputs, of which one is active, and n outputs giving the binary index of the active input.
For an 8-to-3 encoder: Y2 = D4 + D5 + D6 + D7, Y1 = D2 + D3 + D6 + D7, Y0 = D1 + D3 + D5 + D7. Each output ORs the inputs whose index has that bit set.
A plain encoder has two problems: if two inputs are active, the output is garbage (D3 and D4 together give 111, as if D7 were active), and if no input is active the output 000 looks the same as "D0 active". A priority encoder solves both: the highest-numbered active input wins, and a valid bit V says whether any input is active.
4-to-2 Priority Encoder (D3 Highest Priority)
D3 | D2 | D1 | D0 | Y1 | Y0 | V |
|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | x | x | 0 |
0 | 0 | 0 | 1 | 0 | 0 | 1 |
0 | 0 | 1 | x | 0 | 1 | 1 |
0 | 1 | x | x | 1 | 0 | 1 |
1 | x | x | x | 1 | 1 | 1 |
Y1 = D3 + D2
Y0 = D3 + D2′·D1
V = D3 + D2 + D1 + D0
Here x means "don't care": once a higher input is 1, lower inputs do not matter. Priority encoders appear in interrupt controllers (pick the highest-priority pending interrupt, as you will see in Programmed I/O & Interrupts) and in floating-point units (find the leading 1 when normalizing).
All the Blocks at a Glance
Block | Inputs → outputs | What it does | Where it is used in a CPU |
|---|---|---|---|
Half adder | 2 → 2 | S = A ⊕ B, C = AB | Least significant bit, incrementers |
Full adder | 3 → 2 | S = A ⊕ B ⊕ Cin, Cout = majority | Every bit of the ALU adder |
Ripple-carry adder | 2n + 1 → n + 1 | n-bit addition, O(n) delay | Simple ALUs |
Carry-lookahead adder | 2n + 1 → n + 1 | Carries in parallel from G, P | Fast ALUs |
MUX | 2n data + n select → 1 | Selects one input | Datapath operand and PC selection |
DEMUX | 1 data + n select → 2n | Routes input to one output | Distributing signals |
Decoder | n → 2n | Activates one output (minterm) | Instruction and address decoding |
Priority encoder | 2n → n + valid | Index of highest active input | Interrupt priority, leading-one detection |
Common Mistakes
Writing Cout = A ⊕ B ⊕ Cin. That is the sum. The carry is the majority function AB + ACin + BCin.
Counting the ripple-carry delay as n. Each stage costs about 2 gate delays for the carry, so 2n under the usual model. Always state your delay model.
Thinking a CLA has constant delay for any width. Only with unlimited fan-in. Practical CLAs are hierarchical with O(log n) delay.
Confusing MUX and decoder. A MUX has many inputs and one output; a decoder has few inputs and many outputs.
Counting MUXes for a tree as N/k. You also need the next levels: 16-to-1 from 2-to-1 is 8 + 4 + 2 + 1 = 15, not 8.
Forgetting the enable when building a big decoder from small ones. 4-to-16 from 2-to-4 needs 5 decoders, not 4.
Using a plain encoder when several inputs can be active. Use a priority encoder.
GATE and Interview Questions
Q1. In a 32-bit ripple-carry adder, each full adder has a carry delay of 2 gate delays and a sum delay of 1 gate delay after its carry input is ready. When are C32 and S31 available?
Ci is available at 2i, so C32 at 64 gate delays. S31 needs C31 (at 62) plus 1: 63 gate delays.
Q2. Write C3 of a carry-lookahead adder in terms of G, P and C0.
C3 = G2 + P2G1 + P2P1G0 + P2P1P0C0.
Q3. How many 2-to-1 multiplexers are needed to build a 32-to-1 multiplexer?
N − 1 = 31 (16 + 8 + 4 + 2 + 1).
Q4. Implement F(A, B, C) = Σm(0, 2, 6, 7) using a 4-to-1 MUX with A and B on the select lines.
AB = 00: m0 = 1, m1 = 0 → C′. AB = 01: m2 = 1, m3 = 0 → C′. AB = 10: m4 = 0, m5 = 0 → 0. AB = 11: m6 = 1, m7 = 1 → 1. So I0 = C′, I1 = C′, I2 = 0, I3 = 1.
Q5. How many 3-to-8 decoders (with enable) are needed to build a 6-to-64 decoder?
Eight 3-to-8 decoders produce the 64 outputs (driven by the low 3 address bits), and one more 3-to-8 decoder driven by the high 3 bits enables one of them: 9.
Q6. Why is XOR used in the adder-subtractor circuit?
B ⊕ M passes B unchanged when M = 0 and inverts it when M = 1. Together with C0 = M, this computes A + B or A + B′ + 1 = A − B with the same adder.
Q7. What is the difference between a combinational and a sequential circuit?
A combinational circuit's outputs depend only on current inputs (no memory, no feedback); a sequential circuit's outputs depend also on stored state, so it contains memory elements and usually a clock.
Summary
Combinational circuits have no memory: output = function(current inputs).
Half adder: S = A ⊕ B, C = AB. Full adder: S = A ⊕ B ⊕ Cin, Cout = AB + ACin + BCin = AB + Cin(A ⊕ B).
The ripple-carry adder is simple but its delay grows linearly (2n gate delays for Cn).
The carry-lookahead adder uses Gi = AiBi, Pi = Ai ⊕ Bi, Ci+1 = Gi + PiCi, expanded so that all carries are computed in parallel (4-bit: carries at 3, sums at 4 gate delays).
An adder-subtractor uses XOR gates on B and C0 = M.
A MUX selects one of 2n inputs; it can implement any function of n + 1 variables using n selects. N-to-1 from 2-to-1 needs N − 1 MUXes.
A decoder outputs all minterms; with OR gates it implements any SOP. A priority encoder reports the highest active input plus a valid bit.
None of these circuits can remember anything. In Sequential Circuits: Flip-Flops, Registers & Counters we add feedback and a clock to build memory.