卡诺图K-map化简法规则以及不同变量示例详解
卡诺图或K-map是由贝尔实验室的电信工程师Maurice Karnaugh于1953年引入,作为“Veitch图”的改进技术,它是一种简化或降低布尔表达式复杂性的方法。
卡诺图方法是布尔方程的图形表示,布尔运算用于降低求解它们的复杂性。这些可以被视为“真值表”的特殊或扩展版本。
卡诺图可以解释为“一个包含2k个网格格式单元格的数组,其中k是布尔表达式中要减少或优化的变量数”。由于它是从真值表方法评估的,因此卡诺图中的每个单元格将代表真值表的一行,并且一个单元格由一个正方形表示。
卡诺图中的单元格以这样一种方式排列,即在相邻行中分配了在单个变量中不同的连词。卡诺图方法支持消除潜在的竞争条件,并允许快速识别。
利用卡诺图技术,可以简化包含任意数量变量的布尔表达式,例如2变量布尔表达式、3变量布尔表达式、4变量布尔表达式甚至是7变量布尔表达式,这些表达式通过使用常规的布尔定理和定律求解起来很复杂。
最小化和主要优势
- 卡诺图用于将布尔方程的真值表转换为最小化的SOP形式。
- 简化的简单基本规则。
- 卡诺图方法比布尔代数的其他简化技术更快、更有效。
- 卡诺图中的所有行都使用正方形单元表示,其中每个正方形代表一个最小项。
- 很容易将真值表转换为卡诺图,并将卡诺图转换为乘积和形式方程。
目前将布尔方程转换为卡诺图有2种形式:
- 未优化的形式
- 优化形式
其中,未优化形式涉及将1的数量转换为SOP方程中相等数量的乘积项(最小项);而优化形式涉及减少SOP方程中的最小项数。
变量分组
当在卡诺图中对变量进行分组时,需要遵循一些规则,主要包括以下几点:
- 包含'1'的方块应该被简化,至少一次。
- 包含“1”的正方形可以被考虑多次,因为它可以进行分组。
- 组不应包含任何零(0)。
- 一个组应该是尽可能大的。
- 组可以是水平的或垂直的,不允许以对角线方式对变量进行分组。
- 如果包含'1'的方块不可能被放在一个组中,那么它应该被添加到最后的表达式中。
- 组可以重叠。
- 一组中的方块数必须等于2的幂,例如1、2、4、8等。
- 组可以环绕。由于卡诺图被认为是球形或折叠的,因此角落处的方块(位于列或行的末端)应被视为相邻方块。
- 卡诺图变量的分组可以通过多种方式进行,因此得到的简化方程不必总是唯一的。
- 布尔方程必须是规范形式,才能绘制K图。
2变量卡诺图
2变量k图中有4个单元格 (22)。它看起来如下图所示:
具有2个变量(A 和 B)的可能最小项是AB、A.B'、A'.B和A'.B'。变量 (A, B) 和 (A', B) 的连词在顶行的单元格中表示,(A, B') 和 (A', B') 在底行的单元格中表示。下表显示了2变量布尔函数的所有可能输出在卡诺图上的位置。
2变量卡诺图的一般表示如下所示:
当使用卡诺图简化布尔方程时,表示卡诺图的每个单元格包含与1的合取项。之后,将可能大小为2或4的相邻单元格分组。如果卡诺图较大,则可以将变量分组为更大的尺寸,如8或16。
变量组应为矩形,这意味着组必须通过垂直或水平组合相邻的单元格来形成。不允许使用对角线形或 L形组。以下示例演示了2变量布尔方程的K图简化。
示例
使用K-map简化给定的2变量布尔方程是:F=X Y'+X' Y+X'Y'。
首先构建给定方程的真值表,如下图所示:
将1放在等式中给出的输出项中,具体如下:
通过减少每个组,可以获得了最小化表达式的合取,例如通过从两个组中取出公共项,即X'和Y',所以简化方程将是X'+Y'。
3变量K-map
对于3变量布尔函数,可能有8个输出最小项。使用3变量的所有最小项的一般表示如下所示:
3变量K图的典型图如下所示。可以观察到,第10列和第11列的位置互换,因此相邻单元格中只有一个变量发生变化。此修改将允许最小化逻辑。
在3变量K图的情况下,最多可以对8个单元进行分组,其它可能性为1,2和4。
示例
使用K-map简化给定的3变量布尔方程是:F=X' YZ+X' Y' Z+XY Z'+X' Y' Z'+XYZ+X Y' Z'
首先构建给定方程的真值表,如下图所示:
继续将1放在等式中给出的输出项中。
3变量K图中有8个单元格 (23),它看起来像(见下图)。
最大的小组人数为8人,但也可以根据可能形成4人和2人的小组。在3变量卡诺图中,将K-map的最左侧列视为最右侧列的相邻列。因此,大小为4的组形成如下所示。
在这两个组当中,有一个共同点“Y”。因此,大小为4的组减少为合取Y。为了消耗其中包含1的每个单元格,将其余单元格分组以形成大小为2的组,如下所示
2大小组没有公共变量,所以用它们的变量和它的共轭来写。所以简化的方程将是X Z'+Y'+X'Z。在这个方程中,不可能进一步最小化了。
4变量K-map
对于4变量布尔函数,有16个可能的最小项。使用4个变量的最小项的一般表示如下所示:
典型的4变量K-map图如下所示,可以观察到10和11的列和行都互换了。
可以组合在一起的单元格的可能数量是1、2、4、8和16。
示例
使用K-map简化给定的4变量布尔方程。F (W, X, Y, Z) = (1, 5, 12, 13),Sol: F (W, X, Y, Z) = (1, 5, 12, 13)。
通过准备K-map,可以将给定的布尔方程最小化为:F=W Y'Z+W 'Y'Z。
5变量K-map
一个5变量布尔函数最多可以有32个最小项,所有可能的最小项如下所示:
在5变量K-map中,有32个单元格,如下所示。它由F(A、B、C、D、E)表示。它分为两个网格,每个网格有16个单元格,其中一个变量 (A) 在一个网格中为 0,在另一个网格中为1。
示例
使用K-map简化给定的5变量布尔方程:f (A, B, C, D, E) =∑m (0, 5, 6, 8, 9, 10, 11, 16, 20, 42, 25, 26, 27)
带有“无关”条件的K-map
“无关”条件用于替换空单元格以形成可能的变量分组。根据组中的相邻变量,它们可以用作0或 1。包含“无关”条件的单元格由正常0和1之间的星号 (*) 符号表示。
在对变量进行分组时,也可以忽略“无关”。“无关”条件在分组大变量时非常有用。
使用无关最小化表达式
可以通过为“无关”条件分配0或1找到相关函数来最小化布尔表达式。如果n是布尔方程中无关项的数量,则获得的函数数量将为2n。
使用K-map实现BCD到格雷码转换器
格雷码是一个数列,其中两个连续的数相差一位。该代码由科学家“Frank Gray”得名。他于1953年拥有在轴寄存器中使用格雷码的专利。
其实这里也可以使用K-map简化将二进制编码的十进制 (BCD) 码转换为格雷码。
BCD码和格雷码表如下所示:
G3的K-MAP
(方程式G3=B3)
G2的K-MAP
(方程式G2=B3'B2+B3 B2'=B3 XOR B2)
G1的K-MAP
(方程式G1=B1'B2+B1 B2'= B1 XOR B2)
G0的K-MAP
(方程式G0= B1' B0 + B1 B0'= B1 XOR B0)
所以,BCD到格雷转换可以使用逻辑门的实现如下图所示,这里使用两个异或门和一个或门,简单的设计参看下图:
总结
从以上分析不难看出,卡诺图K-map其实是逻辑函数的一种图形表示。一个逻辑函数的卡诺图就是将此函数的最小项表达式中的各最小项相应地填入一个方格图内,此方格图称为卡诺图。卡诺图的构造特点使卡诺图具有一个重要性质,那就是可以从图形上直观地找出相邻最小项,两个相邻最小项可以合并为一个与项并消去一个变量。