Linearity of Sequential Machines

A sequential machine is defined to be linear if its next-state function and output function are linear transformations from their domains (vector spaces) to their ranges (also vector spaces). It is shown that this definition is equivalent to those given by other authors. Based on this definition, a set of necessary and sufficient conditions for the flow table of a sequential machine to be linear is obtained. Many properties of the flow table of a linear sequential machine are found, and in many cases they form very simple tests for the linearity of a flow table. A general procedure for testing the linearity of a flow table is established. This procedure, including the coding of the states, inputs, and outputs, either ends with a linear realization of the flow table with the minimum possible numbers of state variables, input variables, and output variables, or detects that such a linear realization for the flow table is impossible. The type of sequential machine considered in this paper is deterministic and synchronous, and both Moore model and Mealy model are studied in detail. The linearity of incompletely specified sequential machines is also discussed.