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

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.

 [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