New algebraic studies of pattern attributes in maximum-length shift-register sequences

摘要

In order to facilitate the ubiquitous heterogeneous and medium-independent communication net-works, transmitter identification is crucial especially as the number of transmitters becomes tremen-dous in reality. Since the birth of spread-spectrum communications, pseudo-random identification sequences have been widely adopted due to their preferable nearly Dirac-Delta auto-correlation property, which would lead to the advantages in synchronization and multi-user interference miti-gation. Maximum-length shift-register sequences (a.k.a. m-sequences) are pseudo-random sequences often adopted for multi-access communications, but categorization or grouping of the patterns (bit substrings) contained in m-sequences has not been investigated to the best of our knowledge. Thus, this paper is dedicated to the new study on the categorization of m-sequences, which would give rise to many applications involving assignment, addressing, and management of identification or spreading se-quences. We define new essential parameters, namely single-pattern-searching parameters, and design a new parallel algorithm to spot such inherent parameters associated with each selected underlying pattern. Our proposed new approach will facilitate a highly computationally-efficient solution to find the pattern-attributed (pattern-contained) m-sequences without actually generating any m-sequence for subsequence-matching between an m-sequence and the underlying pattern(s). We further utilize these single-pattern-searching parameters to establish the new analysis of pattern capacity and quality by characterizing multiple pattern attributes within m-sequences. The first goal of this work is to find single-pattern-attributed m-sequences recursively until the final subset of m-sequences is acquired so that each m-sequence contains all underlying patterns. The second goal of this work is to find the shortest sequences containing specified patterns. To achieve this goal, we first construct the shortest binary sequences subject to the underlying patterns and it can be accomplished by solving the generalized traveling salesman problem (GTSP). Then, according to the constructed shortest binary sequences, the number of pattern-contained m-sequences can be determined thereby. Memory-and computational-complexity analyses are also presented to demonstrate that our proposed new scheme is much more computationally efficient than the conventional subsequence-matching method for searching and counting the pattern-attributed m-sequences. On the other hand, our proposed new scheme leads to the same memory-complexity as the conventional method for registering the spotted pattern-attributed m-sequences. Finally, three new metrics for assessing the underlying patterns are proposed. They are attributability, discriminability, and ambiguity. The associated numerical evaluation is also provided in this paper. (C) 2021 Elsevier B.V. All rights reserved.