数字设计中基于图的状态等价类集生成算法

A GENERATION ALGORITHM FOR THE SET OF EQUIVALENCE CLASSES BASED ON GRAPH IN DIGITAL DESIGN

在完全确定状态的时序电路、状态机等数字系统设计中,确定全部状态等价类,是进行最优状态化简的前提。结合图论理论提出一种等价类集生成算法,首先建立等价类与图中连通分支的联系,然后给出了通过化简图的邻接矩阵而得到等价类集的方法。算法易于编程实现,适合那些状态完全确定的包含几十、上百甚至更多初始状态的大规模数字系统设计。

In digital design, such as sequential circuit and state machine with the completely specified states, it is the prerequisite that each equivalence class should be ascertained for optimizing the state reduction. Applying graph theory, a generation algorithm for equivalence classes set is presented. Firstly, the relation between the equivalence classes and the connective branches in a graph is founded, and then by reducing the adjacent matrix of the graph, the approach to ascertain the equivalence classes is elaborated. The algorithm is easy to be programmed, and is suitable for large scale digital design with completely specified states that may include dozens, hundreds and even more initial states.