Combinational logic: minimization and hazards
The shortest expression is not always the best: it can let the output drop for a few nanoseconds when it should not. Minimizing well means finding the minimal expression and knowing when to add a term to it.
01From the truth table to the minimal expression
Gates, Boolean algebra and the step from a truth table to a circuit are covered in the page on combinational logic in the Electronics Technician program. This unit starts from there and asks the engineering question: among all the circuits that implement the same function, which one is the best?
Read straight from the table, any function comes out as a canonical sum of products: one AND term for each row that equals 1, with all four variables. It is correct and almost always needlessly expensive. Minimizing it reduces three things at once: the number of gates (the cost and the area on a chip), the number of inputs per gate, and the depth of the circuit, which is what decides how fast it responds.
02The Karnaugh map
The Karnaugh map rearranges the truth table into a grid where two neighboring cells differ in a single variable. To achieve this, rows and columns are numbered in Gray code —00, 01, 11, 10— and opposite edges are neighbors too: the map is really a torus. Two neighboring ones can be grouped because the variable that changes between them does not matter: \( AB + A\overline B = A \).
| Rule | Why |
|---|---|
| Groups have 1, 2, 4, 8 or 16 cells | Each doubling eliminates exactly one variable |
| Groups are rectangles, and can wrap around the edges | Opposite edges differ in a single variable |
| The largest possible group is preferred | More cells, fewer literals in the term |
| Groups can overlap | A 1 covered twice does not change the function (\( X + X = X \)) |
| Don’t-cares (X) are used only if they enlarge a group | They do not need to be covered |
Every group that is not contained in a larger one is a prime implicant. Those that cover some 1 that no other group covers are essential and must be included; the rest are chosen to complete the cover with the fewest possible terms.
03Quine-McCluskey: the same method, for a computer
The map works by eye up to five or six variables; beyond that it becomes impossible to read. The Quine-McCluskey method does the same thing in tabular form: it combines in pairs the terms that differ in one bit, repeats until nothing more can be combined, and what is left uncombined are the prime implicants. It then solves a covering problem: choosing the smallest set of primes that covers all the ones.
That second stage is a set-cover problem, and it grows explosively with the number of variables. That is why real synthesis tools —from ESPRESSO in the 1980s to those that compile for an FPGA today— use heuristics that find very good solutions without guaranteeing the optimal one. The lab on this page applies the full Quine-McCluskey method, which with four variables is solved exactly.
Click or tap each cell to cycle it from 0 to 1, from 1 to don’t-care (X) and back to 0, or choose an example. The lab finds the prime implicants with Quine-McCluskey, chooses the minimum cover, draws it on the map and warns you if any static hazard remains.
04Hazards: when the minimal expression fails
Boolean algebra assumes that signals change instantaneously. Real gates take time: a 74HC inverter on the order of 10 ns. If the same variable reaches an OR gate by two paths with different delays —one direct and one through an inverter—, during those nanoseconds the two terms that use it can both be 0 at once, and the output, which should have stayed at 1, drops for an instant. That is a static-1 hazard, and the spurious pulse it produces is called a glitch.
On the map, the hazard is easy to spot: it appears when two neighboring ones are covered by different groups with no group containing both of them. In a combinational circuit that feeds another combinational circuit the glitch usually does not matter; in one that drives the clock or the reset of a flip-flop, or an enable line, it can cause an intermittent fault that is very hard to find. That is why synchronous design —the subject of the next unit— samples the outputs only once they have settled.
05Delay and critical path
The output of a combinational circuit is valid only after the signal has traveled the slowest path, the critical path. Minimizing gates and minimizing delay do not always go together, and the adder shows this best.
| n-bit adder | How the carry propagates | Delay | Gates |
|---|---|---|---|
| Ripple-carry adder | Each stage waits for the carry from the previous one | Grows as \( n \) | Few |
| Carry-lookahead adder | Computes all the carries in parallel with generate and propagate terms | Grows as \( \log n \) | Many more |
A 64-bit ripple-carry adder would need on the order of 128 gate delays; a carry-lookahead one, a few levels. Every modern processor pays in area to gain speed right there.
06Where it shows up in electronics
| Case | What is used from this unit |
|---|---|
| Seven-segment decoder | Don’t-cares: the BCD codes that do not exist simplify each segment |
| FPGA synthesis | The tool minimizes on its own, and then maps the result onto lookup tables |
| Memory enable logic | A glitch on the chip select can write data where it should not |
| ALU of a microprocessor | Carry lookahead to keep addition fast |
07In the lab
Minimize the seven segments of a BCD decoder using the don’t-cares. Build one of them with 74HC gates and verify it with the ten digits.
Build \( \overline{B}D + BC \) with real gates, hold \( C = D = 1 \), toggle \( B \) with a generator and look with the oscilloscope for the spurious pulse on the output. Add \( CD \) and check that it disappears.
Solve the four-variable majority function by tabulation and compare the prime implicants with those the lab finds.
08Common mistakes
- Numbering the map in ordinary binary. With 00, 01, 10, 11 neighboring cells do not differ in a single bit and the groups stop being valid.
- Forgetting that the edges are neighbors. The four corners of a four-variable map form a group.
- Making groups of three or six. Only powers of two.
- Covering the don’t-cares as if they were ones. They are used if they help; they do not need to be covered.
- Believing the minimal expression is always the best. It can have hazards that one with an extra term does not have.
09Self-assessment
Why is the Karnaugh map numbered in Gray code?
So that two neighboring cells differ in a single variable, which is what makes it possible to group them.
What is an essential prime implicant?
A prime implicant that covers at least one 1 that no other prime covers; it must appear in every minimal expression.
What does a don’t-care do on the map?
It can be taken as 1 if it enlarges a group, or ignored if it does not: the specification does not require any value for that combination.
When is there a static-1 hazard?
When two neighboring ones end up in different groups with no group covering both of them: when the variable that separates them changes, the output can drop for an instant.
Why is a carry-lookahead adder faster?
Because it computes the carries in parallel instead of waiting for each stage to pass its carry to the next.
10Further reading
- M. Morris Mano and Michael D. Ciletti. Digital Design. 6th ed., Pearson, 2018. Karnaugh maps, Quine-McCluskey and combinational blocks, with the classic approach of digital techniques courses.
- John F. Wakerly. Digital Design: Principles and Practices. 5th ed., Pearson, 2018. The most careful treatment of hazards and of the real delays of logic families.
- Robert K. Brayton et al. Logic Minimization Algorithms for VLSI Synthesis. Kluwer, 1984. The ESPRESSO book: how a program minimizes when there are too many variables for Quine-McCluskey.