DECOMPOSITION AND STATE ASSIGNMENT FOR SEQUENTIAL MACHINES,
Abstract
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 19, 1964
- Accession Number
- AD0609253
Entities
People
- Zvi Kohavi
Organizations
- New York University Tandon School of Engineering