A Programmed Algorithm for Assigning Internal Codes to Sequential Machines

Abstract

A relatively fast procedure for assigning codes to the internal states of a sequential machine is described, which leads to a reasonably economical logical realization of the machine in many cases. The method is applicable to both completely and incompletely specified state tables, and permits the use of redundant internal variables if desired. An algorithm which implements the method approximately, and which is nonenumerative, has been programmed for the 7090 computer. The program handles problems with up to 100 internal states and 30 input symbols, or 3000 total states. It has performed a problem of maximum size in 120 seconds. Although fast, the method sometimes fails to attain truly economical logic in cases where unusually simple realizations are known to exist (e.g., the shift register). More comprehensive methods are now known, which in principle can produce better results, but which will be far more tedious to execute. They will be reported separately.