Decomposition of sequential machines

1 January 1965

proceedings article
Published by Institute of Electrical and Electronics Engineers (IEEE)

p. 52-61
https://doi.org/10.1109/focs.1965.6

Abstract

This paper examines the problem of finding cascade decompositions for two or. more reduced sequential machines which have the same input, such that a common submachine may be factored out and serve as a predecessor machine feeding two or more successor machines which generate the outputs of the specified given machines. Necessary and sufficient conditions under which it is possible to obtain decompositions which contain such a common submachine are developed. If the given machines do not satisfy these conditions, and a common submachine cannot be found, it is shown how one or both of the machines can be replaced by equivalent machines in such a way that some common submachine can be found. The basic tool in the determination of the common submachine is the implication table which is constructed from the implication graph. The objective of the cascade decomposition is to obtain, where possible, an economical realization in terms of internal memory elements without sacrificing economy in the complexity of the output logic circuitry.

Keywords

This publication has 4 references indexed in Scilit:

Secondary State Assignment for Sequential Machines
IEEE Transactions on Electronic Computers, 1964
Loop-free structure of sequential machines
Information and Control, 1962
The Cascade Decomposition of Sequential Machines
IEEE Transactions on Electronic Computers, 1961
A method for synthesizing sequential circuits
Bell System Technical Journal, 1955