K-Map(卡诺图)

卡诺图(又称K-map)是贝尔实验室的一位电信工程师莫里斯·卡诺(Maurice Karnaugh)于1953年提出的,作为“爱德华·维奇的维奇图”(Edward Veitch’s Veitch diagram)的一种改进技术,它是一种简化或减少布尔表达式复杂性的方法。

卡诺图法或k -图法是布尔方程的图形表示,并采用布尔操作来降低求解的复杂性。这些可以被认为是“真理表”的特殊或扩展版本。

Karnaugh map可以被解释为“一个包含2k个类似网格格式的单元格的数组,其中k是布尔表达式中需要减少或优化的变量的数量”。由于它是由真值表方法评估的,K-map中的每个单元格将代表真值表中的一行,而一个单元格将用一个正方形表示。

k-map中的细胞以这样一种方式排列,即在相邻的行中分配在单个变量中不同的连接。K-map方法支持消除潜在的竞争条件,并允许快速识别。

利用卡诺映射技术,我们可以减少包含任意数量变量的布尔表达式,如2变量布尔表达式、3变量布尔表达式、4变量布尔表达式甚至7变量布尔表达式,这些布尔表达式使用正则布尔定理和定律求解是很复杂的。

卡诺图的最小化和k -图的优点

  • K-MAPS用于将布尔方程的真实表转换为最小化的SOP形式。
  • 简单易学的基本规则为简化。
  • K-MAP方法比布尔代数的其他简化技术更快,更高效。
  • K-map中的所有行都用一个正方形的单元格表示,其中的每个正方形表示一个中间值。
  • 很容易将真相表转换为k-map和k映射到产品形式方程的总和。

将布尔方程转换为K-MAP,有2个表格:

  1. 未经优化的形式
  2. 优化的形式
  • 未经优化的形式:它涉及在SOP方程中将1的数量转换为相等的产品项(MIN术语)。
  • 优化的形式:它涉及减少SOP方程中的分钟数。

K-map变量分组

  • 当我们在k -map中分组变量时,需要遵循一些规则。他们是
  • 在简化时,至少要取包含' 1 '的平方。
  • 包含'1'的正方形可以被视为多次,因为可以使用分组。
  • Group不应该包含任何零(0)。
  • 一个组应该尽可能的大。
  • 组可以是水平或垂直的。不允许以对角线方式分组变量。

K-map变量分组

1 . K-map变量的分组

  • 如果含有'1'的正方形没有可能放入组中,那么它应该添加到最终表达式中。
  • 组可以重叠。
  • 一组的平方数必须等于2的幂,如1、2、4、8等。
  • 团体可以包裹。当K-MAP被认为是球形或折叠时,拐角处的正方形(在塔或行的末端)应该被认为是它们相邻的正方形。
  • K-MAP变量的分组可以在许多方面进行,因此获得的简化方程不需要始终是唯一的。
  • 布尔方程必须是必须是标准形式,这样才能画出K-map。

3 . K-map变量的分组

4 . K-map变量分组

2变量K-maps

在2变量k-map中有4个单元格(22)。它看起来就像(见下图)

2变量K-maps

具有2个变量(a和b)的可能最小术语是a.b,a.b',a'.b和a'.b'。变量(a,b)和(a',b)的缀合在底行的小区中的顶行和(a,b')和(a',b')的单元中表示。下表显示了K-MAP上的2变量布尔函数的所有可能输出的位置。

2变量k-map

一个2变量K-map图的一般表示如下所示。

2变量k映射

当我们使用Karnaugh Map简化Boolean方程时,我们表示包含连接术语的K-Map的每个单元格,其中包含一个尺寸为2或4的可能尺寸的相邻小区。如果是较大的k映射,我们可以将变量置于较大的尺寸,如8或16。

变量组应该是矩形的,这意味着组必须通过垂直或水平组合相邻的单元格形成。不允许对角线形或l形组。下面的例子演示了一个2变量布尔方程的K-map简化。

例子

利用K-map对给定的2变量布尔方程进行简化。

f = x y'+ x'y + x'y'

首先,让我们构建给定方程的真相表,

例子

我们在方程的输出项上代入1。

2 VAR的前女友

In this K-map, we can create 2 groups by following the rules for grouping, one is by combining (X’, Y) and (X’, Y’) terms and the other is by combining (X, Y’) and (X’, Y’) terms. Here the lower right cell is used in both groups.
分组变量后,下一步是确定最小化的表达式。

通过对每一组进行还原,我们得到了一个极小表达式的合取,如从两组中取出公共项,即X '和Y '。简化后的方程是X ' +Y '

3变量k映射

对于3变量布尔函数,可能有8个输出分钟术语。使用3变量的所有MIN术语的一般表示如下所示。

3变量k图-1

3变量K-map的典型图如下所示。可以观察到,第10列和第11列的位置互换了,因此在相邻的单元格中只有一个变量发生了变化。这种修改将允许最小化逻辑。

3变量k映射

在3个变量的K-map中,最多可以将8个单元格分组,其他可能是1、2和4。

例子

使用k映射简化给定的3变量布尔方程式。

F = x ' y z + x ' y ' z + x ' y ' z + x ' y ' z + x ' y ' z + x ' y ' z '

首先,让我们构建给定方程的真相表,

3 var exm真值表

我们在方程的输出项上代入1。

在3变量K-MAP中有8个细胞(23)。它看起来像(见下面的图片)。

最大的群体规模将是8,但我们也可以形成规模为4和规模为2的群体,根据可能性。在3变量的卡诺图中,我们将k-map的最左列视为最右列的相邻列。所以4号组就形成了如下图所示。

3 var em 2

在这两项中,我们有一个共同的Y。所以大小为4的一组减少为合取y。为了消耗每一个包含1的细胞,我们将剩下的细胞分组形成大小为2的一组,如下所示。

3 var em 3

2号组没有公共变量,所以用它们的变量和共轭形式来表示。因此简化后的方程将是X Z ' + Y ' + X ' Z。在这个方程中,没有进一步的最小化是可能的。

4变量K-maps

在4变量布尔函数中有16个可能的最小项。使用4个变量的项的一般表示如下所示。

4 var k map1

典型的4变量K-map图如下所示。可以看到,10和11的列和行都互换了。

4-Variable K-map

可以分组的可能数量的单元是1,2,4,8和16。

例子

利用k-map对给定的4变量布尔方程进行简化。F (w, x, y, z) = (1, 5, 12, 13)

溶胶:F(w,x,y,z)=(1,5,12,13)

4 VAR示例

通过准备K-MAP,我们可以最小化给定的布尔方程式

f = w y'z + w'y'z

5个变量K-maps

5变量布尔函数最多可具有32个minterms。所有可能的minterms都在下面表示

一种 B. C D. E. 输出功能 位置K-map
0. 0. 0. 0. 0. A’’C’D’E’ 0.
0. 0. 0. 0. 1 a'b'c'e.e. 1
0. 0. 0. 1 0. 一个’B’C’DE’ 2
0. 0. 0. 1 1 一个’B’C’DE 3.
0. 0. 1 0. 0. a'b'cd'e' 4.
0. 0. 1 0. 1 a'b'cd'e. 5.
0. 0. 1 1 0. A’’CDE’ 6.
0. 0. 1 1 1 A’’CDE 7.
0. 1 0. 0. 0. 公元前’’D’E’ 8.
0. 1 0. 0. 1 公元前’’D’E 9.
0. 1 0. 1 0. 一个公元前’’DE’ 10.
0. 1 0. 1 1 公元前’’DE 11.
0. 1 1 0. 0. a'bcd'e' 12.
0. 1 1 0. 1 一个’BCD’E 13.
0. 1 1 1 0. 一个’BCDE’ 14.
0. 1 1 1 1 一个’BCDE 15.
1 0. 0. 0. 0. ab'c'd'e' 16.
1 0. 0. 0. 1 ab'c'e 17.
1 0. 0. 1 0. AB’C’DE’ 18.
1 0. 0. 1 1 Ab'c'de. 19.
1 0. 1 0. 0. AB’CD’E’ 20.
1 0. 1 0. 1 AB’CD’E 21.
1 0. 1 1 0. ab'cde' 22.
1 0. 1 1 1 AB’CDE 23.
1 1 0. 0. 0. abc'd'e' 24.
1 1 0. 0. 1 ABC’D’E 25.
1 1 0. 1 0. abc'de' 26.
1 1 0. 1 1 ABC’德 27.
1 1 1 0. 0. ABCD’E’ 28.
1 1 1 0. 1 ABCD’E 29.
1 1 1 1 0. ABCDE' 30.
1 1 1 1 1 中的 31.

在5变量的K-MAP中,我们有32个单元格如下所示。它由f(a,b,c,d,e)表示。它被分为两个16个单元格,其中一个变量(a)为一个网格中的0,另一个网格中为1。

5变量k映射

例子

使用k映射简化给定的5变量布尔方程式。

f (A, B, C, D, E) =∑m(0、5、6、8、9、10、11、16、20日,42岁,25日,26日27)

5 VAR示例

K-MAP与“不关心”条件

“不关心”条件用于替换空单元格以形成可能的变量分组。它们可以根据组中的相邻变量使用为0或1。包含“不关心”条件的细胞由正常0和1的星号(*)符号表示。

在分组变量中,我们也可以忽略“不要关心”。“不关心”条件在分组大尺寸的变量方面非常有用。

用“不在乎”最小化你的表情

我们可以通过寻找“不关心”条件的相对函数,将它们赋值为0或1来最小化布尔表达式。如果n是一个布尔方程中不关心的个数,那么得到的函数个数为2N

利用K-map实现BCD到灰码转换器

格雷码是一个数字系列,其中两个连续的数字相差一位。这段代码以科学家“弗兰克·格雷”命名。1953年,他拥有了在竖井登记册中使用格雷码的专利。

我们可以通过使用k-map简化将二进制编码的十进制(BCD)代码转换为格雷码。

BCD代码和灰色代码的表

BDC码和灰色码

G3的k映射

G3的k映射

G2的k映射

G2的k映射

G2= B3 ' B2 + B3 B2 ' = B3 XOR B2

G1的k映射

G1的k映射

G1 = B1'B2 + B1 B2'的等式= B1 XOR B2

G0的k映射

G0的k映射

G0 = B1'B0 + B1 B0'的等式= B1 XOR B0

使用逻辑门实现BCD到灰度转换如下图所示。使用了两个前或门和一个或门。

bcd到灰色

留下一个回复

您的电子邮件地址将不会被公布。必需的地方已做标记*