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

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

作　　者：孙志卓[1] 徐凤生[1] 任传成[1] 唐忠莉[1] 

机构地区：[1]德州学院计算机系,山东德州253000

出　　处：《计算机应用与软件》2009年第5期247-248,257,共3页Computer Applications and Software

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

关 键 词：等价类 状态化简 连通分支 邻接矩阵 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术] TP31[自动化与计算机技术—计算机科学与技术]