卡诺图-降维

第6卷第3期湖北职业技术学院学报No.3Vol.62003年9月JournalofHubeiVocational-TechnicalCollegeSep.2003[收稿日期]2003―06―18[作者简介]万学斌（1963－），男，湖北孝感人，湖北职业技术学院计算机科学与技术系讲师，主要研究电工、电子、数字逻辑电路。·67·[文章编号]1671-8178-2003（03）－0067－04浅析卡诺图的降维万学斌（湖北职业技术学院，湖北孝感432000）[摘要]文章提出了一种多变量逻辑函数化简的卡诺图法----降维卡诺图法，从而有效扩展了卡诺图化简的适用范围。[关键词]卡诺变量；降维变量；卡诺图；降维卡诺图[中图分类号]TP331.2[文献标识码]A在数字逻辑电路中，化简逻辑函数是分析和设计数字逻辑电路的重要理论基础和基本技能。我们知道，逻辑化简有两种方法：一种是代数法化简；另一种是卡诺图化简。前者化简过程技巧性强，结果是否为最简还不太容易确定，而后一种方法却克服了前者的不足，使化简变得更加可操作，更重要的是它还可以化简具有随意项的逻辑函数，这是代数法化简无能为力的，但是卡诺图法化简受逻辑变量个数限制，当逻辑变量个数多于5时，卡诺图化简就显得有些麻烦，如果使用引入变量的卡诺图化简，就会使多变量函数化简变得简单[1]，下面介绍引入变量的卡诺图化简问题。一卡诺化简的依据和概念卡诺图法化简是利用格雷码表，直观地反映逻辑函数最小项之间逻辑相邻关系的方格图，它不仅是表达逻辑函数的一种方式，而且也是化简逻辑函数的一种工具。在卡诺图上把逻辑相邻项安排在几何相邻位置，使相邻项能简化为一个与项，同时也使逻辑变量个数减少。当变量个数多于五个时，卡诺化简就显得有些麻烦，可以使用引入变量的卡诺图化简，这样一来就使得卡诺图中的变量数n和逻辑变量数m不再相等（mn），为讨论方便，定义以下概念：1、引入变量的卡诺图称为降维卡诺图。2、k=m－n为卡诺图降维阶数，k为降维变量数，m为逻辑变量数，n为卡诺变量数。3、k=1为一阶降维卡诺图，k≥2为高阶降维卡诺图。当k=0时，每一个小方格代表一个最小项，小方格中只能是1（表示该最小项存在）和0（表示该最小项不存在）或者是随意项。当k≠0，使得降维卡诺图面积表示只有原卡诺图表面积的1/2k，它的每个小方格实际上是原卡诺图2k个最小项的集合。为此，小方格的填写就有四种可能的情形：⑴、填写1，表示函数包含有2k个最小项，即该最小项中只包含有卡诺变量而不包含降维变量。⑵、填写0，表示一个最小项也不包含，即卡诺变量和降维变量都不包含。⑶、填写降维变量函数，表示2k最小项中的部分最小项之和。⑷、填写随意项。万学斌：浅析卡诺图的降维·68·二用降维卡诺图表示与或函数1、卡诺图快速填写方法用卡诺图表示逻辑函数即填写卡诺图，初学者往往是把一般与或表达式首先转换为最小项与或表达式，然后填图。其实，卡诺图的填写是十分简单的，只需要把已知的逻辑变量值代入逻辑函数表达式，求出逻辑函数值，填入卡诺图对应的小方格即可。然而这种方法的运算量大，操作不易，我们在学习了卡诺图化简后，卡诺图的填写就可以利用卡诺图化简思想来快速填写了。也就是说，卡诺图化简可以把一个卡诺圈简写为一个与项，而快速法填写卡诺图就可以将一个与项展开为一个卡诺圈。不过在快速填写卡诺图时，我们掩去了卡诺圈，这是因为我们不是在进行卡诺化简，而是在填写逻辑函数的卡诺图，用卡诺图在表达逻辑函数，为卡诺图化简作准备。例1：填写F=A＋BC＋ABC的卡诺图解：函数F的卡诺图为图一，此处为了表达清楚，把每个与项对应的卡诺圈都没有掩去。BCAOOO1111OOOO1O11111图1F的卡诺图ABC＝ABC也就是说，下面四个1对应于A，A也可散开为下面的四个1；BC对应11列的两个1；ABC对应着1行11列的卡诺圈。在卡诺化简时应该掩去所有卡诺圈。掌握了卡诺图的快速填写方法，将会为以后卡诺化简有很大的帮助。2、与或函数降维卡诺图的填写多变量与或函数中的一个与项如何填入降维卡诺图?根据卡诺图化简依据和卡诺图快速填写方法就有以下三种情况（与或函数中不含随意项的问题）。⑴、当逻辑函数的与项中只含有卡诺变量时，则如同一般卡诺图填写方法，按上例填写，则在与项对应的卡诺圈中小方格为1。⑵、当逻辑函数的与项中既含有卡诺变量，又含有降维变量时，则在与项对应的卡诺圈中所有小方格填写降维变量的与项。⑶、当逻辑函数的与项只有降维变量时，则在卡诺图中所有小方格中填写降维变量与项。把与或函数的每个与项按上述规则填入降维卡诺图就得到了该函数的原始降维卡诺图，经过简单的逻辑代数运算就得到了该函数的降维卡诺图。例2：填写一阶降维卡诺图解：取D为降维变量，A、B、C为卡诺变量，则有三变量的一阶降维卡诺图为图2。AB=∑m(6，7)，BC=∑m(3，7)(情形1)DBA=∑m(0，1)·D(情形2)D=∑m(0，1，2，3，4，5，6，7)·D(情形3)BCAOOO1111OOD+D（0）D+D（1）1+D（3）D（2）1D（4）D（5）1+1+D（7）1+D(6)图2填写F的原始降维卡诺图图2运算后即为F的降维卡诺图3。BCAOOO1111OO111D1DD11图3F的一阶降维卡诺图三用降维卡诺图化简逻辑函数在不包含随意项的逻辑函数降维卡诺图中，只含有0、1、降维变量项，根据卡诺化简的依据，用降维卡诺图化简逻辑函数原则如下：1、首先对降维卡诺图中的“1”的小方格，按卡诺图化简的一般原则化简，即在覆盖函数中的所有最小项的前提下，卡诺圈的个数达到最少，每个卡诺圈的面积达到最大[2]。得到的与项只有卡诺变量，而不含降维变量。2、然后对降维卡诺图中降维变量的小方格进行合并，合并原则也和对“1”的合并原则相似，不过CABABCCBACBAAABCBCABCBCDDBAABF湖北职业技术学院学报2003年第3期第6卷第3期·69·这时“1”的小方格可视为含有任意项的方格，得到卡诺变量的与项必须再与上降维变量项。例3：以例2为例化简一阶降维函数F解：根据降维卡诺图4，据化简原则，BCAOOO1111OO111D1DD11图4F的化简由图4得：BCDABBAF此题化简也可以把m1和m3合并为CA，则：CADABBAF例4：用二阶降维卡诺图化简逻辑函数BCDDBAABF解：选取A、B为卡诺变量，C、D为降维变量，则F的二阶降维卡诺图为图5。AB=∑m(3)DBA=∑m(0)·DBC=∑m(1，3)·CD=∑m(0，1，2，3)·DBAO1OD+D（0）D+C（1）1D（2）1+D+C（3）图5填写F的二阶降维卡诺图图5运算后为图6，BAO1O1C+D1D1图6F二阶降维卡诺图由图6化简得：BCDABBAF化简后的结果与前面讲的一阶降维卡诺图法化简的结果完全相同，实际上也可用四变量卡诺图化简来验证例3和例4结果，从而证明降维卡诺图法的正确性。四含有随意项的降维卡诺图的化简[3]逻辑函数中随意项是指逻辑变量组合不会出现，逻辑函数值随意；或者逻辑变量组合出现后，逻辑函数值随意。随意项逻辑函数值可视为0或者1[1]。为了把随意项和确定项区分开来，随意项函数值填入卡诺图小方格时用括号括起来，由于其逻辑函数值可为1或为0，因而在合并时视逻辑化简的需要选定，充分地利用好随意项，以便把逻辑函数化简到最简形式。其填写原则和化简原则与不含随意项的情况相似，首先化简小方格中的“1”项，然后化简含降维变量的项。这里仅举一例，不再赘述。例5：用一阶降维卡诺图法化简具有随意项的逻辑函数F（A、B、C、D）=∑m（0，1，5，7，8，11，14）+∑d（3，4，9，15）解：选取A为降维变量，B、C、D为卡诺变量，则：F=A·∑m(0，1，5，7)+A·∑m(0，3，6)+A·∑d(3，4)+A·∑d(1，7)对应一阶降维卡诺图为图7，图7运算后的卡诺图为图8。CDBOOO1111OOA+AA+（A）A+（A）O1（A）AA+（A）A图7填写F的原始一阶卡诺图CDBOOO1111OO11（A）1（A）01（A）A1（A）A图8F的一阶降维卡诺图据图8化简有：DBABCCBDAFCDABCCBDAF或万学斌：浅析卡诺图的降维·70·加最后项CD或DB的原因是：既然有AD对应的卡诺圈，在卡诺化简时，CDB处的“1”就是一个确定的“1”，应该单独组项。这一点在含有随意项的降维卡诺图的化简中应该引起特别的注意。五降维变量的选择和降维卡诺图化简逻辑函数的步骤至于逻辑函数中卡诺变量和降维变量的选择，原则上讲是任意的，但是降维变量和卡诺变量选择得合理，降维卡诺图就简单。一般来讲，为保证降维卡诺图简单，把逻辑函数中逻辑变量出现次数较少的变量作为降维变量，出现较多的变量作为卡诺变量，如果有几个变量出现的机会均等，这时就需要把几种情况全部作出来，从中选出较简单的一种方法[4]。只有这样降维卡诺图中的小方格中的降维变量的与或项才最简单。对于以上例3中，若选C为降维变量，求解还要简单，请读者自己完成。据以上讨论可得出，利用降维卡诺图化简逻辑函数的步骤如下：1、合理选择卡诺变量和降维变量。2、根据降维卡诺图的填写原则填写降维卡诺图。3、根据降维卡诺图的化简原则化简逻辑函数。六结束语降维卡诺图化简逻辑函数的最大优点就在于它可以化简多变量的逻辑函数，为此，本文化简一六变量逻辑函数来结束此文。例6：化简逻辑函数ADEBDBDFFEBABDDCAW解：由于E、F出现的次数较少，故而选取A、B、C、D为卡诺变量，E、F为降维变量。利用四变量二阶降维卡诺图表示该函数为图9。CDABOOO1111OOOOOOOO1O1+F+E1+F+EO11O1+1+F+E+11+F+E+1O1OFE1+FE+1FE+1FE图9填写W的二阶原始降维卡诺图运算卡诺图9得到W的降维卡诺图10。CDABOOO1111OOOOOOOO1O11O11O11O1OFE11FE图10W二阶降维卡诺图据图10化简得：FEBABDADW[参考文献][1]李亚伯.数字电路与系统[M].北京：电子工业出版社，1998:30－33.[2]欧阳星明.数字逻辑[M].武汉：华中科技大学出版社，2000:44－58.[3]伍瑜.论含约束项的降维卡诺图[J].电子科技大学学报，2000，（3）:286-287.[4]伍瑜.卡诺图降维变量的选择[J].成都大学学报，1999，（4）：32－35.（特约审稿人：肖锡武）AStudyofHiddenKarnaughMapWANXue-bin（HubeiVocational-TechnicalCollege，Xiaogan432000,Hubei,China）Abstract:ThisessayputsforwardakindofKarnaughMapofsimplifiedmulti-variablelogicalfunction---HiddenKarnaughMap---whichextendsthescopeofapplicationofKarnaughMap.KeyWords:KarnaughVariable;HiddenVariable;KarnaughMap;hiddenKarnaughMap