Uniform Synthesis of Sequential Circuits

The realization of an arbitrary binary output synchronous sequential machine by a network of copies of a fixed sequential machine (module) or copies of a small number of machines is a problem which has received recent attention. 1 - 0 An equivalent problem has been studied in Ref. 6. A design of this sort is particularly suited to batch fabrication techniques, because it is possible to mass produce a fairly complex integrated circuit (the module) and then wire these circuits together to realize any desired sequential machine. The machines, so constructed, will be fast; the time between inputs need not be longer than the time it takes a single module to resolve its output after a change in input, no matter how many modules are in the network. The disadvantage of this technique, so far, has been the large number of copies of the module necessary to realize a machine; as many as 2 n -- 2 copies for an n state machine are required when using the modules of Refs. 1 and 2. These modules are shown in Fig. 1 for the binary input case. Not shown in any of our diagrams is provision for initializing the output of any module to the hot (1) state if desired. Neither is provision for control of the module by a clock shown in this or any other module. t Portions of this paper appeared in the Proceedings of the IEEE 9th Annual Symposium on Switching and Automata Theory, Schenectady, N. Y., October 1968. t Princeton University, Princeton, New Jersey. 1115