Abstract :
Abstract—This paper considers the problem of determining whether a sequential machine, given by its flow table, can be realized in the form of a single binary shift register. One-to-one and many-to-one assignments are considered. Binary partitions are introduced, and shift registers are characterized in terms of binary partitions. An algorithm is given for the determination of the required partitions for a shift-register assignment. Binary set systems are introduced and shift registers are characterized in terms of binary set systems. It is proven that there exists a sequential machine that cannot be realized by a single binary shift register of finite length. Methods for determining the set systems necessary for a single shift-register assignment are given. For machines where every state has two distinct next states, a method is presented whereby a number of machines can be easily eliminated as being not fsr realizable. It is then shown how this can be extended to all machines.
Keywords :
Index terms—Binary partitions, binary set systems, feedback shift registers, internal state assignment, single binary fsr´s, state splitting, synchronous sequential machines.; Algebra; Binary codes; Circuit synthesis; Hardware; Partitioning algorithms; Shift registers; State feedback; Switching circuits; Index terms—Binary partitions, binary set systems, feedback shift registers, internal state assignment, single binary fsr´s, state splitting, synchronous sequential machines.;
