状态化简的一个并行算法

A PARALLEL ALGORITHM FOR STATE SIMPLIFICATION

本文在[1,2]的基础上,提出了“枝”迭代和“树”迭代公式。设M是任意原始状态机,由定理2可以写出对应的矩阵A_i和B_i,从而得到机器M的初始输出矩阵E(1)。由定理3可以求出M的第K级输出矩阵E(K),K=2,3,…r。定理4给出了状态Q_i与Q_i等价的充要条件,从而得到了求M的最简等价状态机M′的一个并行算法。由于本算法适合于向量运算,因此在计算机上实现时,程序设计十分简单。由[3,4,5]可知,“枝”迭代和“树”迭代公式不仅为时序电路的CAD,而且还为时序电路的状态识别和置初值等提出了一个新的数学方法。

The 'branch' iteration and 'tree' iteration formulae and a parallel algorithm for state simplification are presented. Because the algorithm is suitable for vector operation, the programming is rather simple. It is known that 'branch' iteration and 'tree' iteration formulae provide a new mathematical method not only for CAD in sequential circuits but also for state recognition and initials setting in sequential circuits.