The linear complexity of a sequence $s$ is one of the measures of its predictability. It represents the smallest degree of a linear recursion which the sequence satisfies. There are several algorithms to find the linear complexity of a periodic sequence $s$ of length $N$ (where $N$ is of some given form) over a finite field $\F_q$ in $O(N)$ symbol field operations. The first such algorithm is The Games-Chan Algorithm which considers binary sequences of period~$2^n$, and is known for its extreme simplicity. We generalize this algorithm and apply it efficiently for several families of binary sequences. Our algorithm is very simple, it requires~$\beta N$ bit operations for a small constant $\beta$, where $N$ is the period of the sequence. We make an analysis on the number of bit operations required by the algorithm and compare it with previous algorithms. In the process, the algorithm also finds the recursion for the shortest linear feedback shift-register which generates the sequence. Some other interesting properties related to shift-register sequences, which might not be too surprising but generally unnoted, are also consequences of our exposition.
We study the duplication with transposition distance between strings of length $n$ over a $q$-ary alphabet and their roots. In other words, we investigate the number of duplication operations of the form $x = (abcd) \to y = (abcbd)$, where $x$ and $y$ are strings and $a$, $b$, $c$ and $d$ are their substrings, needed to get a $q$-ary string of length $n$ starting from the set of strings without duplications. For exact duplication, we prove that the maximal distance between a string of length at most $n$ and its root has the asymptotic order $n/\log n$. For approximate duplication, where a $\beta$-fraction of symbols may be duplicated incorrectly, we show that the maximal distance has a sharp transition from the order $n/\log n$ to $\log n$ at $\beta=(q-1)/q$. The motivation for this problem comes from genomics, where such duplications represent a special kind of mutation and the distance between a given biological sequence and its root is the smallest number of transposition mutations required to generate the sequence.
In this paper, we analyze the weight class distribution of de Bruijn sequences. The main tool we use is the generating function theory, proposed recently by Coppersmith et al. By analyzing the weights of cycles generated by the pure circulating register, we give explicit formulas for the numbers of de Bruijn sequences in the extremal weight classes. Moreover, we use these formulas to prove some conjectures proposed by Fredricksen and Mayhew, which seems have been opened for a long time. In addition to these theoretical results, some experimental results are also provided.
Via interleaving Ding-Helleseth-Lam sequences, a class of binary sequences with optimal autocorrelation magnitude was constructed (Des. Codes and Cryptogr., 2018). Later, Sun et al. determined the upper and lower bounds of the 2-adic complexity of such sequences (SETA, 2018). In this paper, we determine the exact value of the 2-adic complexity of this class of sequences. The results show that the 2-adic complexity of this class of binary sequences is close to the maximum.
Families of periodic sequences with some desirable auto-correlation and cross-correlation properties have applications in communications and radar systems for identification, synchronization, ranging, or interference mitigation. A sequence is said to be a polyphase sequence if all the coordinates are n-th roots of unity. In this paper, we develop a connection between generalised Frank sequences and well-studied combinatorial objects: circular Florentine arrays. From this connection, we can derive an optimal set of perfect polyphase sequences with respect to the Sarvate bound. Furthermore, the size of the optimal set is determined by the existence of circular Florentine arrays. As a result, the size of an optimal set of perfect sequences is improved, compared with the previous results, where the size depends on the smallest prime divisor of the period.
Spatial modulation (SM) is a new multiple-input multiple-output (MIMO) paradigm in which only one transmit antenna is activated over every symbol duration. So far, efficient SM training sequences (different from the existing design for conventional MIMO systems) remain largely open. Motivated by this research problem, we introduce a novel class of sequence pairs, called “cross Z-complementary pairs (CZCPs)", each displaying zero-correlation zone (ZCZ) properties for both their aperiodic autocorrelation sums and crosscorrelation sums. A CZCP may be transmitted in two non-orthogonal SM channels and hence proper design should be conducted to minimize the cross-interference of the two constituent sequences. We construct perfect CZCPs based on selected Golay complementary pairs. We show that the training sequences derived from our proposed CZCPs lead to optimal channel estimation performance over frequency-selective SM channels.
The two-dimensional (2-D) Golay complementary array pair (GCAP) is an extension of one-dimensional 1-D Golay complementary pair (GCP). The sum of 2-D autocorrelations of constituent arrays are zero except for the 2-D zero shift. In this paper, the 2-D generalized Boolean function is introduced and a novel construction of 2-D GCAPs is proposed based on generalized Boolean functions. Moreover, we provide a construction of 2-D Golay complementary array mate from Boolean functions as well. One potential application of 2-D GCAPs is 2-D synchronization.