尚奥,裴晓鹏,吕迎春,陈泽华.基于等价关系的完全确定时序逻辑电路状态化简算法[J].计算机科学,2018,45(1):118-121
基于等价关系的完全确定时序逻辑电路状态化简算法
State Reduction Algorithm for Completely Specified Sequential Logic Circuit Based on Equivalence Relation
投稿时间:2017-03-03  修订日期:2017-06-19
DOI:10.11896/j.issn.1002-137X.2018.01.019
中文关键词:  状态化简,等价关系,粒计算,时序逻辑电路
英文关键词:State reduction,Equivalence relation,Granular computing,Sequential logic circuits
基金项目:本文受国家自然科学基金资助
作者单位E-mail
尚奥 太原理工大学信息工程学院 太原030024  
裴晓鹏 太原理工大学信息工程学院 太原030024  
吕迎春 太原理工大学信息工程学院 太原030024  
陈泽华 太原理工大学信息工程学院 太原030024 zehuachen@163.com 
摘要点击次数: 573
全文下载次数: 349
中文摘要:
      完全确定时序逻辑电路状态化简是指找到并合并逻辑电路中的等价状态,进而简化电路,提高电路安全性,节约硬件电路成本。电路状态化简的关键是依据等价关系找到电路中的最大状态等价类集合。针对此类问题,提出了一种基于等价关系构建状态转移系统矩阵进行状态化简的算法,并将粒计算理论中的分层粒化思想用于最大等价类集合的求取过程中。在定义输出矩阵和次态矩阵的基础上,根据输出矩阵对原始状态进行初级等价类的划分与标记,可以得到初态标记矩阵和次态标记矩阵,然后构建状态转移系统矩阵。利用等价关系将状态转移系统矩阵中相同的列进行合并,则完成一次对原始状态最大等价类的划分。根据迭代原则,等价类粒子由粗到细,直到分类不再改变时便得到最终的最大状态等价类集合。最后进行状态合并,得到最小化状态表。算法分析表明,该算法简单、准确、有效。
英文摘要:
      State reduction of the completely specified sequential logic circuit refers to find and combine the equivalent states in the logic circuit.The reduction can simplify the circuit,improve its safety and decrease its hardware cost at the same time.The key point for state reduction is to find the maximal state equivalence classes.In this paper,an equivalence relation based algorithm was proposed by introducing granular computing method.By defining output matrix,sub-state matrix,and marking the initial states in the matrices,the initial state mark matrix and the sub-state mark matrix were obtained.Then,state transition system matrix was constructed,and the the initial states in the state table was continuously partitioned from coarser granularity to finer granularity until the maximal state equivalence classes were obtained.The experimental results and complexity analysis show the accuracy and efficiency of the proposed algorithm.
查看全文  查看/发表评论  下载PDF阅读器