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.
이 논문에서는 순서논리회로 (sequential circuit)의 설계를 위하여 내부상태 (internal state)에 코드 (code)를 부여하는 방법을 제시했다.
구체적으로 상태천이표 (State diagram)로부터 가능한 쌍 (pair) 의 연관계수 (adjacency weight)를 구해서 이들 연관성 (adjacency)를 최대로 만족시킬 수 있는 방법을 제시했다.
이 방법에서는 그래프 이론 (graph theory)이 사용되었으며 실현 (implementation)을 위하여 프로그램에서는 순서논리회로 (sequential machine)의 상태 (state) 수에 따라 데이타 구조를 바꿀 수 있는 ALGOL을 사용했다.
실험 결과에 의하면 여기서 제안한 방법을 이용하면 내부상태 (internal state)에 코드를 임의로 부여 (random assignment) 한 것보다 경제적으로 이익이 있음을 알 수 있다.