联合卡诺图在逻辑电路分析中的应用

卢容德

(长江大学电子信息学院，湖北 荆州 434023)

联合卡诺图在逻辑电路分析中的应用

卢容德

(长江大学电子信息学院，湖北 荆州 434023)

深入分析了卡诺图的属性，讨论了卡诺图与真值表的关系，指出卡诺图就是二维真值表。将分离的多个卡诺图结合在一起，构成了联合卡诺图。举例说明了联合卡诺图在多输出逻辑函数化简中的应用。讨论了次态联合卡诺图的结构，揭示了次态联合卡诺图与状态转换图的关系。提出了同步时序逻辑电路联合卡诺图分析法的步骤并举例说明了它的应用。在异步时序逻辑电路的分析中，提出了描述电路状态的严密的次态方程和有效的联合卡诺图分析法。

二维真值表；联合卡诺图；逻辑电路；次态方程；状态转换图

卡诺图由美国工程师Maorice Karnaugh 于1953年提出[1]，用于逻辑函数的化简。作为逻辑函数的图形化简法，与代数法相比，卡诺图法具有直观、简便的独特优点，在逻辑电路中广泛应用。在逻辑电路的分析与设计中，卡诺图广泛用于组合逻辑电路，而在时序电路中应用较少[2,3]。国外有关数字电路方面的教科书，卡诺图在时序电路中的应用则更少[4,5]。其原因是对卡诺图的属性的认识不够全面，对卡诺图的应用缺乏深入的研究。针对这种情况，笔者对卡诺图的属性作了全面剖析，提出了联合卡诺图的概念，对卡诺图在逻辑电路中的应用作了较为深入的研讨。

1 对卡诺图的再认识

1.1卡诺图与真值表

图1 逻辑函数的卡诺图

卡诺图是按照相邻规则排列的表示逻辑函数全体最小项的小方格的集合，由于卡诺图包含了逻辑函数的全体最小项，所以，它可以用来表示任意逻辑函数。图1(a)就是一个4变量的卡诺图，具有16个小方格，它们分别表示4变量逻辑函数的全体最小项∑m(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15)，每个小方格所代表的最小项用对应的阿拉伯数值标明。自变量的取值按格雷码排列，保证了卡诺图的相邻性。图1(b)是某4变量逻辑函数F(A,B,C,D)= ∑m(2,3,5,6,7,10,11,14,15)的卡诺图，在填写卡诺图时，F所包含的最小项对应的小方格写入1，F不含的最小项对应的小方格写入0或空着不写。卡诺图用一行和一列代码，穷举了自变量的取值，用卡诺图表示逻辑函数时，按照原变量对应代码“1”所对应的行或列，反变量对应代码“0”所对应的行或列这样的规则填写，从而使确定逻辑函数的值不需要通过计算。

函数F的真值表如表1所示，将真值表与卡诺图比较，不难发现，在真值表中，逻辑函数的取值排成了一列，即按一维方式排列；而在卡诺图中，逻辑函数的取值按面排列，即按二维方式排列。所以，从本质上说，卡诺图是表示逻辑函数的二维真值表。显然，用卡诺图描述逻辑函数的真值，要比真值表简便，尤其是变量较多时，真值表就显得繁琐了。

表1 函数F的真值表

既然卡诺图就是真值表，那么，它就能够用来描述任何二值逻辑问题，既可以用于组合逻辑电路，又可以用于时序逻辑电路。

1.2多输出逻辑问题与联合卡诺图

实际逻辑问题中，经常遇到多个原因产生多个结果的问题，用逻辑函数描述，就是用一组输入变量表示多个输出函数，用电路实现这种逻辑关系，会涉及到多输出逻辑函数的化简。采用卡诺图法，分别独立化简各个逻辑函数，一般不能保证逻辑电路整体最简。因为各输出函数具有某些共同的部分，应该将它们当作一个整体考虑，在逻辑电路中实现对公用项共享，可以使电路整体最简。解决这个问题的最好办法，就是将各个逻辑函数的卡诺图结合在一起，构成所谓的联合卡诺图。

图2就是一个3输出逻辑函数的联合卡诺图，为了使卡诺图清晰易辨，小方格中只填1，不填0。根据卡诺图，容易得到对应的逻辑函数表达式为：

1.3次态函数与次态联合卡诺图

描述时序电路状态的的次态联合卡诺图如图3所示，图3(a)表示其结构，图3(b)表示含有一个输入变量及三位触发器的时序电路的次态联合卡诺图。小方格中的逻辑值的顺序，与次态函数名一一对应。

图2 三输出逻辑函数的联合卡诺图 图3 次态联合卡诺图

图4 图3 (b)的状态转换图

根据图3(b)，很容易得出其状态转换表和状态转换图。状态转换表是一个17行7列的大表格，状态转换图如图4所示。根据状态转换图不难判断，电路是一个8进制可逆计数器。

上例充分体现出联合卡诺图在时序电路中应用的优点，即一图多用。实际上，次态联合卡诺图既是一个二维的状态转换表，又是一个表格式的状态转换图。任何时序电路，都可以用次态联合卡诺图来描述。

2 联合卡诺图的应用

2.1多输出逻辑函数的化简

采用各自独立的卡诺图化简多输出逻辑函数，为了得出整体最简的结果，对卡诺圈要多次修改，化简过程显得比较麻烦[6]。图2所表示的3个逻辑函数，就是文献[6]讨论的一个例子。这里，用联合卡诺图法化简这些逻辑函数。为了方便形象思维，将图2改画成图5(a)，用各函数的下标序号替代了联合卡诺图中对应小方格中的“1”，这样处理，画卡诺圈时更为直观。

按照卡诺图法化简逻辑函数的规则，不难画出图5(a)所示的卡诺圈，并很方便地得到各逻辑函数的最简与或式：

图5 利用联合卡诺图化简多输出逻辑函数

显然，这种方法比文献[6]介绍的传统的分离式卡诺图法方便得多，文献[6]在化简这些多输出函数时，对卡诺圈作了3次修改。卡诺图中独立卡诺圈的个数，就是对应的逻辑电路中第一级门电路的个数。例如，如果用与非门实现，该例中第一级需要5个与非门，输出级需要3个与非门，总共8个与非门就可以解决问题。

2.2时序电路的分析

文献[2]是国内最具影响力的数字电子技术教材，在时序电路的分析方法中，它并没有采用卡诺图法，而是传统的计算法，即根据电路的状态方程将电路的次态一一计算出来，列出状态转换表，最后得出状态转换图；在时序电路的设计方法中，本来采用了联合卡诺图，但在确定各级的次态方程时，却又把联合卡诺图拆开了，给自启动的设计带来了不便。国外的教材在时序电路的应用中，卡诺图一般只用于驱动函数的单独描述，还是属于组合逻辑电路的范畴。文献[5]实际上采用了联合卡诺图，但它没有称作卡诺图，而是称为“转换表”(transition table)，也就是说，文献[5]对卡诺图的定义还严格地限定在单个输出函数的前提下，没有从本质上认识卡诺图。

1) 同步时序电路的分析 卡诺图法用于同步时序电路分析的步骤是：①根据已知电路写出各触发器的驱动方程(或称为激励方程)和电路的输出方程；②将驱动方程代人触发器的特性方程，写出各触发器的次态方程(或称为状态方程)；③写出次态方程的联合卡诺图；④根据联合卡诺图确定电路的状态转换图；⑤判断电路的功能。

根据联合卡诺图确定电路的状态转换关系，避开了计算法的繁琐计算过程，可以使电路的分析过程得到充分简化。

这里，以文献[2]中例6.2.1说明联合卡诺图法的应用。

根据文献[2]的分析，电路的次态方程为:

上式中，Q的上标n+1表示触发器的次态，没有上标则表示触发器的现态。为了得出电路的状态转换图，文献[2]在设定电路的初始值后，经过8轮24次计算，得出了电路的状态转换表，进而得出状态转换图，确定出电路的功能。显然，这种方法比较繁琐，如果再增加一个触发器，将要计算16轮64次。

前面已经说明，卡诺图是二维真值表。根据逻辑函数填写真值表，需要穷举自变量的值，再通过逻辑运算求得对应的函数值。而用卡诺图表示逻辑函数，是根据逻辑函数表达式直接在卡诺图中表示出的，这里不需要任何计算。根据时序电路的次态方程，画出次态卡诺图是一项很容易做的工作。分离式的卡诺图对状态转换的分析意义不大，不过它可以用来构成状态转换表而不需要计算。但是，当把这些次态卡诺图结合在一起构成联合卡诺图时，逻辑电路的状态转换图就构造出来了。

图6 文献[2]中的同步时序逻辑电路 图7 图6的次态联合卡诺图

图8 图6的状态转换图

根据次态方程，很容易画出图7所示的次态联合卡诺图，再根据卡诺图所表示的因果关系，可以很方便地画出图8所示的状态转换图。根据状态转换图不难判断，该电路是一个同步7进制加法计数器，电路在状态110保持期间输出高电平进位信号。该电路还具有自启动功能，无效状态111可以自动进入000状态。

2)异步时序电路的分析 异步时序电路分析的步骤与同步时序电路分析的步骤基本相同，不同的是首先要根据电路写出时钟方程，次态方程中要标明时钟方程，卡诺图中要标明时钟的有效区。在填写次态卡诺图时，一定要注意在卡诺图的时钟有效区外，触发器因没有时钟信号，其状态保持不变。在卡诺图的时钟有效区内，按次态方程的描述填写。

图9 文献[2]中的异步时序逻辑电路

图9给出了文献[2]中例6.2.4讨论的异步时序逻辑电路，电路中的触发器是负边沿触发的JK触发器。

根据逻辑电路，结合文献[2]的分析，不难得出考虑时钟信号的次态方程：

(1)

触发器Q0的时钟信号由电路的时钟源提供，与同步时序电路相同，次态方程中时钟变量不必列出；其余各触发器的时钟信号由电路中相关触发器的负跳变提供，对于触发器的次态函数，时钟变量和触发器的现态变量是逻辑与的关系。表达式中，向下的箭头表示对应触发器输出端的负跳变。当Q0出现负跳变时，“Q0↓”为“真”，其逻辑值为“1”，次态函数按逻辑表达式取值。

值得注意的是，当Q0没有出现负跳变时，“Q0↓”为“假”，其逻辑值为“0”。但此时次态函数的值并不是0，而是保持原来的逻辑值不变。这就是说，次态方程(1)只是描述了各触发器在时钟信号存在时其次态函数的逻辑值。所以，描述图9所示电路的严密的次态方程应为：

(2)

式(2)是用卡诺图法分析异步时序逻辑电路的理论依据。按照卡诺图与逻辑函数的对应关系，不难得出描述图9所示电路的次态联合卡诺图，如图10(a)所示。

图10 图9所示电路的卡诺图分析

填写联合卡诺图的步骤是，首先填写Q0的次态卡诺图，并在卡诺图中标明Q0的负跳变区；然后，填写Q1和Q3的次态卡诺图，并在卡诺图中标明Q1的负跳变区；最后，填写Q2的次态卡诺图。在填写Q1、Q2和Q3的卡诺图时，要注意在卡诺图的时钟信号有效区外，触发器保持不变；而在卡诺图的时钟信号有效区内，填写方法与同步型电路相同。图10(a)中，用粗实线框标出了Q0的负跳变区，用虚线框标出了Q1的负跳变区，使卡诺图的填写方便直观。

在逻辑电路的联合卡诺图完成后，其状态转换图就很容易得出，因为次态联合卡诺图就是一个表格式的状态转换图。根据图10(a)，容易得出图10(b)所示的状态转换图。显然，这个电路是一个具有自启动功能的异步型10进制加法计数器，电路在状态1001保持期间输出高电平进位信号。

在分析图9所示的电路时，文献[2]采用的是传统的分析方法。这个电路共有16个状态，对于电路每个次态的分析，都要事先考虑相关触发器的时钟信号是否存在，然后根据次态方程，用计算与列表相结合的方式，逐个状态一步一步地进行分析，其过程相当麻烦。

相比之下，无论是分析同步时序电路，还是异步时序电路，联合卡诺图法具有清晰快捷的优点。这里的关键，在于各次态函数卡诺图的联合，使每个小方格中的逻辑值的组合，都代表电路的一个状态。这些逻辑值的获得，不需要通过计算，而是直接通过用卡诺图表示逻辑函数的一般方法填写的。

3 结 语

采用联合卡诺图法化简多输出逻辑函数，可以避免传统的卡诺图法对卡诺圈要作多次比对、修改的弊端。在时序电路的分析中，次态联合卡诺图中每一个小方格中的逻辑值的组合，代表了时序电路的一个状态。次态联合卡诺图的小方格与时序电路状态对应关系的建立，是将分离的卡诺图联合起来的结果。对于时序电路，次态联合卡诺图是优于状态转换表的一种基本描述方式，它避开了计算法确定次态函数逻辑值的弊端。时序电路的联合卡诺图分析法，具有直观、简便、快捷的优点，是时序电路分析的有效工具。

[1]Karnaugh M.The Map Method for Synthesisf Combinational Logic Circuits[J].Transactions of American Institute of Electrical Engineers ，1953，72：593～599.

[2]阎石.数字电子技术基础[M].第5版.北京：高等教育出版社，2006.

[3]刘常澍.数字逻辑电路[M].北京：高等教育出版社，2008.

[4][美]Thomas L. Floyd Digital Fundamentals[M].9th Ed.北京：电子工业出版社，2006.

[5]Jain R P.Modern Digital Electronics[M].3rd Ed.New York: McGraw-Hill, Inc，2003.

[6]韩天荣.具有多输出端逻辑电路化简的卡诺图法[J].集宁师专学报，2005，27(4):16～17

[编辑] 易国华

2009-08-01

卢容德(1947-)，男，1970年大学毕业，教授，现主要从事电子技术方面的教学与研究工作。

TM131.5

A

1673-1409(2009)04-N061-05