A Method for Synthesizing Sequential Circuits
📜 Abstract
The theoretical basis of sequential circuit synthesis is developed, with particular reference to the work of D. A. Huffman and E. F. Moore. A new method of synthesis is developed which emphasizes formal procedures rather than the more familiar intuitive ones. Familiarity is assumed with the use of switching algebra in the synthesis of combinational circuits.
✨ Summary
The paper develops a formal method for synthesizing sequential switching circuits. It introduces an abstract model in which a circuit’s next state and output are uniquely determined by its present state and input. State diagrams and truth tables are used to represent circuit behavior, while reduction procedures identify equivalent states and eliminate redundancy. The method combines ideas associated with Moore’s sequential-machine theory and Huffman’s flow-table merging, and extends the synthesis process to both synchronous and asynchronous circuits. For asynchronous designs, the paper also addresses state coding and the avoidance of harmful race conditions. The proposed workflow proceeds from circuit requirements to a state representation, reduction, state assignment, circuit equations, and realization of the resulting combinational networks. The paper explicitly notes limitations involving large truth tables, designer-dependent initial specifications, and the absence of optimal state-coding rules.
The work became foundational for the theory and practice of finite-state machines. The transition-based output model described in the paper is now commonly referred to as a Mealy machine, and remains a standard abstraction in digital-logic design and automata theory. (xlinux.nist.gov) Later literature continues to use Mealy machines for hardware synthesis, formal verification, circuit semantics, and extensions such as quantum state machines. (georgejkaye.com)