《计算机组成与体系结构（原书第4版）》 —3 特别关注：卡诺图

特别关注：卡诺图

3A.1　引言

本章主要关注布尔表达式及其与数字电路的关系。简化这些电路有助于减少在实际物理实现中的元器件数量。具有较少的元器件可以使电路更快地操作。

可以使用布尔定律化简布尔表达式，然而，使用定律可能很困难，因为没有给出如何使用定律或者何时使用定律，并且没有明确定义一组要遵循的步骤。一方面，简化布尔表达式非常像在做证明：你知道何时在正确的轨道上，但有时在到达时可能令人沮丧和费时。在本部分，介绍一种系统方法来简化布尔表达式。

3A.2　卡诺图和术语描述

卡诺图或K图（Kmaps）是表示布尔函数的图形方式。映射只是一个表，这个表用于列举不同输入值对应的布尔函数值。行和列对应于函数可能的输入值。每个单元格代表那些可能的输入值的函数输出。

如果乘积项正好包括所有变量一次，即原变量或反变量，则该乘积项称为最小项。例如，如果存在两个输入x和y，则存在4个最小项x′y′、x′y、xy′和xy，它们表示函数所有可能的输入组合。如果输入变量是x、y和z，则存在8个最小项：x′y′z′、x′y′z、x′yz′、x′yz、xy′z′、xy′z、xyz′和xyz。

作为示例，假设布尔函数F（x，y）=xy+x′y。x和y的可能输入如图3A-1所示。最小项x′y′表示输入对（0，0）。同理，最小项x′y表示（0，1），最小项xy′表示（1，0），最小项xy表示（1，1）。

三个变量的最小项以及它们表示的输入值如图3A-2所示。

图3A-1　两个变量的最小项   图3A-2　3个变量的最小项

卡诺图是一个表，其中每个单元格对应最小项。这意味着函数真值表的每行对应一个单元格。考虑函数F（x，y）=xy和它的真值表，如例3A.1所示。

例3A.1F（x，y）=xy

对应的卡诺图是：

请注意，卡诺图中唯一为1的单元格出现在x=1和y=1时，相同的值在真值表中是xy=1时。下面请看另一个例子，F（x，y）=x+y。

例3A.2F（x，y）=x+y

例3A.2中有3个最小项的值为1，正好是函数的输入和输出至少有一个为1的最小项。要在卡诺图中设置1，只需要在真值表中找到相应1的地方放置1。可以将函数F（x，y）=x+y表示为所有最小项的逻辑或，其中最小项的值为1。然后F（x，y）可以表示为表达式x′y+xy′+xy。显然，这个表达式不是最小化的（我们已经知道这个函数的最简形式是x+y）。可以使用布尔定律化简。F（x,y）=x′y+xy′+xy

=x′y+xy+xy′+xy　（记住，xy+xy=xy）

=y（x′+x）+x（y′+y）

=y+x

=x+y　　我们如何知道添加一个额外的xy项呢？使用布尔定律化简可能是很棘手的。这时卡诺图可以帮助我们。

3A.3　用卡诺图化简两个变量

先前对函数F（x，y）的化简的目标是对各项进行分组，使得变量因子可以分解出来。添加了xy项来组合x′y，这使得能够计算出y，留下x′+x，它可以化简为1，如果使用卡诺图化简，不必担心要添加哪些项或哪些项要使用布尔定律。卡诺图能够帮助化简。

请再看看图3A-3所示的F（x，y）=x+y的卡诺图。

图3A-3　F（x，y）=x+y的卡诺图要想使用卡诺图来化简布尔函数，只需要对1进行分组。这种分组类似于在使用布尔定律化简时对项进行的分组，除了必须遵循的特定规则。第一，只对1分组。第二，如果1在同一行或者同一列，但它们不在对角线上（即它们必须是相邻单元），那么可以在卡诺图中对1进行分组。第三，如果组中的总数是2的幂，则可以对1进行分组。第四，必须使组尽可能大。第五，所有1必须在一个组中（即使一些在一组中）。如图3A-4～图3A-7所示，可以检查一些正确和不正确的分组。

注意在图3A-6b和图3A-7b中，有一个1属于两个组。这等价于将xy项添加到布尔函数中，就像使用定律执行简化所做的那样。卡诺图中的xy在简化过程中使用两次。

　　为了使用卡诺图化简，首先创建由上述规则指定的组。找到所有组后，检查每个组并丢弃每个组内不同的变量。例如，图3A-7b给出了F（x，y）=x+y的正确分组。从第二行表示的组开始（其中x=1），两个最小项是xy′和xy。此组表示这两个项的逻辑或，即xy′+xy。这些项在y上不同，因此y被丢弃，只留下x。（可以看到，如果使用布尔定律，将会得到相同值。卡诺图允许采取一个捷径，帮助我们自动丢弃正确的变量。）第二组表示x′y+xy。这些项在x上不同，所以x被丢弃，留下y。将第一组和第二组的结果组进行OR运算，得到x+y，这是原始函数F的正确简化形式。

3A.4　用卡诺图化简三个变量

卡诺图可以应用于两个以上变量的表达式中。在本部分，我们显示了三变量和四变量卡诺图。这些可以扩展为有五个或更多个变量的情况。在本节的扩展阅读部分中，Maxfield（1995）的书将会使你彻底和愉快地理解卡诺图。

你已经知道如何为有两个变量的表达式设置卡诺图。这里只是将这个想法扩展到3个变量，如图3A-8所示。

你应该注意图3A-8　3个变量的最小项和卡诺图到的第一个区别是，在表中两个变量y和z被组合起来了。第二个区别是列编号不是按顺序的。这里将列标记为00、01、11、10（正常二进制），而不是00、01、10、11。卡诺图的输入值必须按顺序排列，以使每个最小项只有一个变量不同于相邻单元。通过使用此顺序（例如，01后跟11），对应的最小项x′y′z和x′yz仅在y变量上不同。记住，要化简就需要丢弃不同的变量。因此，必须确保每组的两个最小项中只有一个变量不同。

在两个变量的实例中找到的最大组是由两个1构成的。这个组也可能具有四个甚至八个1，这取决于函数。下面来看看化简3个变量的表达式的例子。

例3A.3F（x，y，z）=x′y′z+x′yz+xy′z+xyz

再次遵循分组规则，你能够看到可以以不同的方式分两个组。然而，规则规定必须创建大小为2的幂的最大组。四个1可以为一组，所以分组如下：

没有必要创建两个额外的组。组越少将会有更少的项。记住，要想化简表达式，所要做的就是保证每一个1都在一些组中。

当某一组有四个1时，如何化简？组中有两个1时允许丢弃一个变量。若组中有四个1，则允许丢弃两个变量：这四项中不同的两个变量。前面的例子中，组中的四项有以下最小项：x′y′z、x′yz、xy′z和xyz。这些项都有z，但x和y变量不同。所以丢弃x和y，F（x，y，z）=z作为最终化简结果。要想了解它与使用布尔定律的简化有何相似之处，请考虑使用定律来简化。注意，该函数最初表示为值1与最小项的逻辑或。

F（x,y,z）=x′y′z+x′yz+xy′z+xyz

=x′（y′z+yz）+x（y′z+yz）

=（x′+x）（y′z+yz）

=y′z+yz

=（y′+y）z

=z　　使用布尔定律的最终结果与使用卡诺图化简的结果完全相同。

有时，分组过程可能有点棘手。下面来看一个需要更仔细观察的例子。

例3A.4F（x，y，z）=x′y′z′+x′y′z+x′yz+x′yz′+xy′z′+xyz′

这是一个棘手的问题，原因有两个：有重叠的组和“环绕”的组。第一列最左边的1可以与最后一列最右边的1分为一组，因为第一列和最后一列在逻辑上相邻（设想卡诺图是在圆柱体上绘制的）。卡诺图的第一行和最后一行在逻辑上也相邻，在下一节讨论四变量卡诺图时这会变得很明显。

正确的分组如下：

第一组化简为x，（这是四项中唯一共同的项），第二组化简为z′，所以最终的最简函数是F（x，y，z）=x′+z′。

例3A.5假设有一个卡诺图的内容都是1。

可以找到的含有1的最大组有八项，其中所有的1在同一组。如何简化？遵循一直以来的规则。记住，两组允许丢弃一个变量，而四组允许丢弃两个变量，因此，八组应该允许丢弃三个变量。但这是所有的变量！如果丢弃所有变量，会留下F（x，y，z）=1。如果用真值表来检查此函数，你会看到这确实是正确的　图3A-9　4个变量的最小项和卡诺图简化。

3A.5　用卡诺图化简四个变量

现在将卡诺图化简扩展到4个变量。4个变量给出了16个项，如图3A-9所示。注意特殊的顺序11后跟10，这适用于所有行和列。

例3A.6说明了有4个变量的函数表示和化简。我们只关心1的情况，所以在卡诺图中省略了0。

例3A.6F（w，x，y，z）=w′x′y′z′+w′x′y′z+w′x′yz′+w′xyz′+wx′y′z′+wx′y′z+wx′yz′

如前面所见，第一组是一个“环绕”组。第三组很容易找到。第二组代表最终的环绕组：它由四个角落的1组成。记住，这些角在逻辑上相邻。最后的结果是F减少到三项，每组中有一个：x′y′（来自组1），x′z′（来自组2），w′yz′（来自组3）。F的最终化简形式为F（w，x，y，z）=x′y′+x′z′+w′yz′。

偶尔，在执行化简时可以使用一些选择。考虑例3A.7。

例3A.75选择组

第一列可清楚地分组。此外，w′x′yz和w′xyz项应分为一组。然而需要选择如何分组w′xyz′项，它可以与w′xyz或w′xy′z′（作为环绕）分组。这两种解决方案如下。

第一个图化简为F（w，x，y，z）=F1=y′z′+w′yz+w′xy。第二个图化简为F（w，x，y，z）=F2=y′z′+w′yz+w′xz′。最后的项是不同的。然而F1和F2是等效的。把它交给F1和F2的真值表来检查是否相等。它们都有相同数量的项和变量。如果遵循规则，卡诺图最小化会导致有最小化函数（因此电路最小），但这些最小化函数在表示中不需要是唯一的。

在继续下一节之前，总结一下卡诺图化简的规则。

1.组中只能包含1，不能包含0。

2.只有相邻的1可以分为一组，不允许对角分组。

3.组中1的数量必须是2的幂。

4.组必须尽可能大，同时仍遵循所有规则。

5.所有1必须属于一个组，即使是单个元素的组。

6.允许重叠组。

7.允许环绕。

8.使用尽可能少的组数。

使用这些规则，再完成一个四变量函数的例子。例3A.8示给出了各种规则的若干应用。

例3A.8F（w,x,y,z）=w′x′y′z′+w′x′yz+w′xy′z+w′xyz+wxy′z+wxyz+wx′yz+wx′yz′

在这个例子中，有一个单元素的组。注意，如果遵守规则，则没有办法将这个项与任何其他项分为1组。由这个卡诺图表示的函数简化为F（w，x，y，z）=yz+xz+w′x′y′z′+wx′y。

如果给出的函数没有写为最小项的和，仍然可以使用卡诺图来实现最小化函数。但是，在化简之前你不得不使用一个与设置卡诺图有些相反的过程。例3A.9说明了该过程。

例3A.9函数没有表示为最小项之和

假设给定函数F（w，x，y，z）=w′xy+w′x′yz+w′x′yz′。最后两项是最小项，我们可以很容易地把1放在卡诺图的适当位置。然而，w′xy不是最小项。假设这项是你在卡诺图上执行分组的结果。被丢弃的是z项，这意味着这个项相当于w′xyz′+w′xyz两项。你现在可以在卡诺图中使用这两项，因为它们都是最小项。现在得到以下卡诺图：

所以，函数F（w，x，y，z）=w′xy+w′x′yz+w′x′yz′可以化简为F（w，x，y，z）=w′y。

3A.6　无关条件

在某些情况下，可能不能完全指定函数。这意味着函数可能有一些未定义的输入。例如，假设有一个函数有4个输入，0～10（十进制）作为二进制计数位。使用位组合0000、0001、0010、0011、0100、0101、0110、0111、1000、1001和1010。但是不使用组合1011、1100、1101、1110和1111。后面的这些输入将是无效的，这意味着如果查看真值表，这些值不会是0或1。它们不应该在真值表中。

化简卡诺图时，可以使用这些无关输入的优势。因为它们是不重要的输入值（并且是不应该发生的），所以可以让它们有0或1的值，这取决于哪个对我们帮助最多。基本思想是设置这些无关值，使它们要么有助于构成一个更大的组，要么它们根本不贡献。例3A.10阐释了该概念。

　　例3A.10无关条件

无关值通常在适当的单元格中用“×”表示。下面的卡诺图展示了如何使用这些值来帮助最小化。将第一行中的值视为1，以形成四个1一组。行01和11中的无关值被视为0。因此化简为F1（w，x，y，z）=w′x′+yz。

还有一种方法可以将这些值分组：

使用这些分组，最终得到F2（w，x，y，z）=w′z+yz的简化形式。注意，在这种情况下，F1和F2不相等。但是，如果你为两个函数创建真值表，则应该看到它们仅在“无关”的那些值上不相等。

3A.7　总结

本部分简要介绍了卡诺图和卡诺图化简。使用布尔定律来化简很笨拙，甚至可能是非常困难的。从另一方面来说，卡诺图提供了一组精确的步骤来寻找函数的最小化表示，从而得到函数所表示的最小化电路。

练习

1. 使用以下卡诺图为定义的布尔函数写出一个简化的表达式：

   

   
   

2.使用以下卡诺图为定义的布尔函数写出一个简化的表达式：

3.创建卡诺图，然后化简以下函数：

a）F（x,y,z）=x′y′z′+x′yz+x′yz′

b）F（x,y,z）=x′y′z′+x′yz′+xy′z′+xyz′

c）F（x,y,z）=y′z′+y′z+xyz′

4.使用以下卡诺图为定义的布尔函数写出一个简化的表达式：

5.使用以下卡诺图为定义的布尔函数写出一个简化的表达式（使用乘积和的形式）

6.创建卡诺图，然后化简以下函数（保留乘积和的形式）：

a）F（w,x,y,z）=w′x′y′z′+w′x′yz′+w′xy′z+w′xyz+w′xyz′+wx′y′z′+wx′yz′

b）F（w,x,y,z）=w′x′y′z′+w′x′y′z+wx′y′z+wx′yz′+wx′y′z′

c）F(w,x,y,z)=y′z+wy′+w′xy+w′x′yz′+wx′yz′

7.创建卡诺图，然后化简以下函数（保留乘积和的形式）：

a)F(w,x,y,z)=w′x′y′z+w′x′yz′+w′xy′z+w′xyz+w′xyz′+wxy′z+wxyz+wx′y′z

　b)F(w,x,y,z)=w′x′y′z′+w′z+w′x′yz′+w′xy′z′+wx′y

c)F(w,x,y,z)=w′x′y′+w′xz+wxz+wx′y′z′

8.给定下面的卡诺图，（使用布尔定律）说明四个项如何化简为一个项。

9.为由以下卡诺图定义的布尔函数编写一个简化表达式：

10.为由以下卡诺图定义的布尔函数编写一个简化表达式：

11.为由以下卡诺图定义的布尔函数编写一个简化表达式：

12.为以下每个真值表定义的函数找到最小化的布尔表达式：