Quine and McCluskey method

The method according to Quine and McCluskey (QMCV, according to Willard Van Orman Quine and Edward J. McCluskey ) is a method to minimize Boolean functions . The core of the process has already been fully described by Quine. McCluskey's refinements essentially concern practical algorithmic feasibility. The minimization is u. a. This is important because it makes the hardware implementation easier and therefore cheaper. The advantage of this method is that it can be included in a computer program relatively easily and thus executed using a computer . In the worst case, the method needs exponential running time to find a minimal solution. The procedure always finds a minimal solution, but it is possible that there are other (equivalent) solutions that are not found. Since the underlying problem is NP-complete , there is no method that is efficient in this sense under the assumption that P ≠ NP holds.

The procedure initially only refers to function representations in canonical disjunctive normal form (KDNF). Expressions in conjunctive normal form (CNF) can, however, first be converted into a DNF without further ado by negating the function under consideration, then minimized as described below and finally transformed back into a CNF by another negative.

Description of the procedure

principle

The basic principle of the Quine-McCluskey method is based on the following property of conjunction terms : If two conjunction terms linked by disjunction differ only through the negation of a single variable, these two terms can be merged and the variable concerned can be removed. This property is explained by the following algebraic relationship:

${\displaystyle x_{1}\cdot \ldots \cdot x_{i}\cdot \ldots \cdot x_{n}+x_{1}\cdot \ldots \cdot {\overline {x_{i}}}\cdot \ldots \cdot x_{n}}$

${\displaystyle =x_{1}\cdot \ldots \cdot (x_{i}+{\overline {x_{i}}})\cdot \ldots \cdot x_{n}}$

${\displaystyle =x_{1}\cdot \ldots \cdot x_{i-1}\cdot 1\cdot x_{i+1}\cdot \ldots \cdot x_{n}}$

${\displaystyle =x_{1}\cdot \ldots \cdot x_{i-1}\cdot x_{i+1}\cdot \ldots \cdot x_{n}}$

In this context it is useful to consider a Boolean function from the point of view of set theory. (Only fully defined functions are considered here):

• A Boolean function can be represented as a set of conjunctions of all independent variables. This corresponds to the function values ​​of the truth table and is the total amount. For n independent variables, their cardinality is elements. ${\displaystyle 2^{n}}$
• The elements are also called elementary conjunctions. So this is a single function value.
• This amount is divided into two subsets. A part that makes the function a true statement and a part that does not fulfill the function. (When using '0' and '1', the subset of the '1' and the subset of the '0' in the truth table).
• A conjunction is a subset of this total. There are possible conjunctions. (including the total amount itself). ${\displaystyle 3^{n}}$

An element of the total set is an element of a conjunction if the assignment of the variables contained in the conjunction with the corresponding values ​​of the element (elementary conjunction) makes the conjunction a true statement.

Example:

${\displaystyle x_{0}\cdot x_{1}\cdot {\overline {x_{2}}}\in x_{0}\cdot x_{1}}$

${\displaystyle {\overline {x_{0}}}\cdot x_{1}\cdot {\overline {x_{2}}}\in \!\!\!\!\!/\,x_{0}\cdot x_{1}}$

Create the canonical disjunctive normal form

The Quine-McCluskey method is based on an algebraic representation of the formula in canonical disjunctive normal form (KDNF). Such a KDNF consists of a disjunction of minterms . Another representation must first be brought into this form.

Since this step can generate up to 20,000 terms, there are also variants of the method that only require a DNF (instead of a KDNF), such as B. the resolvent method . ${\displaystyle 2^{n}}$

Finding the prime terms

All minterms are now sorted by ascending class and listed in a table. The class of a conjunction is the number of non-negated variables that occur in it.

We now compare all minterms of neighboring classes to see whether they differ in pairs by a single negation. If this is the case, the two terms are merged into a new term (which is of course no longer a minterm) and entered in a second table. The two terms used are marked (e.g. with a tick), but should still be used for comparisons.

The method is applied recursively in several stages to the merged terms until no further merging is possible. Make sure that both terms (table lines) contain the same variables. During this process, some terms remain that could not be merged. These terms are called Primterme or Primkonjunktionen.

From the second minimization level onwards, the same conjunctions occur several times, but they only need to be entered once in the new table.

Creation of the primterm table

It is entirely possible that not all prime terms are needed. In order to find out which prime terms you absolutely need, you create a so-called prim term table. The minter terms are used as the column headers of the table. The prime terms are entered as line headers. The individual cells in the table are therefore the crossing points of certain minterms with certain primterms.

You always enter a mark in the respective cell if the minterm is an element of the primterm (see below).

Dominance check

During the dominance check, obsolete rows and columns are determined.

Column dominance check

The columns are compared in pairs to determine whether a column does not exist in which the marked primer terms are a subset of the marked primer terms of the other column. If this is the case, the column with the superset can be deleted, because all conjunctions must be recorded and therefore the conjunction with the superset is also recorded by selecting the conjunction with the subset.

Example:

In a table are u. A. the two columns

${\displaystyle K_{a}=P_{1}+P_{2}+P_{4}}$

${\displaystyle K_{b}=P_{1}+P_{4}}$

It can be deleted here because it dominates completely. is therefore obsolete and is no longer taken into account from now on. ${\displaystyle K_{a}}$ ${\displaystyle K_{b}}$ ${\displaystyle K_{a}}$

Line dominance check

Now compare the rows (primer terms) of the table in pairs to see whether there is a row in which the marked minterms are a subset of the marked minterms of the other row. If this is the case, the primer term with the subset can be deleted, because the other primer term can be used as a substitute for each marking of the deleted primer term. The relation here is exactly the opposite of that of the column dominance.

Example:

In a table are u. A. the two lines

${\displaystyle P_{a}=K_{1}+K_{2}+K_{6}+K_{7}}$

${\displaystyle P_{b}=K_{1}+K_{2}}$

It can be deleted here because it is completely dominated by. is therefore obsolete and is no longer taken into account from now on. ${\displaystyle P_{b}}$ ${\displaystyle P_{a}}$ ${\displaystyle P_{b}}$

These two tests are repeated alternately until no row / column can be deleted in one test, but at least once each.

Selection of the prime terms

The remaining prime terms must now be selected in such a way that all minter terms are covered. There may be several (possibly equivalent) options for this. One chooses as few and small prime terms as possible, since one would like to achieve an optimized function that can ultimately be technically implemented with as few switching gates as possible .

example

Here is an example to explain the method:

Representation as canonical disjunctive normal form

We assume a Boolean function with four input variables , whose canonical disjunctive normal form looks like this: ${\displaystyle f}$ ${\displaystyle x_{0}\dots x_{3}}$

${\displaystyle \,f(x_{0},x_{1},x_{2},x_{3})=Y=}$

${\displaystyle {\begin{matrix}\\{\overline {x_{0}}}*{\overline {x_{1}}}*{\overline {x_{2}}}*{\overline {x_{3}}}\,+\,{x_{0}}*{\overline {x_{1}}}*{\overline {x_{2}}}*{\overline {x_{3}}}\,+\,\\{\overline {x_{0}}}*{\overline {x_{1}}}*{x_{2}}*{\overline {x_{3}}}\,+\,{x_{0}}*{\overline {x_{1}}}*{x_{2}}*{\overline {x_{3}}}\,+\,\\{\overline {x_{0}}}*{x_{1}}*{x_{2}}*{\overline {x_{3}}}\,+\,{x_{0}}*{x_{1}}*{x_{2}}*{\overline {x_{3}}}\,+\,\\{\overline {x_{0}}}*{\overline {x_{1}}}*{\overline {x_{2}}}*{x_{3}}\,+\,{x_{0}}*{\overline {x_{1}}}*{\overline {x_{2}}}*{x_{3}}\,+\,\\{x_{0}}*{x_{1}}*{\overline {x_{2}}}*{x_{3}}\,+\,{x_{0}}*{x_{1}}*{x_{2}}*{x_{3}}\ \ \ \end{matrix}}}$

In another notation:

${\displaystyle Y=m_{0}\,+\,m_{1}\,+\,m_{4}\,+\,m_{5}\,+\,m_{6}\,+\,m_{7}\,+\,m_{8}\,+\,m_{9}\,+\,m_{11}\,+\,m_{15}}$

Finding the prime terms

The selection tables

The output table:	The first summary gives:	Only lines may be combined that have the "-" in the same positions (!)	Third summary
Table 1 ${\displaystyle m_{x}}$ ${\displaystyle x_{3}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{0}}$ OK ${\displaystyle m_{0}}$ 0 0 0 0 ✓ ${\displaystyle m_{1}}$ 0 0 0 1 ✓ ${\displaystyle m_{4}}$ 0 1 0 0 ✓ ${\displaystyle m_{8}}$ 1 0 0 0 ✓ ${\displaystyle m_{5}}$ 0 1 0 1 ✓ ${\displaystyle m_{6}}$ 0 1 1 0 ✓ ${\displaystyle m_{9}}$ 1 0 0 1 ✓ ${\displaystyle m_{7}}$ 0 1 1 1 ✓ ${\displaystyle m_{11}}$ 1 0 1 1 ✓ ${\displaystyle m_{15}}$ 1 1 1 1 ✓	Table 2 ${\displaystyle m_{x}+m_{y}}$ ${\displaystyle x_{3}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{0}}$ OK ${\displaystyle m_{0}+m_{1}}$ 0 0 0 - ✓ ${\displaystyle m_{0}+m_{4}}$ 0 - 0 0 ✓ ${\displaystyle m_{0}+m_{8}}$ - 0 0 0 ✓ ${\displaystyle m_{1}+m_{5}}$ 0 - 0 1 ✓ ${\displaystyle m_{1}+m_{9}}$ - 0 0 1 ✓ ${\displaystyle m_{4}+m_{6}}$ 0 1 - 0 ✓ ${\displaystyle m_{4}+m_{5}}$ 0 1 0 - ✓ ${\displaystyle m_{8}+m_{9}}$ 1 0 0 - ✓ ${\displaystyle m_{5}+m_{7}}$ 0 1 - 1 ✓ ${\displaystyle m_{6}+m_{7}}$ 0 1 1 - ✓ ${\displaystyle m_{9}+m_{11}}$ 1 0 - 1 P 1 ${\displaystyle m_{7}+m_{15}}$ - 1 1 1 P 2 ${\displaystyle m_{11}+m_{15}}$ 1 - 1 1 P 3	Table 3 ${\displaystyle m_{w}+m_{x}+m_{y}+m_{z}}$ ${\displaystyle x_{3}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{0}}$ OK ${\displaystyle m_{0}+m_{1}+m_{4}+m_{5}}$ 0 - 0 - P 4 ${\displaystyle m_{0}+m_{1}+m_{8}+m_{9}}$ - 0 0 - P 5 ${\displaystyle m_{4}+m_{6}+m_{5}+m_{7}}$ 0 1 - - P 6	No further summaries possible.

There are therefore six prime terms:

${\displaystyle \,P_{1}=x_{0}*{\overline {x_{2}}}*x_{3}=m_{9}+m_{11}}$

${\displaystyle \,P_{2}=x_{0}*x_{1}*x_{2}=m_{7}+m_{15}}$

${\displaystyle \,P_{3}=x_{0}*x_{1}*x_{3}=m_{11}+m_{15}}$

${\displaystyle \,P_{4}={\overline {x_{1}}}*{\overline {x_{3}}}=m_{0}+m_{1}+m_{4}+m_{5}}$

${\displaystyle \,P_{5}={\overline {x_{1}}}*{\overline {x_{2}}}=m_{0}+m_{1}+m_{8}+m_{9}}$

${\displaystyle \,P_{6}=x_{2}*{\overline {x_{3}}}=m_{4}+m_{5}+m_{6}+m_{7}}$

Creation of the primterm table

The primterm table looks like this:

	${\displaystyle m_{0}}$	${\displaystyle m_{1}}$	${\displaystyle m_{4}}$	${\displaystyle m_{5}}$	${\displaystyle m_{6}}$	${\displaystyle m_{7}}$	${\displaystyle m_{8}}$	${\displaystyle m_{9}}$	${\displaystyle m_{11}}$	${\displaystyle m_{15}}$
${\displaystyle P_{1}}$								•	•
${\displaystyle P_{2}}$						•				•
${\displaystyle P_{3}}$									•	•
${\displaystyle P_{4}}$	•	•	•	•
${\displaystyle P_{5}}$	•	•					•	•
${\displaystyle P_{6}}$			•	•	•	•

Dominance check

The first column dominance check shows:

• Deletion of , and because of, column ${\displaystyle m_{0}}$ ${\displaystyle m_{1}}$ ${\displaystyle m_{9}}$ ${\displaystyle m_{8}}$
• Deletion of , and because of, column ${\displaystyle m_{4}}$ ${\displaystyle m_{5}}$ ${\displaystyle m_{7}}$ ${\displaystyle m_{6}}$

Then the table looks like this:

	${\displaystyle m_{6}}$	${\displaystyle m_{8}}$	${\displaystyle m_{11}}$	${\displaystyle m_{15}}$
${\displaystyle P_{1}}$			•
${\displaystyle P_{2}}$				•
${\displaystyle P_{3}}$			•	•
${\displaystyle P_{4}}$
${\displaystyle P_{5}}$		•
${\displaystyle P_{6}}$	•

The line dominance check gives:

• Delete from (blank). ${\displaystyle P_{4}}$
• Delete because of ${\displaystyle P_{2}}$ ${\displaystyle P_{3}}$
• Delete because of ${\displaystyle P_{1}}$ ${\displaystyle P_{3}}$

So we get:

	${\displaystyle m_{6}}$	${\displaystyle m_{8}}$	${\displaystyle m_{11}}$	${\displaystyle m_{15}}$
${\displaystyle P_{3}}$			•	•
${\displaystyle P_{5}}$		•
${\displaystyle P_{6}}$	•

A second column dominance check shows:

• Delete because of ${\displaystyle m_{15}}$ ${\displaystyle m_{11}}$

Result:

	${\displaystyle m_{6}}$	${\displaystyle m_{8}}$	${\displaystyle m_{11}}$
${\displaystyle P_{3}}$			•
${\displaystyle P_{5}}$		•
${\displaystyle P_{6}}$	•

A second line dominance check reveals no more deletions. This ends the dominance test.

Selection of the prime terms

The selection of suitable prime terms is now very easy, since there is only one possibility: The prime terms , and are required . ${\displaystyle P_{3}}$ ${\displaystyle P_{5}}$ ${\displaystyle P_{6}}$

Linking the selected prime terms

Now the selected prime terms have to be linked to the solution equation using a disjunction:

${\displaystyle \,Y=P_{3}\ +P_{5}\ +\ P_{6}}$

${\displaystyle \,Y=x_{0}*x_{1}*x_{3}\quad +\quad {\overline {x_{1}}}\ *{\overline {x_{2}}}\quad +\quad x_{2}*{\overline {x_{3}}}}$

annotation

The problem of choosing a minimal number of prim terms from the primer table is NP-complete ; d. that is, for many cases, no much better method is known than trying all possible choices. It is therefore advisable to only determine the minimum approximately. For example, you first select the columns with only one mark (these are absolutely necessary), then look for suitable terms in the columns with few markings or in lines with many markings.

The method has advantages over the Karnaugh-Veitch diagram (KVD) , especially with a higher number of variables . As a rule of thumb, the KVD is better up to five variables, the QMCV is better from six variables.

See also

• Buchberger algorithm

Web links

• The Quine-McCluskey Optimizer
• An applet that demonstrates the steps in the process
• JavaScript program of the University of Marburg