The concatenation and partitioning of linear finite state machines

Abstract

Abstract The behaviour of linear finite state machines when partitioned into a number of smaller machines or concatenated into longer ones is discussed. Linear feedback shift registers (LFSRs) and linear cellular automata registers (LCARs) used in built-in self-test, cryptography and coding theory are examined, as is the concatenating and/or partitioning of machines which have a maximal length cycle structure to obtain longer or smaller ones maintaining this properly. It is shown that LCARs have better overall behaviour than LFSRs. Some minimum one-cell modifications which improve the number of concatenated or partitioned machines and maintain a maximal length cycle are introduced. The hardware cost is discussed.