数字电路 - K-Map 方法

在前面的章节中，我们使用布尔公理和定理简化了布尔函数。这是一个耗时的过程，我们必须在每个步骤之后重写简化的表达式。

为了克服这个困难，卡诺 介绍了一种简单的布尔函数简化方法。此方法称为卡诺图方法或 K-map 方法。它是一种图形方法，由 2ⁿ 个单元格组成，用于"n"个变量。相邻单元格仅在单个位位置上有所不同。

2 到 5 个变量的 K-Map

K-Map 方法最适合最小化 2 个变量到 5 个变量的布尔函数。现在，让我们逐一讨论 2 到 5 个变量的 K-Map。

2 变量 K-Map

2 变量 K-Map 中的单元格数量为四个，因为变量数量为两个。下图显示了2 变量 K-Map。

• 只有一种可能性是对 4 个相邻的最小项进行分组。

• 对 2 个相邻的最小项进行分组的可能组合是 {(m₀, m₁), (m₂, m₃), (m₀, m₂) 和 (m₁, m₃)}。

3 变量 K-Map

3 变量 K-Map 中的单元格数量为 8，因为变量数量为 3。下图显示3变量K-Map。

• 将8个相邻的最小项分组只有一种可能性。

• 将4个相邻的最小项分组的可能组合是{(m₀, m₁, m₃, m₂), (m₄, m₅, m₇, m₆), (m₀, m₁, m₄, m₅), (m₁, m₃, m₅, m₇)、(m₃、m₂、m₇、m₆) 和 (m₂、m₀、m₆、m₄)}。

• 将 2 个相邻的最小项分组的可能组合为 {(m₀, m₁)、(m₁, m₃)、(m₃, m₂)、(m₂, m₀)、(m₄, m₅)、(m₅, m₇)、(m₇, m₆)， （m₆，m₄）、（m₀，m₄）、（m₁，m₅）、（m₃，m₇）和（m₂，m₆））。

• 如果 x=0，则 3 变量 K 图变为 2 变量 K 图。

4 变量 K 图

4 变量 K 图的单元格数为 16，因为变量数为 4。下图显示 4 变量 K 图。

• 将 16 个相邻的最小项组合在一起的可能性只有一种。

• 令 R₁、R₂、R₃ 和 R₄ 分别表示第一行、第二行、第三行和第四行的最小项。同样，C₁、C₂、C₃ 和 C₄ 分别表示第一列、第二列、第三列和第四列的最小项。 8 个相邻最小项的可能组合为 {(R₁, R₂), (R₂, R₃), (R₃, R₄), (R₄, R₁), (C₁, C₂), (C₂, C₃), (C₃, C₄), (C₄, C₁)}。

• 如果 w=0，则 4 变量 K 图变为 3 变量 K 图。

5 变量 K 图

5 变量 K 图的单元格数为 32，因为变量数为 5。下图显示 5 变量 K-Map。

• 只有一种可能性可以将 32 个相邻的最小项分组。

• 有两种可能性可以将 16 个相邻的最小项分组。即，将最小项从 m₀ 分组到 m₁₅ 和从 m₁₆ 分组到 m₃₁。

• 如果 v=0，则 5 变量 K-map 变为 4 变量 K-map。

在上述所有 K-map 中，我们仅使用最小项符号。类似地，您可以专门使用最大项符号。

使用 K-Maps 最小化布尔函数

如果我们考虑布尔函数为"1"的输入组合，那么在简化 K-map 后，我们将得到布尔函数，该函数为标准乘积和形式。

类似地，如果我们考虑布尔函数为"0"的输入组合，那么在简化 K-map 后，我们将得到布尔函数，该函数为标准和积形式。

遵循这些简化 K-maps 的规则以获得标准乘积和形式。

• 根据布尔函数中存在的变量数量选择相应的 K-map。

• 如果布尔函数给出为最小项和形式，然后将这些值放在 K-map 中相应的最小项单元格中。如果布尔函数以乘积和形式给出，则将这些值放在 K-map 中给定乘积项有效的所有可能单元格中。

• 检查对最大数量的相邻值进行分组的可能性。它应该是 2 的幂。从最高的 2 的幂开始，直到最小的 2 的幂。最高幂等于 K-map 中考虑的变量数，最小幂为零。

• 每个分组都会给出一个文字或一个乘积项。它被称为素蕴涵项。如果至少一个"1"未被任何其他分组覆盖，而只有该分组覆盖，则素蕴涵项被称为基本素蕴涵项。

• 记下所有素蕴涵项和基本素蕴涵项。简化的布尔函数包含所有必要的素蕴涵项和仅必需的素蕴涵项。

注释 1 − 如果未针对某些输入组合定义输出，则这些输出值将用无关符号"x"表示。这意味着，我们可以将它们视为"0"或"1"。

注释 2 − 如果还存在无关项，则将无关项"x"放置在 K 图的相应单元格中。仅考虑有助于对最大数量的相邻项进行分组的无关项"x"。在这些情况下，将无关值视为"1"。

示例

让我们使用 K-map 简化以下布尔函数，f(W, X, Y, Z)= WX'Y' + WY + W'YZ'。

给定的布尔函数是乘积和形式。它有 4 个变量 W、X、Y 和 Z。因此，我们需要 4 变量 K-map。下图显示了 4 变量 K-map，其中 1 对应于给定的乘积项。

这里，1 被放置在 K-map 的以下单元格中。

• 第 4 行和第 1 列的交点所共有的单元格 & 2 对应于乘积项 WX'Y'。

• 第 3 行和第 4 行以及第 3 列和第 4 列的交点所共有的单元格对应于乘积项 WY。

• 第 1 行和第 2 行以及第 4 列的交点所共有的单元格对应于乘积项 W'YZ'。

16 个相邻的或 8 个相邻的不可能被分组。4 个相邻的有三种分组可能性。经过这三种分组后，没有一个是未分组的。因此，我们不需要检查 2 个相邻的分组。下图显示了具有这三个分组的4 变量 K 图。

在这里，我们得到了三个素蕴涵项 WX'、WY 和 YZ'。由于以下原因，所有这些素蕴涵项都是必需的。

• 第四行分组中的两个 1(m₈ 和 m₉) 未被任何其他分组覆盖。只有第四行分组覆盖这两个 1。

• 方形分组中的单个 1(m₁₅) 未被任何其他分组覆盖。只有方形分组覆盖了那个。

• 第四列分组的两个 1(m₂ & m₆) 未被任何其他分组覆盖。只有第四列分组覆盖了这两个。

因此，简化的布尔函数是

f = WX' + WY + YZ'

遵循这些简化 K 图的规则，以获得标准的和积形式。

• 根据布尔函数中存在的变量数量选择相应的 K 图。

• 如果布尔函数以最大项乘积的形式给出，则将零放置在 K 图的相应最大项单元格中。如果布尔函数以和积的形式给出，则将零放置在给定和项有效的 K 图的所有可能单元格中。

• 检查对最大数量的相邻零进行分组的可能性。它应该是 2 的幂。从 2 的最高幂开始，直到 2 的最小幂。最高功率等于 K-map 中考虑的变量数，最低功率为零。

• 每个分组将给出一个文字或一个和项。它被称为素蕴涵项。如果至少一个"0"未被任何其他分组覆盖，而只有该分组覆盖，则素蕴涵项被称为基本素蕴涵项。

• 记下所有素蕴涵项和基本素蕴涵项。简化的布尔函数包含所有基本素蕴涵项和仅所需的素蕴涵项。

注意 − 如果还存在无关项，则将无关项"x"放置在 K-map 的相应单元格中。仅考虑有助于对最大数量的相邻零进行分组的无关项"x"。在这些情况下，将无关值视为"0"。

示例

让我们使用 K-map 简化以下布尔函数 $f\left ( X,Y,Z ight )=\prod M\left ( 0,1,2,4 ight )$。

给定的布尔函数是最大项乘积形式。它有 3 个变量 X、Y 和 Z。因此，我们需要 3 个变量 K-map。给定的最大项是 M₀、M₁、M₂ 和 M₄。下图显示了具有与给定最大项相对应的零的 3 变量 K-map。

8 个相邻零或 4 个相邻零均不可能分组。2 个相邻零有三种分组可能性。经过这三种分组后，没有单个零未分组。下图显示了具有这三种分组的3 变量 K 图。

这里，我们得到了三个素数蕴涵项 X + Y、Y + Z & Z + X。所有这些主要蕴涵项都是必要的，因为每个分组中的一个零除了它们各自的分组外，不会被任何其他分组覆盖。

因此，简化的布尔函数是

f = (X + Y).(Y + Z).(Z + X)

这样，我们可以使用 K-map 方法轻松简化最多 5 个变量的布尔函数。对于超过 5 个变量，使用 K-Map 简化函数会很困难。因为，通过包含一个新变量，K-map 中的单元格数量会翻倍。

因此，检查和分组相邻的 1（最小项）或相邻的零（最大项）将变得复杂。下一章我们将讨论表格方法来克服K-map方法的困难。