A theory on sequence spaces and shift register generators

As a unified approach to the description of various shift register generators, the concept of sequence space is introduced and its properties are examined. A sequence space refers to a vector space whose elements are sequences satisfying the relation specified by a characteristic polynomial. In support of the sequence space, two bases-the elementary basis and the primary basis-are defined, and the polynomial expression of the sequence is defined as a tool for mathematical manipulations within the sequence space. Based on these definitions, various properties of sequence spaces such as sequence subspaces and minimal sequence spaces are investigated and summarized in terms of properties and theorems. The developed sequence theory is then applied to the description of the behaviors of shift register generators (SRGs). An SRG is represented by the state transition matrix, and the relevant SRG sequences are uniquely determined by this state transition matrix and the initial state vector. For an SRG, it is shown how to identify the sequence space generated by the SRG sequences with a fixed initial state vector (or the SRG space), and further, how to find the largest-dimensional sequence space that can be obtained by varying the initial state vectors (or the SRG maximal space). Conversely, for a given sequence space, it is shown how to find the minimum-sized SRGs that can generate the sequence space (or the basic SRGs). Finally, it is shown that the two typical SRGs-simple SRG and modular SRG-are special cases of basic SRGs that can generate the primary and the elementary bases, respectively