Quine-McCluskey 表格方法

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

Quine-McCluskey 方法更有利于最小化超过六个变量的布尔函数。这种最小化技术克服了与超过六个变量的 K-Map 相关的问题。

Quine-McCluskey 方法的另一个主要优点是它同样适用于手工计算和机器计算，因为它是可编程的。

Quine-McCluskey 方法的理论

Quine-McCluskey 方法是最小化复杂布尔表达式的系统技术。它成为执行大量变量的布尔表达式最小化的合适方法。它也被称为表格方法。

这种最小化技术基于对所有相邻的项对重复使用组合定理(即 $\mathrm{XA \: + \: X\bar{A} \: = \: X}$，其中 X 是一组文字)。此过程给出了所有素蕴涵项的集合，我们可以从中选择最小和。

Quine-McCluskey 方法程序

使用 Quine McCluskey 方法最小化布尔函数的分步程序如下 −

步骤 1 − 列出给定布尔表达式的所有最小项。

步骤 2 − 将最小项分组。在此步骤中，我们根据二进制形式中 1 的数量将所有最小项分组排列。例如，将所有没有 1 的最小项排在一起，将所有只有一个 1 的最小项排在一起，依此类推。最小项中 1 的数量称为最小项的索引。将这些分组的最小项写在表格的第 1 列中。

步骤 3 − 组合最小项。在此步骤中，将最低索引组的每个最小项与后续组中的每个最小项进行比较。尽可能将相邻组中仅相差 1 位的两个最小项组合在一起，并用破折号 (-) 替换不同的位。这表示不关心条件。此外，在每个已与至少一个最小项组合的最小项前面放置一个复选标记 (✓)。重复此过程，直到完成所有可能的最小项组合。将所有合并的最小项写在表格的第 2 列中。

步骤 4 − 以相同的方式比较和合并上一步中生成的最小项。在此步骤中，我们将两个仅相差 1 位且破折号位于相同位置的最小项合并。我们不能合并两个破折号位于不同位置的最小项。

将新生成的项写在第 3 列中，并在第 2 列中已合并的每个项旁边标记 (✓)。继续对第 3、4 列中的项执行此过程，直至无法再进行合并。最后，未合并的项称为 素蕴涵项。

步骤 5 − 列出所有素蕴涵项并创建素蕴涵项图表。如果有任何无关项，则不应出现在素蕴涵项图中。

步骤 6 − 选择基本素蕴涵项，即覆盖未被任何其他素蕴涵项覆盖的最小项的基本蕴涵项。

步骤 7 − 组合基本素蕴涵项以获得最终的最小化表达式。

与 Quine-McCluskey 方法相关的重要术语

在布尔表达式最小化的 Quine-McCluskey 方法中，使用几个术语来传达信息。与 Quine-McCluskey 方法相关的一些关键术语定义如下 −

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

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

索引 − 最小项中 1 的数量称为其索引。

素蕴涵项 − 不能与任何其他最小项组合的最小项称为素蕴涵项。

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

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

无关条件 − 无关条件是在函数最小化期间​​可以忽略的位或变量。在 Quine-McCluskey 方法中，它用破折号 (-) 表示。

这些是使用 Quine-McCluskey 方法所必需的一些重要术语。

现在让我们通过一个例子来了解 Quine-McCluskey 方法在最小化布尔函数中的应用。

基于 Quine-McCluskey 方法的示例

使用 Quine-McCluskey 技术最小化以下布尔函数。

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

解决方案

解释了使用 Quine-McCluskey 方法最小化给定布尔函数下面。

步骤 1 − 按 1 的数量按升序对给定的最小项进行分组，并将其二进制形式写在第 1 列中。

步骤 2 − 比较并合并第 1 列的最小项。

我们可以看到，两个相邻组之间的第 2 列中没有任何项可以与任何其他项组合。因此，它们都是主要蕴涵项。

步骤 3 − 创建主要蕴涵项图表。

从素蕴涵项图中我们可以看出，最小项 m10 和 m14 仅由 S 覆盖。因此，S 是本质素蕴涵项。还可以观察到，函数的其余最小项由最小素蕴涵项集 P 和 R 覆盖。

因此，最小表达式将是，

$$\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 门来实现。

Quine-McCluskey 方法的优势

Quine-McCluskey 方法与其他最小化技术(如卡诺图)相比具有多项优势。 Quine-McCluskey 方法的一些主要优点如下 −

• Quine-McCluskey 方法提供了一个系统的最小化过程来找到复杂布尔表达式的最小版本。
• 它可以应用于大量变量的布尔函数，其中 K-map 技术变得不切实际。
• 它适用于手工计算和计算机计算。
• Quine-McCluskey 方法基于一种有助于减少人为错误的系统算法。
• 它还可以应用于具有无关条件的布尔函数，即不完全布尔函数。

Quine-McCluskey 方法的缺点

然而，Quine-McCluskey 方法是一种强大的简化技术，可以最小化具有多个布尔函数的布尔函数优于其他最小化技术。

但是，它也有一些缺点，其中一些列在下面 −

• Quine-McCluskey 方法的主要缺点是计算复杂度。这是因为，我们必须检查最小项的所有可能组合。
• 虽然对于大量变量，Quine-McCluskey 方法比 K-Map 更好。但它对于大量变量(通常超过 7 个变量)也变得不切实际。
• Quine-McCluskey 方法涉及大量手动计算，这使其变得繁琐且容易出现人为错误。
• Quine-McCluskey 方法对某些类型的布尔函数不太有效。
• 由于 Quine McCluskey 方法涉及最小化的算法方法，而不是图形方法。这使得它不那么直观。

Quine-McCluskey 方法的应用

Quine-McCluskey 方法是布尔代数中最有效的最小化技术之一。它提供了一种最小化大量变量的复杂布尔函数的系统方法。Quine-McCluskey 方法的一些主要应用如下 −

• Quine-McCluskey 方法用于设计和优化数字电路和系统。它有助于减少数字电路中使用的逻辑门的数量。
• 它还用于计算机编程，以优化条件逻辑，提高效率和速度。
• 在数字信号处理中，Quine-McCluskey 方法用于简化布尔表达式，以开发高效的处理算法。
• Quine-McCluskey 方法用于设计高效的状态机。

结论

总之，Quine-McCluskey 方法是一种简化复杂布尔表达式的系统算法方法。它是一种有效的布尔函数最小化技术，适用于大量变量。

Quine-McCluskey 方法的最大优点是它支持手工计算和机器计算，即它是可编程的。然而，这种方法涉及相对复杂的计算，这使得它变得繁琐。