Combinational Circuits
The structure of a combinational circuit: n inputs, m outputs, gates, no memory.
Description
A combinational circuit has n input variables, logic gates, and m output variables; each output is a Boolean function of the inputs. There are no storage elements and no feedback paths, so for every input combination there is exactly one output combination.
- n binary inputs → 2ⁿ possible input combinations.
- m binary outputs, each a function of the inputs.
- Only logic gates inside — no flip-flops/latches.
- No feedback loops permitted.
- Fully described by m Boolean functions / one truth table.
- Deterministic: one output per input combination.
- Steady-state output reached after propagation delay.
- Glitches/hazards can appear transiently before settling.
- Analysis recovers functions from a given circuit.
- Design synthesizes a circuit from required functions.
At a glance
What
An interconnection of gates with n inputs and m outputs and no memory.
Why
It is the formal object the analysis/design procedures operate on.
How
Wire gates so each of m outputs is a Boolean function of the n inputs.
Where
Every combinational block in a datapath.
When
Whenever you formalize a memoryless logic block.
Think of it like…
A combinational circuit is a function machine: drop in an input tuple, exactly one output tuple falls out, every time.
Structure
- n binary inputs → 2ⁿ possible input combinations.
- m binary outputs, each a function of the inputs.
- Only logic gates inside — no flip-flops/latches.
- No feedback loops permitted.
- Fully described by m Boolean functions / one truth table.
Implications
- Deterministic: one output per input combination.
- Steady-state output reached after propagation delay.
- Glitches/hazards can appear transiently before settling.
- Analysis recovers functions from a given circuit.
- Design synthesizes a circuit from required functions.
Sizing
| Quantity | Value |
|---|---|
| Inputs | n |
| Input combinations | 2ⁿ |
| Outputs | m |
Real-world applications
The 5 Whys
- 1
Why define structure? To analyze and design rigorously.
- 2
Why no feedback? Feedback creates state.
- 3
Why m functions? Each output is its own Boolean function.
- 4
Why care about hazards? Transient glitches before settling.
- 5
Root cause: a memoryless gate network maps each input tuple to one output tuple.
Cheat sheet
Working principle
- Wire gates so each of m outputs is a Boolean function of the n inputs.
- An interconnection of gates with n inputs and m outputs and no memory.
Formulas & Boolean expressions
- n binary inputs → 2ⁿ possible input combinations.
- Inputs = n
- Input combinations = 2ⁿ
- Outputs = m
Key facts
- n binary inputs → 2ⁿ possible input combinations.
- Deterministic: one output per input combination.
Why it exists
- Root cause: a memoryless gate network maps each input tuple to one output tuple.