3. Combinational Circuits
Learning Objectives
- Define a combinational circuit and explain why it has no memory
- Derive the truth table and Boolean expression of a half adder and full adder
- Explain how a multiplexer selects one of several inputs using select lines
- Explain how a demultiplexer routes one input to one of several outputs
- Distinguish combinational circuits from sequential circuits
- Apply combinational circuit design steps to a simple custom function
Quick Answer
A combinational circuit is a digital circuit built from logic gates whose output depends only on the current combination of inputs — it has no memory of past inputs. Feed it the same inputs twice and you always get the same output, instantly (aside from small propagation delays). Adders, multiplexers, demultiplexers, encoders, and decoders are all combinational circuits. They matter because they are the "instant calculation" building blocks of digital systems — a CPU's arithmetic logic unit, for example, is fundamentally a large combinational circuit that computes results the moment its inputs are stable.
How Combinational Circuits Work
Because there's no memory element (no flip-flop, no feedback loop), a combinational circuit's behavior can be fully captured in a truth table, and every output can be written as a Boolean expression of the inputs. Design always follows the same recipe: define the function in words, build a truth table, derive and simplify the Boolean expression, then draw the gate-level circuit.
Half Adder
A half adder adds two single bits and produces a sum and a carry.
| A | B | Sum (A⊕B) | Carry (A·B) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Sum = A XOR B, Carry = A AND B. Notice the sum bit is exactly the XOR truth table — this is why XOR is called the "addition without carry" gate.
Limitation: A half adder cannot accept a carry-in from a previous stage, so it can only be used for the least significant bit of a multi-bit addition.
Full Adder
A full adder extends the half adder by accepting a carry-in (Cin), making it possible to chain adders together for multi-bit arithmetic.
| 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 |
Sum = A ⊕ B ⊕ Cin, Cout = AB + Cin(A⊕B). A full adder can be built from two half adders plus an OR gate for the final carry.
Real-world example: Chain four full adders together and you get a 4-bit ripple-carry adder — the same principle scales up to the 32-bit or 64-bit adders inside a CPU's ALU.
Multiplexer (MUX)
A multiplexer is a digital switch: it selects one of several data inputs and routes it to a single output, based on select lines. A 2-to-1 MUX has one select line S:
| S | Output |
|---|---|
| 0 | I0 |
| 1 | I1 |
For n select lines, a MUX can choose among 2ⁿ inputs. A 4-to-1 MUX needs 2 select lines; an 8-to-1 MUX needs 3.
Demultiplexer (DEMUX)
A demultiplexer does the reverse: it takes one input signal and routes it to exactly one of several output lines, chosen by select lines.
| S | Output A | Output B |
|---|---|---|
| 0 | Input | 0 |
| 1 | 0 | Input |
Why it matters: MUX/DEMUX pairs let a single physical wire or bus carry many different signals over time — this is exactly how time-division multiplexing works in telecommunications, letting many phone calls share one line.
Common Misunderstanding
Students often think combinational circuits "remember" the previous output because a circuit diagram looks like it has feedback. In a true combinational circuit there is no feedback path — every output wire traces back only to input wires and gates, never to a stored state. If you see a feedback loop from output to input, you're looking at a sequential circuit instead.
Key Terms
| Term | Definition | Related Concept |
|---|---|---|
| Combinational circuit | A circuit whose output depends only on present inputs | No memory element |
| Half adder | Adds two bits, producing sum and carry, no carry-in | XOR and AND gates |
| Full adder | Adds two bits plus a carry-in, producing sum and carry-out | Chained for multi-bit addition |
| Multiplexer (MUX) | Selects one of several inputs based on select lines | Data selector |
| Demultiplexer (DEMUX) | Routes one input to one of several outputs | Data distributor |
| Select line | Control input that determines which data path is active in a MUX/DEMUX | Digital switching |
| Ripple-carry adder | Multiple full adders chained so carry propagates stage to stage | Multi-bit addition |
Common Mistakes
Misconception: A half adder can be used anywhere in a multi-bit addition. Why it's wrong: A half adder has no carry-in input, so it cannot correctly account for a carry generated by a lower-order bit. Correct understanding: Use a half adder only for the least significant bit (which has no incoming carry); use full adders for every other bit position.
Misconception: A 4-to-1 multiplexer needs 4 select lines, one per input. Why it's wrong: Select lines encode a binary address of which input to choose, not one line per input. Correct understanding: n select lines can address 2ⁿ inputs, so a 4-to-1 MUX needs only 2 select lines (00, 01, 10, 11 select inputs I0–I3).
Misconception: Combinational circuits and sequential circuits are basically interchangeable since both use logic gates. Why it's wrong: The presence of memory elements (flip-flops) and feedback fundamentally changes behavior — a sequential circuit's output depends on history, not just current inputs. Correct understanding: If a circuit uses only gates with no feedback or storage, it is combinational; if it needs to "remember" past states to decide the current output, it is sequential.
Comparison and Connections
| Circuit | Inputs | Outputs | Carry-in? | Typical Use |
|---|---|---|---|---|
| Half Adder | A, B | Sum, Carry | No | LSB of an addition |
| Full Adder | A, B, Cin | Sum, Carry-out | Yes | Any bit position in multi-bit addition |
| Multiplexer | 2ⁿ data + n select | 1 | — | Selecting one of many signals |
| Demultiplexer | 1 data + n select | 2ⁿ | — | Routing one signal to many destinations |
Practice Questions
Recall
-
What are the two outputs of a full adder? Sum and Carry-out (Cout).
-
How many select lines are needed for an 8-to-1 multiplexer? 3 select lines, since 2³ = 8 inputs.
Understanding
-
Why is the sum output of a half adder identical to the XOR truth table? Because addition of two single bits without a carry produces 1 exactly when the bits differ (0+1 or 1+0), which is precisely what XOR computes.
-
Explain why a full adder is more versatile than a half adder in a multi-bit adder chain. The full adder's carry-in input lets it absorb the carry produced by the previous (lower) bit position, allowing full adders to be cascaded to add numbers of any bit width.
Application
-
Design a 4-bit ripple-carry adder using full adders. What connects the carry-out of one stage to the next stage? Chain four full adders; the Cout of stage n becomes the Cin of stage n+1. The first stage (LSB) can use Cin = 0 or a half adder.
-
You need to route one of four sensor signals to a single ADC input based on a 2-bit control code. What component do you use and how many select lines are required? A 4-to-1 multiplexer with 2 select lines, where the select code (00–11) picks which sensor's signal reaches the ADC.
Analysis
-
A student builds a full adder using two half adders and claims one OR gate is unnecessary because both half-adder carries can never be 1 at the same time. Evaluate this claim. The claim is false in general — it is true that both half-adder carries cannot both be 1 simultaneously for a single-bit full adder, but you still need the OR gate to combine them into Cout because either one alone can be 1 depending on the input combination. Removing it would lose carry information in some cases.
-
Compare the wiring complexity of a demultiplexer to a multiplexer with the same number of select lines. Which has more output connections, and why does that matter for PCB layout? A DEMUX with n select lines has 2ⁿ outputs but only 1 input, whereas a MUX with n select lines has 2ⁿ inputs but only 1 output. The DEMUX therefore needs more output traces, which can matter for routing density and pin count in the target application.
FAQ
Why don't combinational circuits need a clock signal? Because their output depends only on the current inputs, not on timing or sequence. As soon as inputs settle, the output settles too (after the gates' propagation delay) — there's no need to synchronize state changes to a clock edge as sequential circuits do.
Can a multiplexer replace a set of AND/OR gates? Yes, in fact any Boolean function of n variables can be implemented using a 2ⁿ-to-1 multiplexer by connecting each data input to the correct output value from the truth table. This is a common technique in digital design called "function implementation using MUX."
What is the difference between an encoder and a multiplexer? A multiplexer selects one of many inputs to pass through based on a select code. An encoder converts an active input line (like one of 8 buttons) into a binary code representing which line is active — it compresses information rather than selecting a signal path.
Why do ripple-carry adders get slower as bit width increases? Because each full adder's carry-out must wait for the carry from the previous stage to be valid before it can compute its own — the carry "ripples" through the chain, so the worst-case delay grows linearly with the number of bits. This is why faster designs like carry-look-ahead adders exist.
Are combinational circuits used anywhere besides arithmetic? Extensively — decoders drive seven-segment displays, multiplexers implement digital switches and function generators, and priority encoders are used in interrupt-handling hardware. Any "instant decision from current inputs" logic is combinational.
Quick Revision
- Combinational circuits have no memory; output depends only on present inputs
- Half adder: Sum = A⊕B, Carry = A·B — no carry-in
- Full adder: Sum = A⊕B⊕Cin, Cout = AB + Cin(A⊕B) — accepts carry-in
- Chain full adders (carry-out to next carry-in) to build multi-bit ripple-carry adders
- A MUX with n select lines picks 1 of 2ⁿ inputs
- A DEMUX with n select lines routes 1 input to 1 of 2ⁿ outputs
- No feedback path exists in a purely combinational circuit
- Design flow: define function → truth table → simplify Boolean expression → draw circuit
- Ripple-carry adders are simple but slow for wide bit widths due to carry propagation delay
Related Topics
Prerequisites: Logic gates and truth tables, Boolean algebra basics, binary number system
Related Topics: Boolean simplification (Karnaugh maps), encoders and decoders, arithmetic logic units (ALUs)
Next Topics: Sequential circuits, flip-flops, and how memory changes circuit behavior