The Tree Set of a Linear Machine

Linear sequential machines are finding an increasing number of uses in error correction, random number generation, and other digital applications. Autonomous behaviors of such machines with nonsingular characteristic matrix have been widely studied. Their state graphs consist of a set of cycles, which is most conveniently described by a cycle set. Analysis and synthesis of such machines have been completely established in terms of cycle sets. The purpose of this paper is to extend the result to the linear machines with singular matrices. The stage graphs of such machines consist of a set of cycles and a tree. The latter part can analogously be described by a tree set. The product and quotient of two tree sets are defined, and it is shown that a tree is realizable by a linear machine if and only if its tree set is a product of canonical tree sets.