Prof. Dr. Thorsten Jungmann (last updated 2026-10-25)
Relates to DET-04 Algorithmic minimization of functions with many inputs and hazard analysis
Task
The Karnaugh map relies on your eye, the Quine–McCluskey algorithm on fixed rules. The following questions are about functions with many inputs.
a) How many rows does the truth table of a function with 4, 6, 10 and 20 inputs have? Up to how many inputs is the Karnaugh map well suited to the human eye?
b) In part 1, the algorithm compares each term only with the terms of the next group. Why can two terms of groups that are not consecutive never unite? Explain it with the codes 0100 and 1101.
c) How does the algorithm treat don’t cares in part 1 and in part 2, and why?
d) A synthesis tool is to minimize a function with 30 inputs. Why does it not use the Quine–McCluskey algorithm, and what does it use instead? What is the price?
Solution
a) 16, 64, 1 024 and 1 048 576 rows; up to five inputs according to Reichardt, while Donzellini and his co-authors already leave more than four inputs to algorithms
b) two codes that differ in exactly one position differ by exactly one in their number of ones; 0100 (one 1) and 1101 (three ones) differ in two positions
c) in part 1, they count as ones, so that the united terms become as large as possible; in part 2, they get no column, because they need not be covered
d) its effort grows exponentially with the number of inputs: rows, while it is realistic for 15 to 20 inputs at most; instead, a heuristic method such as the Espresso heuristic logic minimizer, whose result can be slightly off the optimum in individual cases