Minimum-State Sequential Circuits for a Restricted Class of Incompletely Specified Flow Tables

One of the classical problems of sequential circuit theory is that of obtaining a minimum-state sequential circuit satisfying the requirements of a given flow table. When the flow table is incompletely specified, the procedures for obtaining the minimum-state sequential circuit are lengthy and require such extensive enumeration that they are impractical for computer implementation. This paper discusses a restricted type of incompletely specified flow table for which more efficient procedures can be devised. In particular, relay-type flow tables in which the unspecified entries all are present because of a restriction of the manner in which the inputs can change are considered. It is shown that for this type of flow table only the maximal compatibles or compatibility classes need be considered in forming a minimum-state circuit.