Digital-electronics 简明教程

Quine-McCluskey Tabular Method

在本章中，我们将讨论使用表格法最小化布尔表达式，该方法也称为 Quine-McCluskey method 。

In this chapter, we will discuss the minimization of Boolean expressions using a tabular method also known as Quine-McCluskey method.

奎纳-麦克拉斯基方法在最小化超过六个变量的布尔函数方面更有益。这种最小化技术克服了超过六个变量的卡诺图相关的问题。

The Quine-McCluskey method is more beneficial in minimization of Boolean functions of more than six variables. This minimization technique overcomes the issues associated with K-Map for more than six variables.

奎纳-麦克拉斯基方法的另一个主要优点是它由于可编程性而同样适合手工计算和机器计算。

Another major advantage of Quine-McCluskey method is that it is equally suitable both hand computation and machine computation, as it is programmable.

Theory of Quine-McCluskey Method

奎纳-麦克拉斯基方法是一种极小化复杂布尔表达式的系统化技术。它成为最小化大量变量的布尔表达式的合适方法。它也被称为表格法。

The Quine-McCluskey method is a systematic technique of minimizing complex Boolean expressions. It becomes a suitable method to perform minimization of Boolean expressions of large number of variables. It is also known as tabular method.

这种最小化技术基于对所有相邻项对重复使用结合定理（即 $\mathrm{XA \: + \: X\bar{A} \: = \: X}$，其中 X 是文字集合）。这个过程给出了所有真含元组，我们可以从中选择最小和式。

This minimization technique is based on the repeated use of the combining theorem (i.e., $\mathrm{XA \: + \: X\bar{A} \: = \: X}$, where X is a set of literals) on all adjacent pairs of terms. This process gives a set of all prime implicants, from which we can select a minimal sum.

Quine-McCluskey Method Procedure

使用奎因·麦克拉斯基方法最小化布尔函数的分步过程如下 −

The step-by-step procedure for minimizing a Boolean function by using the Quine McCluskey method is explained below −

Step 1 − 列出给定布尔表达式的全部极小项。

Step 1 − List all the minterms of the given Boolean expression.

Step 2 − 根据极小项对极小项进行分组。在这一步，我们将根据二进制形式中 1 的数量将所有极小项进行分组。例如，将所有不带 1 的极小项排在一起，将所有只带 1 的极小项排在一起，依此类推。极小项中的 1 的数量称为极小项的指数。将这些分组极小项写入表格的第 1 列。

Step 2 − Group the minterms. In this step, we arrange all the minterms in groups according to the number of 1s in their binary form. For example, arrange all the minterms with no 1s together, all the minterms with only one 1s together, and so on. The number of 1s in a minterm is called the index of the minterm. Write these grouped minterms in the column 1 of the table.

Step 3 − 合并极小项。在这一步，将最低指数组的每个极小项与连续组中的每个极小项进行比较。每当可能时，合并相邻组中仅在 1 位上不同的两个极小项，并将不同的位替换为连字符 (-)。这表示不管条件。此外，在已至少与一项极小项合并的每个极小项前打上勾号 (✓)。重复此过程，直至进行所有可能的极小项组合。将所有合并的极小项写入表格的第 2 列。

Step 3 − Combine minterms. In this step, compare each minterm of the lowest index group with every minterm in the succeeding group. Whenever possible, combine two minterms in adjacent groups that differ by only 1-bit and replace the differing bit by a dash (-). This represents a don’t care condition. Also, place a check mark (✓) in front of the every minterm that has been combined with at least one minterm. Repeat this process until all possible minterm combinations are made. Write all the combined minterms in the column 2 of the table.

Step 4 − 以相同的方式比较并合并上面步骤中产生的极小项。在这一步中，我们将合并仅在 1 位上不同且连字符位于相同位置的两项极小项。我们不能合并连字符在不同位置的两项极小项。

Step 4 − Compare and combine the minterms generated in the above step in the same manner. In this step, we combine two minterms which differ by only 1-bit and whose dashes are in the same position. We cannot combine two minterms having dashes in different positions.

将新生成的项写入第 3 列，并在第 2 列中已合并的每个项旁边打上勾号 (✓)。继续使用第 3、4 列中的项进行此过程，依此类推，直至无法进行进一步的合并。最后，未合并的项被称为 prime implicants 。

Write the newly generated terms in the column 3 and put a check mark (✓) next to each term that has been combined in the column 2. Continue this process with terms in column 3, 4, and so on until no further combination is possible. At the end, the terms that are not combined are called the prime implicants.

Step 5 − 列出所有真含元组并创建一个真含元组图表。如果有不管项，它不应该出现在真含元组图表中。

Step 5 − List all the prime implicants and create a prime implicant chart. If there is any don’t care, it should not appear in the prime implicant chart.

Step 6 − 选择真含元组，它们是覆盖未被任何其他真含元组覆盖的极小项的真含元组。

Step 6 − Select the essential prime implicants which are the prime implicants that cover a minterm which is not covered by any other prime implicant.

Step 7 − 合并真含元组以获得最终最小化表达式。

Step 7 − Combine the essential prime implicants to obtain the final minimized expression.

Important Terms Related Quine-McCluskey Method

在奎纳-麦克拉斯基布尔表达式最小化方法中，使用了几个术语来传达信息。以下定义了与奎纳-麦克拉斯基方法相关的一些关键术语 −

In the Quine-McCluskey method of Boolean expression minimization, several terms are used to convey information. Some key terms related to the Quine-McCluskey method are defined below −

Minterm − 极小项是布尔变量的组合，其中 1 表示真值，0 表示假值。

Minterm − A minterm is a combination of Boolean variables that has 1 for true value and 0 for false value.

Maxterm − 最大值项是布尔变量的组合，其中真值为 0，假值为 1。

Maxterm − A maxterm is a combination of Boolean variables in which true values are designated by 0s and false values are designated by 1s.

Index − 最小值项中 1 的数量称为其指数。

Index − The number of 1s in a minterm is called its index.

Prime Implicant − 无法与任何其他最小值项组合的最小值项称为素蕴含项。

Prime Implicant − A minterm that cannot be combined with any other minterm is called a prime implicant.

Essential Prime Implicant − 覆盖至少一个未被任何其他素蕴含项覆盖的最小值项的素蕴含项称为基本素蕴含项。

Essential Prime Implicant − A prime implicant that covers at least one minterm which is not covered by any other prime implicant is called an essential prime implicant.

Prime Implicant Chart − 显示素蕴含项和布尔表达式的最小值项之间的关系的图形表示称为素蕴含项图表。

Prime Implicant Chart − The graphical representation showing the relationship between the prime implicants and the minterms of the Boolean expression is called the prime implicant chart.

Don’t Care Condition − 任意条件是一个位或变量，在最小化函数期间可以忽略。在奎因-麦克卢斯基法中，它用连字符 (-) 表示。

Don’t Care Condition − A don’t care condition is a bit or variable that can be ignored during minimization of the function. In Quine-McCluskey method, it is represented by a dash (-).

这些是一些与奎因-麦克卢斯基法合作必不可少的重要术语。

These are some important terms essential to work with the Quine-McCluskey method.

现在让我们通过一个示例了解奎因-麦克卢斯基法在最小化布尔函数中的应用。

Let us now understand the application of Quine-McCluskey method to minimize a Boolean function through an example.

Example Based on Quine-McCluskey Method

使用奎因-麦克卢斯基技术最小化以下布尔函数。

Using the Quine-McCluskey technique minimize the following Boolean function.

\mathrm{f(A, B,C,D) \: = \: \sum \: m(0,1,5,7,10,14)}

Solution

下面说明了使用奎因-麦克卢斯基法最小化给定布尔函数的方法。

The minimization of given Boolean function using the Quine-McCluskey method is explained below.

Step 1 − 根据升序中 1 的数量对给定的最小值项进行分组，并将它们的二进制形式写在第 1 列。

Step 1 − Grouping the given minterms in terms of number of 1s in ascending order and writing their binary form in column 1.

Column 1
Index
Min Term
Binary Form
A
B
C
D
I0
0
0
0
0
0
I1
1
0
0
0
1
I2
5
0
1
0
1
10
1
0
1
0
I3
7
0
1
1
1
14
1
1
1
0

Step 2 − 比较和组合第 1 列的最小值项。

Step 2 − Comparing and combining minterms of the column 1.

Column 1	Column 2
Index	Min Term	Binary Form
	Pairs	A
B	C	D
	A	B
C	D
	I0	0
0	0	0
0	✓	0, 1 (1)
0	0	0
-	P	I1
1	0	0
0	1	✓
I2	5	0
1	0	1
✓	1, 5 (4)	0
−	0	1
Q	10	1
0	1	0
✓	5, 7 (2)	0
1	−	1
R	I3	7
0	1	1
1	✓	14
1	1	1
0	✓	10, 14 (4)
1	−	1

我们发现第 2 列中没有可以与两个相邻组之间的任何其他项组合的项。因此，它们都是素蕴含项。

We can see there is no term that can be combined with any other term in the column 2 between two adjacent groups. Thus, all of them are prime implicants.

Step 3 − 创建素蕴含项图表。

Step 3 − Creating the prime implicant chart.

PI	Minterms	0	1	5	7	10	14
P	0, 1 (1)	x	x
Q	1, 5 (4)		x	x
R	5, 7 (2)			x	x
S	10, 14 (4)					x	x

我们可以从素蕴含项图表中看到，最小值项 m10 和 m14 仅由 S 覆盖。因此，S 是一个基本素蕴含项。还可以观察到函数的剩余最小值项由素蕴含项 P 和 R 的最小集合覆盖。

We can see from the prime implicant chart that the minterms m10 and m14 are covered by S only. Hence, S is an essential prime implicant. It can also be observed that the remaining minterms of the function are covered by the minimal set of prime implicants P and R.

因此，最小表达式将为：

Therefore, the minimal expression will be,

\mathrm{f_{min} \: = \: P \: + \: R \: + \: S \: = \: (000 \: − \: ) \: + \: (01 \: − \: 1) \: + \:(1 \: − \: 10)}

\mathrm{\Rightarrow f_{min} \: = \: \overline{ABC} \: + \: \overline{A}BD \: + \: AC\overline{D}}

这是针对给定布尔函数的最小布尔表达式，它可以使用 AND、OR 和 NOT 门实现。

This is minimal Boolean expression for the given Boolean function and it can be realized using AND, OR, and NOT gates.

Advantages of Quine-McCluskey Method

与其它最小化技术（例如卡诺图）相比，奎因-麦克拉斯基方法具有以下几个优势。奎因-麦克拉斯基方法的一些主要优势如下所列：

The Quine-McCluskey method offers several advantages over other minimization techniques such as Karnaugh Map. Some of the key advantages of the Quine-McCluskey method are listed below −

The Quine-McCluskey method provides a systematic minimization process to find a minimal version of a complex Boolean expression.
It can be applied to Boolean functions of large number of variables where, the K-map technique becomes impractical.
It is suitable for both hand computation and computerized computation.
The Quine-McCluskey method is based on a systematic algorithm that helps to reduce human errors.
It can also be applied to Boolean functions with don’t care conditions, i.e., incomplete Boolean functions.

Disadvantages of Quine-McCluskey Method

但是，奎因-麦克拉斯基方法是一种强大的简化技术，它可以最小化布尔函数，并且比其它最小化技术具有几个优势。

However, the Quine-McCluskey method is a powerful simplification technique to minimize Boolean functions having several advantages over other minimization techniques.

但是，它也有一些缺点，其中一些缺点如下所列：

But, it also has certain disadvantages, some of which are listed below −

The primary disadvantage of the Quine-McCluskey method is computational complexity. It is because, we have to check all the possible combinations of minterms.
Although the Quine-McCluskey method is better than K-Map for large number of variables. But it also becomes impractical for vary large number of variables, typically more than 7 variables.
The Quine-McCluskey method involves extensive manual computation that makes it tedious and prone to human error.
The Quine-McCluskey method is not much effective for certain types of Boolean functions.
As the Quine McCluskey method involves an algorithmic approach for minimization rather than graphical approach. This makes it less intuitive.

Applications of Quine-McCluskey Method

奎因-麦克拉斯基方法是最有效的最小化技术之一，它应用于布尔代数。对于变量数目较大的复杂布尔函数，它提供了一种系统化方法来实现最小化。奎因-麦克拉斯基方法的一些主要应用如下所列：

The Quine-McCluskey method is one of the most effective minimization techniques in Boolean algebra. It provides a systematic approach to minimized complex Boolean functions of large number of variables. Some major applications of the Quine-McCluskey method are given below −

Quine-McCluskey method is used to design and optimize digital circuits and systems. It helps reducing the number of logic gates used in the digital circuits.
It is also used in computer programming to optimize conditional logics for better efficiency and faster speed.
In digital signal processing, the Quine-McCluskey method is used to simplify Boolean expressions to develop efficient processing algorithms.
Quine-McCluskey method is used to design efficient state machine.

Conclusion

总之，蒯因 - 麦克卢斯基方法是一种系统且具有算法性的方法，用于化简复杂的布尔表达式。它是针对大量变量的布尔函数的一种有效的最小化技术。

In conclusion, the Quine-McCluskey method is a systematic and algorithmic approach for simplifying complex Boolean expressions. It is an effective minimization technique for Boolean functions of large number of variables.

蒯因 - 麦克卢斯基方法的最大优势在于它同时支持手动计算和机器计算，即它可以编程。但是，该方法涉及相对复杂的计算，这使其变得繁琐。

The greatest advantage of the Quine-McCluskey method is that it supports both hand computation and machine computation, i.e., it is programmable. However, this method involves relatively complex computation which makes it tedious.