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

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

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

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.