数字电路 - K-Map 方法

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

为了克服这个困难，卡诺引入了一种简单地简化布尔函数的方法。该方法称为卡诺图法或K-图法。^{它是一种图形方法，由 2 n 个}代表“n”个变量的单元格组成。相邻单元仅在一位位置上有所不同。

2 至 5 个变量的 K 映射

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

2 变量 K-Map

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

只有一种可能性将 4 个相邻的最小项分组。
将2个相邻最小项分组的可能组合是{(m ₀ , m ₁ )、(m ₂ , m ₃ )、(m ₀ , m ₂ )和(m ₁ , m ₃ )}。

3 变量 K-Map

3 变量 K 图中的单元数量为 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-Map

4 变量 K 图中的单元数量为 16，因为变量数量为 4。下图显示了4个变量的K-Map。

将 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-Map

由于变量数量为 5，因此 5 变量 K-map 中的单元格数量为 32。下图显示了5 变量 K-Map。

只有一种可能性将 32 个相邻的最小项分组。
将 16 个相邻的最小项分组有两种可能性。_{即，对从m 0}到m ₁₅和m ₁₆到m ₃₁的最小项进行分组。
如果v=0，则5变量K图变成4变量K图。

在上述所有 K 图中，我们专门使用了最小项符号。同样，您可以专门使用最大项表示法。

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

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

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

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

根据布尔函数中存在的变量数量选择相应的 K 图。
如果布尔函数以最小项之和的形式给出，则将它们放置在 K 图中相应的最小项单元格中。如果布尔函数以乘积之和的形式给出，则将其放置在给定乘积项有效的 K 映射的所有可能单元格中。
检查将最大数量的相邻的分组的可能性。应该是二的幂。从最高的二的幂开始，到最小的二的幂。最高功效等于 K 图中考虑的变量数量，最小功效为零。
每个分组将给出一个字面术语或一个乘积术语。它被称为素蕴涵。如果至少单个“1”没有被任何其他分组覆盖而仅被该分组覆盖，则素蕴涵被称为本质素蕴涵。
记下所有素蕴涵项和基本素蕴涵项。简化的布尔函数包含所有必要的素蕴涵项并且仅包含所需的素蕴涵项。

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

注 2 - 如果也存在不关心术语，则将不关心“x”放置在 K-map 的相应单元格中。仅考虑不关心“x”，这有助于对最大数量的相邻“x”进行分组。在这些情况下，请将无关值视为“1”。

例子

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

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

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

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

不可能将 16 个相邻的或 8 个相邻的进行分组。将 4 个相邻的分组有三种可能性。经过这三组之后，没有任何一个是未分组的。因此，我们不需要检查 2 个相邻的分组。具有这三个分组的 4 变量 K 图如下图所示。

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

第四行分组中的两个（m ₈和m ₉）不被任何其他分组覆盖。只有第四行分组涵盖了这两个。
方形分组中的单个（m ₁₅）不被任何其他分组覆盖。只有方形分组涵盖了该分组。
第四列分组的两个（m ₂和m ₆）不被任何其他分组覆盖。只有第四列分组涵盖了这两个。

因此，简化的布尔函数为

f = WX' + WY + YZ'

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

根据布尔函数中存在的变量数量选择相应的 K 图。
如果布尔函数以最大项形式的乘积给出，则将零放置在 K 图中相应的最大项单元格处。如果布尔函数以和形式的乘积给出，则将零放置在给定和项有效的 K 映射的所有可能单元格中。
检查对最大数量的相邻零进行分组的可能性。应该是二的幂。从最高的二的幂开始，到最小的二的幂。最高功效等于 K 图中考虑的变量数量，最小功效为零。
每个分组将给出一个字面值或一个总和项。它被称为素蕴涵。如果至少单个“0”没有被任何其他分组覆盖而仅被该分组覆盖，则素蕴涵被称为本质素蕴涵。
记下所有素蕴涵项和基本素蕴涵项。简化的布尔函数包含所有必要的素蕴涵项并且仅包含所需的素蕴涵项。

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

例子

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

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

不可能将 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 图中的单元格数量会增加一倍。

由于这种检查和相邻项（最小项）或相邻零项（最大项）的分组将会很复杂。我们将在下一章讨论Tabular 方法来克服 K-map 方法的困难。