Exercise DET-04.03 – Functions with many inputs (Solution)

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?

◀️ Back to the task

---

Solution

Given

Given explicitly:

• a) functions with 4, 6, 10 and 20 inputs
• b) the codes 0100 and 1101
• d) a function with 30 inputs and a synthesis tool that minimizes it

Known:

• Number of rows of a truth table, the map for six inputs and how far the map suits the eye (DET-04)
• Codes and groups: the group of a code is the number of its ones (DET-04)
• Part 1: terms that differ in exactly one position unite (DET-04)
• Don’t cares in the algorithm, growth of the effort (DET-04)
• Exact and heuristic methods, the Espresso heuristic logic minimizer (DET-04)

Required

a) the number of rows for 4, 6, 10 and 20 inputs and the number of inputs up to which the Karnaugh map suits the eye
b) the reason why terms of groups that are not consecutive never unite, shown with 0100 and 1101
c) how the algorithm treats don’t cares in part 1 and in part 2, with the reasons
d) the reason why the synthesis tool does not use the Quine–McCluskey algorithm, what it uses instead and the price

a) Rows and cells

Each input doubles the number of combinations, so a function with $n$ inputs has $2^n$ rows in its truth table, and its Karnaugh map has as many cells (DET-04, 3.1):

$$\begin{array}{rl}{2}^4& =16\\ 2^6& =64\\ 2^{10}& =1024\\ 2^{20}& =1048576\end{array}$$

According to the lesson, Reichardt considers the map well suited to the human eye for up to five inputs; Donzellini and his co-authors draw the line even earlier and leave the minimization of functions with more than four inputs to algorithms on a computer (DET-04, 3.1). With six inputs, the map consists of four maps for four inputs, and a cell has neighbours not only next to it but also in the other maps; finding the largest loops by eye then becomes error-prone.

Check by splitting the exponent: 20 inputs are twice 10, so $2^{20}=2^{10}\cdot 2^{10}=1024\cdot 1024=1048576$ ✓

b) Consecutive groups

The group of a code is the number of its ones (DET-04, 2.1). If two codes differ in exactly one position, one of them has a 1 there and the other a 0; in all other positions, they agree. The first code therefore has exactly one 1 more than the second, and the two codes lie in consecutive groups.

The code 0100 has one 1 and lies in group 1; the code 1101 has three ones and lies in group 3. Each position in which two codes differ changes the number of ones by one. For a difference of two in the number of ones, the codes must therefore differ in at least two positions. Indeed, 0100 and 1101 differ in the first and in the fourth position, so they cannot unite. Comparing only consecutive groups therefore misses no pair and saves many comparisons.

c) Don’t cares

In part 1, the don’t cares count as ones while terms are united, so that the united terms become as large as possible (DET-04, 3.2). A larger term has fewer literals and needs a gate with fewer inputs.

In part 2, the don’t cares get no column in the prime implicant chart, because they need not be covered: for these combinations, the output does not matter (DET-04, 3.2). A prime implicant that contains only don’t cares therefore has nothing to cover and is left out of the minimal disjunctive normal form (DNF).

d) Thirty inputs

With every further input, the number of rows doubles, and the effort of the algorithm grows exponentially with the number of inputs (DET-04, 3.2). With 30 inputs, the truth table has this many rows:

$$2^{30}=1073741824$$

According to the lesson, the Quine–McCluskey algorithm can realistically be computed for 15 to 20 inputs at most (DET-04, 3.2). A synthesis tool therefore uses a heuristic method for large functions, such as the Espresso heuristic logic minimizer (DET-04, 3.3). It works with simplifying assumptions and needs much less effort. The price: as a rule, it reaches the same result as the exact algorithm, but in individual cases, the solution that it finds is slightly off the optimum.

Check by splitting the exponent: $2^{30}=2^{10}\cdot 2^{20}=1024\cdot 1048576=1073741824$ ✓