2.2.3逻辑函数的表格法化简(Q-M法) 计算机辅助逻辑设计的方法 卡诺图化简法直观方便,过程简单明了, 但只适合于变量数<=4的函数。 Q-M( Quine-McCluskey)法和卡诺图 法的化简思路是一致的:两相邻最小项 可以合并消去一个变量.1952,1956] ·Q-M法是用分组表格法,把两相邻与项 合成为一新的与项,从而消去一变量。 它适合于变量数>4的函数,化简过程有 规律,可编程,便于计算机实现
2.2.3逻辑函数的表格法化简(Q-M法 ) ——计算机辅助逻辑设计的方法 • 卡诺图化简法直观方便，过程简单明了， 但只适合于变量数<=4的函数。 • Q-M(Quine-McCluskey) 法和卡诺图 法的化简思路是一致的:两相邻最小项 可以合并,消去一个变量. [1952，1956] • Q-M法是用分组表格法，把两相邻与项 合成为一新的与项，从而消去一变量。 它适合于变量数>4的函数，化简过程有 规律，可编程，便于计算机实现
4变量卡诺图的最小项 A00 011110 “相邻两个最小项中 00mm|mm2有一个变量互补” 如何体现? 01 丛最小项的编号上 11 m12 m13 m15 m14 看有什么规律? 10
4变量卡诺图的最小项 B A D C 00 01 11 10 00 11 01 10 m0 m1 m3 m2 m4 m5 m7 m6 m13 m12 m15 m14 m8 m9 m11 m10 “相邻两个最小项中 有一个变量互补” 如何体现？ 从最小项的编号上 看有什么规律？
QM方法的基本思想 ·“相邻两个最小项中有一个变量互补”在最小项编号 上的规律: ·以4变量卡诺图为例分析观察 m1同皿0,皿3,m5,m相邻,(每个m都有4个相邻) 它们的下标编号为:0001与0000,0011,0101,1001 结论:相邻最小项编号中“1”的个数差等于1; m同皿2皿4mg23个最小项不相邻,它们的下标编号 中1”的个数差等于0 政不相邻管们下称01出置,:吗等个最 这些最小项编号中“1”的个数差可能等于1,也可能 不等于1
Q-M方法的基本思想 • “相邻两个最小项中有一个变量互补”在最小项编号 上的规律： • 以4变量卡诺图为例分析观察： m1同 m0,m3,m5,m9相邻，（每个mi都有4个相邻） 它们的下标编号为：0001与0000,0011,0101,1001 结论：相邻最小项编号中“1”的个数差等于1； m1同 m2,m4,m8,3个最小项不相邻，它们的下标编号 中“1”的个数差等于0； m1还有 m6,m7, m10, m11, m12, m13, m14,m15等8个最 小项不相邻，它们的下标0110,0111,1010,1011……, 这些最小项编号中“1”的个数差可能等于1，也可能 不等于1
QM方法的基本思想(续) 根据最小项编号中“”的个数差就能判断是否相邻! 最小项编号中“1”的个数差: 等于0,最小项肯定不相邻! 等于1,最小项有可能相邻! ·算法步骤:(1)最小项分组:将最小项编号中“1”的 个数相同的最小项分在一组,并按组号大小排序; (2)相邻组比较:合并最小项编号中“1”的个数差 等于1的所有相邻最小项,得到函数的全部质项 (3)求必要质蕴涵项:从全部质蕴涵项中消去冗余项, 得到必要质蕴涵项,即为化简结果
Q-M方法的基本思想（续） • 根据最小项编号中“1”的个数差就能判断是否相邻！ • 最小项编号中“1”的个数差： 等于0，最小项肯定不相邻！ 等于1，最小项有可能相邻！ • 算法步骤：（1）最小项分组：将最小项编号中“1”的 个数相同的最小项分在一组，并按组号大小排序； （2）相邻组比较：合并最小项编号中“1”的个数差 等于1的所有相邻最小项，得到函数的全部质蕴涵项； （3）求必要质蕴涵项：从全部质蕴涵项中消去冗余项， 得到必要质蕴涵项，即为化简结果
步骤1求函数的全部质蕴涵项 函数的“质蕴涵项”就是不能再合并的最小项 先把F中的各m,按下标i中“1”的个数,由少到多 分组排队列表I。组号是m中所包含“1”的个数。 在表工的姐邻组闳进行逐项搜索,寻找相邻项。把可以合并 的记在表工中,并在表I中相应的最小项旁作记号“y” 表工所列均是变量数为n-1的与项(n是F的变量数),它们 同样按与项所含“1”的个数由少到多,分组排列。 重复上述过程,直到不能合并为止
步骤1 求函数的全部质蕴涵项 函数的“质蕴涵项”就是不能再合并的最小项. 先把F中的各mi，按下标i中“1”的个数，由少到多， 分组排队列表I。组号是mi中i所包含“1”的个数。 在表I的相邻组间进行逐项搜索，寻找相邻项。把可以合并 的记在表II中，并在表I中相应的最小项旁作记号“√” 。 表II所列均是变量数为n-1的与项（n是F的变量数），它们 同样按与项所含“1”的个数由少到多，分组排列。 重复上述过程，直到不能合并为止