Theoretical exploration of pattern attributes for maximum-length shift-register sequences
Journal
2009 ACM International Wireless Communications and Mobile Computing Conference
Pages
1116-1120
ISBN
9781605585697
Date Issued
2009
Author(s)
Abstract
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. Copyright ? 2009 ACM.
Subjects
Berlekamp's algorithm
Finite fields
M-sequences
Pattern attribute
Ttraveling salesman problem
SDGs
Type
conference paper