Properties of Linear Machines

Publisher Website
Google Scholar
Abstract
Certain properties are proved for machines whose state and output behavior are linear ever a finite field. In particular, conditions in terms of the defining matrices are given for definiteness; all linear machines are shown to have finite memory no greater than their dimensions; a simple test for diagnosibility is described, and the existence of diagnos- ing sequences much shorter than in the general case is proved; finally, information lossless- hess is discussed. I. Linear Machines A machine is said to be linear if its states can be identified with vectors and its state and output behavior described by a pair of matrix equations over a finite field .1 s(t + 1) = As(t) + Bx(t) (la) z(t) = Cs(t) + Dx(t). (lb) The vectors s(t), x(t) and z(t) denote the state, input and output, respectively, of the machine at time t. No restrictions are placed on the dimensions of the input or output vectors (numbers of inputs or outputs). A machine described by Eqs. la and lb will be called a linear machine (A, B, C, D); the dimension of the machine is the dimension of its state vector. The equations represent a Moore model or a Mealy model according to whether D is or is not identically zero. Conversion between Moore and Mealy models of linear machines will be discussed in a forthcoming paper by the author and S. Even. The final-state and input-output behavior of a linear machine under an experi- ment of length t may be described by iterating Eqs. la and lb.

This publication has 1 reference indexed in Scilit: