计算机科学 ›› 2018, Vol. 45 ›› Issue (1): 118-121.doi: 10.11896/j.issn.1002-137X.2018.01.019

• CRSSC-CWI-CGrC-3WD 2017 • 上一篇    下一篇

基于等价关系的完全确定时序逻辑电路状态化简算法

尚奥,裴晓鹏,吕迎春,陈泽华   

  1. 太原理工大学信息工程学院 太原030024,太原理工大学信息工程学院 太原030024,太原理工大学信息工程学院 太原030024,太原理工大学信息工程学院 太原030024
  • 出版日期:2018-01-15 发布日期:2018-11-13
  • 基金资助:
    本文受国家自然科学基金资助

State Reduction Algorithm for Completely Specified Sequential Logic Circuit Based on Equivalence Relation

SHANG Ao, PEI Xiao-peng, LV Ying-chun and CHEN Ze-hua   

  • Online:2018-01-15 Published:2018-11-13

摘要: 完全确定时序逻辑电路状态化简是指找到并合并逻辑电路中的等价状态,进而简化电路,提高电路安全性,节约硬件电路成本。电路状态化简的关键是依据等价关系找到电路中的最大状态等价类集合。针对此类问题,提出了一种基于等价关系构建状态转移系统矩阵进行状态化简的算法,并将粒计算理论中的分层粒化思想用于最大等价类集合的求取过程中。在定义输出矩阵和次态矩阵的基础上,根据输出矩阵对原始状态进行初级等价类的划分与标记,可以得到初态标记矩阵和次态标记矩阵,然后构建状态转移系统矩阵。利用等价关系将状态转移系统矩阵中相同的列进行合并,则完成一次对原始状态最大等价类的划分。根据迭代原则,等价类粒子由粗到细,直到分类不再改变时便得到最终的最大状态等价类集合。最后进行状态合并,得到最小化状态表。算法分析表明,该算法简单、准确、有效。

关键词: 状态化简,等价关系,粒计算,时序逻辑电路

Abstract: 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.

Key words: State reduction,Equivalence relation,Granular computing,Sequential logic circuits

[1] 刘宝琴,罗嵘,王德生.数字电路与系统(第2版)[M].北京:清华大学出版社,2007.
[2] 刘培植.数字电路与逻辑设计[M].北京:北京邮电大学出版社,2009.
[3] ZHAO H,SUN F R.Discussion on State Reduction Method in Synchronous Sequential Circuit Design [J].Automation and Instrumentation,2010(5):120-122.(in Chinese) 赵贺,孙凤茹.同步时序电路设计中状态化简方法探讨[J].自动化与仪器仪表,2010(5):120-122.
[4] 边计年,薛宏熙,苏明,等.数字系统设计自动化(第2版)[M].北京:清华大学出版社,2005.
[5] CHANG Q M,YUE C Q.A Graph Theory Method for State Reduction of Digital Systems [C]∥Academic Annual Confe-rence on Electrician Theory.2006.(in Chinese) 常青美,岳彩青.一种数字系统状态化简的图论方法[C]∥电工理论学术年会.2006.
[6] ZHANG K Y,ZHANG Y,CHEN Z H.GrC-Based State Reduction Algorithm for Completely Specified Sequential Logic Circuit[J].Journal of Chinese Computer Systems,2016,37(8):1786-1789.(in Chinese) 张凯英,张裕,陈泽华.基于粒计算的完全确定时序逻辑电路状态化简算法[J].小型微型计算机系统,2016,37(8):1786-1789.
[7] 苗夺谦,王国胤,刘清,等.粒计算:过去,现在与展望[M].北京:科学出版社,2007.
[8] WANG W Z.A Parallel Algorithm for State Simplification[C]∥CAD/CG 1988.1988:831-838.(in Chinese) 王文章.状态化简的一个并行算法[C]∥ 全国计算机辅助设计与图形学学术会议.1988:831-838.
[9] LU Y P,LIN Y P,YANG G Z,et al.A State Minimization Algorithm for Completely Specified Sequential Machine[J].Journal of Hunan University,1997,24(1):97-102.(in Chinese) 陆应平,林亚平,杨贯中,等.完全定义时序机的状态化简算法[J].湖南大学学报1997,4(1):97-102.
[10] PAULL M C,UNGER S H.Minimizing the Number of States in Incompletely Specified Sequential Switching Functions[J].Ire Transactions on Electronic Computers,1959,EC-8(3):356-367.
[11] DAMIANI M.The state reduction of nondeterministic finite-state machines[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,1997,16(11):1278-1291.
[12] GRASSELLI A,LUCCIO F.A method for minimizing the number of internal states in incompletely specified machines .http://www.researchgate.net/publication/238705600_A_method_for_minimizing_the_number_of_internal_states_in_incompletely_specified_machines.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!