QUASI-LINEAR SEQUENTIAL MACHINES.
Abstract
A class of sequential circuits, in which the next state and output functions are linear functions of the present state and non-linear functions of the inputs, is analyzed. The problem of deciding if an arbitrary sequential machine belongs to this class, is solved using cyclic and transient binary partitions generated by the output variables. Special cases of this class, such as the linear machines, and machines which perform multiplication and division in finite fields are considered as quasi-linear machines with a special coding of the input combinations. This class of machines is shown to possess very short diagnosing sequences of length at most n, for a q state machine. A procedure is presented whereby any sequential machine is simulated by a quasi-linear machine using a minimum number of extra delay elements over and above that needed for non quasi-linear realization. Finally a computational algorithm is developed for the detection of a quasi-linear next-state assignment for a machine with a non-quasi-linear output function. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1966
- Accession Number
- AD0632602
Entities
People
- Pierre Lavallee
Organizations
- New York University Tandon School of Engineering