15逻辑函数的表格法化简(Q-M法) 计算机辅助逻辑设计的方法 卡诺图法化简直观方便,过程简单明了, 但只适合于变量数<=4的函数 Q-M( Quine-MCO| askey)法和卡诺图法 的化简思路是一致的 ■QM法是用分组表格法,把两相邻与项 合成为一新的与项,从而消去一变量 它适合于变量数>4的函数,化简过程 规律性强,适用于计算机算法实现
1.5 逻辑函数的表格法化简(Q-M法 ) ——计算机辅助逻辑设计的方法 ◼ 卡诺图法化简直观方便，过程简单明了， 但只适合于变量数<=4的函数。 ◼ Q-M(Quine-McCluskey) 法和卡诺图法 的化简思路是一致的。 ◼ Q-M法是用分组表格法，把两相邻与项 合成为一新的与项，从而消去一变量。 它适合于变量数>4的函数，化简过程 规律性强，适用于计算机算法实现
Q-M方法的基本思想 什么情况下会出现“相邻两个最小项中有一个变量互补”? 从最小项的编号上看有什么规律? 观察:以4变量卡诺图为例: m1同m0,m3,m5m9相邻, 下标编号为:0001与500000011001,1001 m同m4,m8,ml0,m13等不相邻 下标编号为:0001与0100,1000,1010,1101 结论: 最小项编号中“1”的个数差=0,肯定不相邻 最小项编号中“1”的个数差>=2,肯定不相邻 最小项编号中“1”的个数差=1,可能相邻 按照最小项m下标编号中二进制数“1”的个数进行分组比较 可以化简
Q-M方法的基本思想 ◼ 什么情况下会出现“相邻两个最小项中有一个变量互补”？ 从最小项的编号上看有什么规律？ ◼ 观察：以4变量卡诺图为例： m1 同 m0,m3,m5,m9相邻， 下标编号为：0001与0000,0011,0101,1001 m1 同 m4,m8,m10, m13等不相邻， 下标编号为：0001与0100,1000,1010,1101 ◼ 结论： 最小项编号中“1”的个数差＝0 ，肯定不相邻 最小项编号中“1”的个数差>＝2，肯定不相邻 最小项编号中“1”的个数差＝1，可能相邻！ ◼ 按照最小项mi下标编号中二进制数“1”的个数进行分组比较， 可以化简
4变量 Karnaugh Map B A00011110 00 01 ma ms m, m 11 5m14 10
4变量Karnaugh Map 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法化简 步骤1寻找函数的全部质蕴涵项 先把F中的各mi,按下标i“1”的个数,由少到多 分组排队列表(见表I)。组号是m中所包含“1”的个数 在表I的相邻组间进行逐项搜索,寻找相邻项,把可以合 并的记在表I中,并在表I中相应的最小项旁作记号 √”。表II所列均是变量数为n-1的与项(n是F的变量 数),它们同样按与项所含“1”的个数由少到多,分组 排列 重复上述过程,直到不能合并为止
逻辑函数的Q-M法化简 步骤1 寻找函数的全部质蕴涵项 先把F中的各mi，按下标i中“1”的个数，由少到多， 分组排队列表(见表I) 。组号是mi中i所包含“1”的个数。 在表I的相邻组间进行逐项搜索，寻找相邻项，把可以合 并的记在表II中，并在表I中相应的最小项旁作记号 “√”。表II所列均是变量数为n-1的与项（n是F的变量 数），它们同样按与项所含“1”的个数由少到多，分组 排列。 重复上述过程，直到不能合并为止
逻辑函数的QM法化简(续) 例:F=∑m1(2468.910121315 表II 表I 组号 m DCBA 组号最小项DCBA 2,6010 0010 2,10 0|10 0100 46010 2 486902 1000 412 00 0110 8,9100 100 8,1010 010 8,12 00 100 01 3 110 2,13110 15111 313,1511-1
逻辑函数的Q-M法化简（续） 例: 8,12 1 _ 0 0 13,15 1 1 _ 1 12,13 1 1 0 _ 9,13 1 _ 0 1 8,10 1 0 _ 0 8,9 1 0 0 _ 4,12 _ 1 0 0 4,6 0 1 _ 0 2,10 _ 0 1 0 2,6 0 _ 1 0 15 1 1 1 1 3 13 1 1 0 1 12 1 1 0 0 10 1 0 1 0 9 1 0 0 1 6 0 1 1 0 2 8 1 0 0 0 4 0 1 0 0 2 0 0 1 0 1 组号 最小项 D C B A 表I 3 2 1 组号 m D C B A 表II √ √ √ √ √ √ √ √ √ = (2,4,6,8,9,10,12,13,15) 4 F m