Theoretical exploration of pattern attributes for maximum-length shift-register sequences

摘要

The maximum-length shift-register sequences (m-sequences) are the often-used pseudo-random sequences for multi-access communications. It is well known that the generation of the m-sequences relies on the initial seed and the cyclic shift. Although we can identify a particular m-sequence using a unique initial seed and the step of the cyclic shift, the categorization or the classification of the m-sequence structures has never been studied to the best of our knowledge. In this paper, we study the m-sequence structures by means of the attributes (common subsequences or patterns). Such patterns are a set of binary sequences with finite length occurring in the full-length m-sequences and they can be used to denote the special attributes (common features) for transceivers. In addition, we design a parallel method to compute all the possible positions of bits '0' and '1' for each underlying pattern using the Berlekamp's algorithm and then we employ the solution to a generalized traveling salesman problem for constructing the shortest binary sequences, each of which contains all underlying patterns. From these shortest binary sequences, we can thus evaluate the number of m-sequences that include the underlying patterns. We also define the attributability, and discriminability for the population analysis of the jointly- or exclusively-attributed m-sequences.