奎恩-麦克拉斯基化简法(Q M 法)

大家好，欢迎来到IT知识分享网。

文章目录

为什么需要化简?

因为表达式的复杂度决定了逻辑门元器件的搭建复杂度,也就是说化简后的式子所搭建的逻辑电路不仅功能上等同未化简的式子,而且成本更少,制造的电子元件更轻. 所以说化简是很有必要的

逻辑函数的化简史

那么化简有哪些方式?

代数化简(人工苦力,利用公式化简)————适用于四输入及以下变量加减化简
卡诺图化简(相对来说轻松了一点,从代数 $\rightarrow$ 几何)顺序按照格雷码 $^{[1]}$ 编码方式. 利用了卡诺图的相邻性——消除相邻因子的不同因子.
```
[1] 格雷码:在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同， 则称这种编码为格雷码`（Gray Code） 
```
1. Q M 法(划时代的化简方法),解放人力,运用计算机解决化简

在卡诺图中相邻的格子不仅在几何上相邻也在逻辑上相邻, 如你所见上图中 $m_0$ 与 $m_1$ (表格中为1的地方)几何相邻, 从逻辑来看他们都是 $A^{'} B^{'} C^{'} -$ (这里的 $“ - “$ 代表任意取值), 又因为二进制只有 $0/1$ 所以也满足逻辑相邻.

我们来化简下这两项合并的结果:

$A’B’C'( D+D’) = A’B’C’_{\;(1)}$

如你所见,化简的基本思路是留下相同因子,消去相邻项不同因子

运用Q M法化简

卡诺图虽然看起来很直观,但是他在逻辑变量 $\geq 5$ 时失去了直观上的相邻 $^{[2]}$ 同时增加了复杂度 $^{[3]}$ ,再仔细想想,目前生活中变量 $\leq 4$
的电路基本上凤毛麟角, 所以卡诺图与代数化简就失去了优势.

[2] 例如，一个5变量卡诺图可以表示为两个4x4矩阵叠在一起。尽管每个矩阵内部的相邻性还算容易理解，但跨矩阵的相邻性变得非常难以直观地识别。 下表中的四个格子就是相邻的 [3] 随着变量数量的增加，卡诺图的大小呈指数级增长。对于5变量卡诺图，它有2^5=32个格子，而6变量卡诺图则有2^6=64个格子。 这样的大图非常难以管理和视觉化

Step 1:补全最小项

编号	8	9	10	11	12	13	14
代码	1000	1001	1010	1011	1100	1101	1110

Step 2:合并格雷码

将这些最小项写成二进制的形式并含按1的个数分组,合并逻辑上相邻的最小项(两个只有一个字母不同,例如:ABCD和ABCD’可以归到同一组,编号8,9)同时使用最小项的十进制数作为对应编号, 无法合并的项用 $P_i$ 表示.

通过合并我们可以得到未合并的项以及Group 3 (显然Group 3也无法再合并了)
至此我们得到了所有的素蕴含项(其中包含着本质蕴含项)

Step 3:列出蕴含项表,找出本质蕴含项.

\	8	9	10	11	12	13	14
$p 1$					√	√
$p 2$	√	√	√	√
$p 3$	√		√		√		√
$p 4$	√	√			√	√

为了找到本质素蕴涵项，我们寻找只有一个“✓”的列。如果一列只有一个“✓”，这意味着最小项只能由一个素蕴涵项覆盖。这个素蕴涵项是本质的。不难发现本质蕴含项是 $p 2$ 和 $p 3$

所以素蕴含项是 $p 1$ 和 $p 4$

$f_{A,B,C,D}=AB’+ABC’+AD’$

这两个最终方程在功能上等同于原始的详细方程： $A B^{'} C D + A B^{'} C D^{'} + A B^{'} C^{'} D^{'} + A BC D^{'} + A B C^{'} D^{'} + A B C^{'} D + A B^{'} C^{'} D$

证明:

A	B	C	D	AB′	AD′	AC′	AB′+AD′+AC′	ABC′	AB′+AD′+ABC′
0	0	0	0	0	0	0	0	0	0
0	0	0	1	0	0	0	0	0	0
0	0	1	0	0	0	0	0	0	0
0	0	1	1	0	0	0	0	0	0
0	1	0	0	0	0	0	0	0	0
0	1	0	1	0	0	0	0	0	0
0	1	1	0	0	0	0	0	0	0
0	1	1	1	0	0	0	0	0	0
1	0	0	0	1	1	1	1	0	1
1	0	0	1	1	0	1	1	0	1
1	0	1	0	1	1	0	1	0	1
1	0	1	1	1	0	0	1	0	1
1	1	0	0	0	1	1	1	0	1
1	1	0	1	0	0	1	1	1	1
1	1	1	0	0	0	1	1	1	1
1	1	1	1	0	0	0	0	0	0

从真值表中可以看到，对于每一个输入组合，两个表达式 AB′+AD′+AC′ 和AB′+AD′+ABC’ 的输出都是相同的。因此，这两个表达式是相等的。

代码实现

C语言实现奎恩-麦克拉斯基化简法见码云

https://gitee.com/U-smiles/bit_code/blob/master/Q-M%20method/Q-M%20method/test.c

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/117630.html

A	B	C	D	AB′	AD′	AC′	AB′+AD′+AC′	ABC′	AB′+AD′+ABC′
0	0	0	0	0	0	0	0	0	0
0	0	0	1	0	0	0	0	0	0
0	0	1	0	0	0	0	0	0	0
0	0	1	1	0	0	0	0	0	0
0	1	0	0	0	0	0	0	0	0
0	1	0	1	0	0	0	0	0	0
0	1	1	0	0	0	0	0	0	0
0	1	1	1	0	0	0	0	0	0
1	0	0	0	1	1	1	1	0	1
1	0	0	1	1	0	1	1	0	1
1	0	1	0	1	1	0	1	0	1
1	0	1	1	1	0	0	1	0	1
1	1	0	0	0	1	1	1	0	1
1	1	0	1	0	0	1	1	1	1
1	1	1	0	0	0	1	1	1	1
1	1	1	1	0	0	0	0	0	0

A	B	C	D	AB′	AD′	AC′	AB′+AD′+AC′	ABC′	AB′+AD′+ABC′
0	0	0	0	0	0	0	0	0	0
0	0	0	1	0	0	0	0	0	0
0	0	1	0	0	0	0	0	0	0
0	0	1	1	0	0	0	0	0	0
0	1	0	0	0	0	0	0	0	0
0	1	0	1	0	0	0	0	0	0
0	1	1	0	0	0	0	0	0	0
0	1	1	1	0	0	0	0	0	0
1	0	0	0	1	1	1	1	0	1
1	0	0	1	1	0	1	1	0	1
1	0	1	0	1	1	0	1	0	1
1	0	1	1	1	0	0	1	0	1
1	1	0	0	0	1	1	1	0	1
1	1	0	1	0	0	1	1	1	1
1	1	1	0	0	0	1	1	1	1
1	1	1	1	0	0	0	0	0	0