Identification and Synthesis of Linear Sequential Machines

This paper develops a method for identifying and synthesizing linear sequential machines using their state transition table representation. The basic objective is to construct a procedure which can be efficiently implemented by a digital computer. Towards that end, we develop simple and easily used preliminary tests which reject nonlinear systems to precede the time consuming synthesis, or state coding, process. The method for the coding of states is completely analytic, with the result that trial and error processes are not required. Consider the symbolic state transition table, Table I. The input vectors, u, have m components (2 ^ M ^ 2"'),* and the next state vectors, six, and present state vectors, s, , have n unspecified components (N ^ 2"). The vector components are defined over a modular field, and here this field is taken as GF(2). Most of the results obtained below can be easily extended to other prime fields. In terms of the state transition table, a linear sequential machine * This paper considers tables which have at least two distinct columns of next states (nonautonomous systems). 343