Accession Number : AD0646593

Title :   ON SHIFT-REGISTER REALIZATIONS OF SEQUENTIAL MACHINES,

Corporate Author : NORTHWESTERN UNIV EVANSTON ILL INFORMATION-PROCESSING AND CONTROL SYSTEMS LAB

Personal Author(s) : Su,Chau Chang

Report Date : JAN 1967

Pagination or Media Count : 61

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)

Descriptors :   (*AUTOMATA, *SHIFT REGISTERS), ALGORITHMS, SYNTHESIS, GRAPHICS, COMPUTER LOGIC, MEMORY DEVICES, DIGITAL COMPUTERS, COMPUTER PROGRAMMING, COMBINATORIAL ANALYSIS

Subject Categories : Computer Programming and Software
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE