On the Efficient Assignment of Internal Codes to Sequential Machines

Abstract

A set of procedures for assigning codes to internal states of a synchronous sequential machine so as to minimize the internal logic in two-level form is proposed. The procedures are based on interpreting the state table of a sequential machine as a set of mappings from present states into next states, under control of the inputs. Attention is focused on a particular subset of these mappings, called pr mappings. A numerical score is assigned to each pr mapping, which is a measure of the desirability of ``selecting'' the mapping for inclusion in a ``basic set'' of mappings. A basic set has the property of determining a unique code assignment (within a symmetry of the cube of internal states). The procedures are applied to a 3-stage shift register and result in the optimum encoding for that device. Finally, it is briefly indicated how three previous assignment methods, including one developed by the author, are related to those described here. Algorithms are presented for some but not all of the proposed procedures. These algorithms must be completed before the proposals can be implemented by a computer program.