(A) study on state assignment in sequential machine design

Abstract

A set of procedures for assigning codes to the internal states of synchronous sequential machines so as to minimize the internal logic in two level form is proposed. The fundamental idea in this study is to maximize the adjacencies between the states so that the realization can be economical. This idea was implemented and its effectiveness is measured in terms of the number of AND gates required to realize with flip flops and AND-OR 2-level logic. For test purpose, for some sequential machines, relative comparisions are made with the results of the proposed procedure to the randomly assigned codes, to the other state assignment method and in some cases, to the greatest lower bound. The experimental results show that the proposed procedure usually performs better than the random assignments and the finding suboptimal embedding of the adjacency graph. Because it is implemented in ALGOL, especially with the dynamic data structure, the size of problems which can be handled is not limited. A version of implementation is limited to both completely specified and the single output machines.