DECOMPOSITION AND STATE ASSIGNMENT FOR SEQUENTIAL MACHINES
Zvi Kohavi · Defense Technical Information Center (DTIC) · 1964
A system of sequential machines can be significantly reduced if we find a method of factoring some small machines connected in cascade to other machines and producing the desired response. Necessary and sufficient conditions are developed for two (or more) machines to be cascade decomposable in such a way that both have one common component machine that may be factored and shared by the two machines. To obtain the common machine the concept of implication table is introduced. The implication table is shown to be the state table of the factored machine. It is further shown how machines that do not obey these conditions can be augmented in such a way that the conditions are satisfied and the factoring is possible. The problem of reducing the output circuit is also considered. The main tools in this point are the output consistant partitions and the partitions with substitution property or the partition pairs. The importance of a simplified output circuit is increased in the treatment of multiple-outputs, Mealy-type machines. As a more advanced step, a new concept of partially independent subsets is studied. For machines that do not have any partition with substitution property or partition pairs it is shown how to obtain simpler assignments and output circuits with reduced dependencies by recognizing the partially independent subsets. (Author)