On the Linearity of Sequential Machines

Abstract-This paper presents a method for determining, from ments in which the correspondence between states and n the flow table of a sequential machine, whether the machine is tuples of secondary variables is one-to-one. linearly realizable using the minimum number of unit delay elements. With regard to the input, two cases are considered: In The method is an extension of a previously presented method for autonomous machines. A linearity algorithm is presented for each the first case, the input r tuple for each input is given. In of two cases: 1) where the output is given and is to be linear, and the second case, the inputs are not specified, except that 2) where the output is either not given or may be nonlinear. The p different inputs are required; hence, an assignment of method is simple, straightforward, and, in general, provides a ready r = [log2 p] input variables will have to be made. In the solution to the linearity problem. following development, no distinction between the two INTRODUCTION cases is necessary; however, both are illustrated for th