ON SHIFT-REGISTER REALIZATIONS OF SEQUENTIAL MACHINES,
Abstract
The problem of determining secondary state assignments for sequential machines such that the binary memory elements are connected in the form of shift registers is studied. Algorithm for finding such state assignments is developed. One or more code words may be assigned to a state of the sequential machines. The only restriction is that the realizations be unitary. A single shift-register realization of a sequential machine is unitary if and if all code words assigned to a state have the same first digit. In a multiple shift-register realization of a sequential machine, corresponding to each shift register, there exists a set system on the state set of the sequential machine. A multiple shift-register realization is unitary if each of the set system is a partition and if all code words assigned to a block of the partitions have the same first digit. With our technique, the unitary realizations consisting of the least number of shift registers can be found for any finite, deterministic, synchronous and reduced(minimal-state) sequential machine, each of whose states has a non-empty predecessor set. The algorithm is suitable for programming on digital computers. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1967
- Accession Number
- AD0646593
Entities
People
- Chau Chang Su
Organizations
- Northwestern University