Universal Multicode STT State Assignments for Asynchronous Sequential Machines

A universal single transition time (STT) state assignment is a way to give a valid STT state assignment in which all state variables that must change in a given transition are allowed to change simultaneously without critical races for any asynchronous sequential machine regardless of the configuration of its flow table. This paper presents a new systematic procedure for constructing universal STT state assignments and shows that the procedure can give better upper bounds on the number of state variables required for realizing asynchronous normal flow tables than any known universal STT state assignments, although there is some difference in standpoint between earlier works and the present one. It is further shown that the procedure can also be applied to improve the best known bounds for (2, 1) separating systems which are known to be less restricted universal assignments. The feature of the procedure lies in the idea that two binary code vectors are assigned to each internal state. In the resulting universal STT assignments, the number of state variables required is given by 2 · m1.59 where m = [log2 n], n being the number of states and [X] being the least integer ≥ X. Furthermore, the resulting (2, 1) separating systems require 2 ·m state variables.