《武汉工程大学学报》 2011年01期
100-103
出版日期：2011-01-30
ISSN:1674-2869
CN:42-1779/TQ
增强型QuineMcCluskey算法及其实验
0引言数字系统中的逻辑电路按其结构可分为组合逻辑电路和时序逻辑电路两大类型.组合逻辑电路是一种逻辑电路,它的任一时刻的稳态输出,仅仅与该时刻的输入变量的取值有关,而与该时刻以前的输入变量取值无关.在组合逻辑电路中,每个输出都是其输入变量的逻辑函数.从电路结构分析,组合电路由各种逻辑门组成,网络中无记忆元件,也无反馈线［1］.时序逻辑电路是指电路任何时刻的稳态输出不仅取决于当前的输入,还与前一时刻输入形成的状态有关.这种电路跟组合逻辑电路相反,它的输出结果是依照目前的输入和先前的输入有关系,拥有储存元件(内存)来存储信息.在时序逻辑电路中,若采用Mealy型状态机描述,则每个输出和内部状态都是其输入变量和内部状态的逻辑函数;若采用Moore型状态机描述,则每个输出都是其内部状态的逻辑函数,每个内部状态都是其输入变量和内部状态的逻辑函数.可见,逻辑函数是描述数字电路功能的重要方法［2］.逻辑函数化简,是为了获得最简化的逻辑电路,从而提高电路速度、安全性等性能,减少电路资源消耗.逻辑函数化简,没有严格的原则,它一般是依以下几个方面进行:(1)逻辑电路所用的门最少;(2)各个门的输入端要少;(3)逻辑电路所用的级数要少;(4)逻辑电路要能可靠地工作.常用的化简方法有公式化简法［7］、卡诺图化简法［3］、QuineMcCluskey化简法［45,8］和Espresso启发式化简法［6,9］等.公式化简法适于做书面逻辑推导,在形式化逻辑演算中比较常用,由于规则较多,EDA软件中较少采用.卡诺图化简法在简单的数字逻辑电路设计中常用,其优点是直观、方便、容易掌握,缺点是当变量的数目(大于6)较大时,图形庞大复杂,并且不易编程实现.QuineMcCluskey化简法在功能上等同于卡诺图,能对任意数目变量构成的布尔函数化简,其优点是采用了表格形式而不是图形方式,这使它更适于计算机实现,并且它还给出了检查逻辑函数是否达到了最小化形式的确定性方法,可以判断算法终止的时机,可获得最优结果.Espresso化简法会对一个逻辑系统做一些单一化假设,所以它运行的非常快,甚至是大型系统也非常快,但不能保证获得最优结果.1QuineMcCluskey算法QuineMcCluskey算法(简称QM算法)是A+A′=1最小化逻辑函数的一种方法.1.1基本定义定义1(真值)在数字逻辑中,真值、布尔值或逻辑值是指真(用1表示)、假(用0表示)、未知(或任意)(用X或x表示),简写为v.定义2(蕴涵项)一个蕴涵项(Implicant Term)就是一个由若干真值的有序序列构成一个真值向量,记为V.定义3(最小项)对蕴涵项V,若每个变量的真值必须而且只能以0或1的形式出现一次,则称其为最小项(Minterm).定义4(蕴含最小项)对蕴含项V,若V=v1v2…x…vn,则可将其分解为V1=v1v2…0…vn和V2=v1v2…1…vn,从而派生出两个新的蕴含项V1和V2;如此重复,直到不可分解为止,即输入向量均为最小项,产生的全部最小项称为蕴含项V的蕴含最小项,记为［V］.定义5(蕴含)对于蕴涵项V1和V2,若［V1］［V2］,则称V1蕴含于V2,记为V1V2.定义6(真值表)一个真值表是一个描述逻辑函数的输入向量和输出变量之间映射关系的二维表,由若干使输出变量取1值的蕴涵项组成,简写为T.定义7(质蕴涵项)对于V∈T,若不存在V′∈T,V′≠V,使VV′,则称V为质蕴涵项(Prime Implicant),简称为质项.该定义表明质蕴含项蕴含的全部最小项不能由其他蕴涵项所包含,在逻辑函数表达式中表现为该“与项”描述的逻辑关系不能由其他与项所代表.定义8(必要质蕴涵项)对于V∈T,若对V′∈T,V′≠V,且V″∈［V］使V″［V″］,则称V为必要质蕴涵项(Essential Prime Implicant),简称为必要质项.该定义表明必要质蕴涵项在描述输入和输出之间的逻辑关系时是必不可少的,在逻辑函数中表现为一个质蕴涵项蕴含有不被函数的其他任何质蕴涵项所蕴含的最小项.第1期陈付龙,等:增强型QuineMcCluskey算法及其实验
武汉工程大学学报第33卷
1.2算法原理QM算法主要分两个步骤:第一步找到这个逻辑函数的所有质蕴涵项.对某个蕴涵项,其匹配项是指当且仅当有一位与其相反的蕴涵项,也称逻辑相邻项.找质蕴涵项的过程,就是对蕴涵项与其逻辑相邻项,利用A+A′=1律进行归约的过程.例如,t=0100,则其匹配项t′可能为1100、0000、0110或0101.其中,利用A+A′=1律,0100与1100归约为X100.第二步在找到的所有质蕴涵项中继续找到所有的必要质蕴涵项,去掉非必要质蕴涵项.1.3算法评价由于在n个输入变量的逻辑函数中,最小项数目最多可达2n,因此,搜索质蕴涵项是一个NP完全问题,QM算法的时间复杂度依赖于搜索空间大小,随输入变量数目大小而呈指数增长.2增强QuineMcCluskey算法实现传统的QM算法第一步多从只拥有最小项的真值表开始,而真值表中的最小项数目是算法时间复杂度的最重要因素,数目越大,算法完成需要的时间越多.特别是与Espresso算法相比,QM算法的执行效率较低.但随着计算机性能的提升,在实际设计中,可对真值表大小进行控制,利用更多化简规则,从而减少QM算法执行时间,获得某些应用的最优化设计.2.1归约方法在真值表中,可以用蕴涵项代替最小项,例如{01,1X}{01,10,11}.但是,01和1X无法用传统的A+A′=1归约.为此,须再使用A′B+A=A+B进行归约,从而获得质蕴涵项{X1,1X}./*算法:2.1 reduceTerm功能:利用A+A’=1和A’B+A=A+B归约输入:蕴涵项Term1,Term2输出:质蕴涵项表*/Flag1←true;//未发现可用A+A’=1归约Flag2←true;//未发现可用A’B+A=A+B归约Term←Φ;while (Term1≠Φ && Term2≠Φ){//取向量第一个真值V1←first(Term1);V2←first(Term2); //取向量剩余真值Term1←rest(Term1); Term2←rest(Term2); switch (V1,V2){case (1,1):case (0,0):case (X,X): Term←Term∪{V1};case (0,1):case (1,0): //发现A+A’=1if Flag1 then {Term←Term∪{X}; Flag1←false;}case (1,X): //发现A’B+A=A+Bif Flag2 then {Term←Term∪{1}; Flag2←false;}}}return Term;//返回归约后的结果/**/2.2查找质蕴涵项/*算法:2.2 find Prime Implicant功能:找质蕴涵项 输入:单输出变量真值表TruthTable输出:质蕴涵项表*///从真值表提取蕴涵项ImplicantTable ← extractImplicant(TruthTable); PrimeTable←Φ;//初始化质蕴涵表ActiveTable←Φ;//初始化活动表while (ImplicantTable≠Φ){//当蕴涵表不空//从蕴涵表中取蕴涵项Term←fetchTerm(ImplicantTable); ImplicantTable←ImplicantTable{Term};//删除该蕴涵项ActiveFlag←false;//置不活动标记for each Term’∈ ImplicantTable do{//对每个蕴涵项NewTerm←reduceTerm(Term,Term’);//归约if ||NewTerm||=||Term|| then {//若逻辑相邻//即归约后的向量长度与被归约向量长度一致Flag←true;//置活动标记//加入蕴涵表ImplicantTable←ImplicantTable∪{NewTerm}; ActiveTable←ActiveTable∪{Term’};//加入活动表}}if ActiveFlag then ActiveTable←ActiveTable∪{Term}//若活动else if Term ActiveTable then PrimeTable←PrimeTable∪{Term};//加入质蕴涵表}return PrimeTable;//返回质蕴涵表/**/2.3查找必要质蕴涵项/*算法:2.3 find Essential Prime Implicant功能:找必要质蕴涵项输入:质蕴涵项表PrimeTable输出:必要质蕴涵项表EssImpTable*/Minterms←findMinterms(PrimeTable);//收集所有最小项EssImpTable←Φ;//取第一项初始化必要质蕴涵表while (Minterms≠Φ){//当最小项表不空MinTimeTerms←minTime(Minterms,PrimeTable);//查找被PrimeTable中质蕴涵项蕴含次数最少的最小项Term←maxTerm(MinTimeTerms,PrimeTable);//查找蕴含的最小项与MinTimeTerms交集最多的质蕴涵项EssImpTable← EssImpTable∪{Term};Minterms←MintermsMinTimeTerms;PrimeTable←PrimeTable{Term}}return EssImpTable;//返回必要质蕴涵表/**/3QuineMcCluskey算法性能评测QM算法和增强QM算法性能比较见表1.表1QuineMcCluskey算法性能对比
Table 1Performance comparison of QuineMcCluskey algorithms
测试用例QM算法增强QM算法表长度执行时间/ms表长度执行时间/ms83编码器82.6682.6638译码器82.6682.66优先级83编码器255138 578.008750.93BCD编码器100.94100.94优先级BCD编码器1 023>1 000 000.00106 725.15BCD译码器103.91103.91BCD7段LED显示译码器102.96102.9674138优先编码器256>1 000 000.00102 466.4074138译码器408751062.031位全加器80.9480.941位比较器40.3240.324位比较器1 171>1 000 000.0091 899.372路多路器80.4740.314路多路器6447.0087.504路分配器80.3180.31比较发现,增强QM算法在某些应用设计中具有更加优异的性能.4结束语通过压缩真值表的大小,利用更多化简规则,使QM算法性能得到显著提升,从而使其对大数量输入的数字电路最优化设计具有应用价值,如数码显示与译码电路［1011］.在《数字逻辑》课程教学中,对比传统的QM算法,讲授增强型QM算法,可加强对数字逻辑简化的理解,并在实际设计中进行运用