Some new balanced and almost balanced quaternary sequences with low autocorrelation

Jerod Michel, Qi Wang

TL;DR

This paper introduces new methods for constructing quaternary sequences with desirable "low autocorrelation" properties, crucial for efficient communication and cryptography. The authors also analyze the "linear complexity" of existing sequences, providing a deeper understanding of their suitability for these applications.

What Problem Does This Paper Address?

In fields like digital communications, cryptography, and signal processing, sequences with specific properties are highly sought after. Two key properties are:

  1. Low Autocorrelation: This refers to how well a sequence "matches itself" when shifted. Low autocorrelation means the sequence doesn't strongly resemble itself at different shifts, which is vital for avoiding interference and enabling efficient synchronization.
  2. Balancedness/Almost Balancedness: A balanced sequence has an equal (or nearly equal) distribution of its possible values. This is important for ensuring consistent signal power and preventing bias.
  3. Linear Complexity: This measures how complex a sequence is to generate using a linear feedback shift register (LFSR). Higher linear complexity generally means a sequence is harder to predict and thus more secure in cryptographic applications.

While much research has focused on binary sequences (sequences of 0s and 1s), quaternary sequences (sequences of 0, 1, 2, and 3) offer greater information density. However, constructing quaternary sequences with good autocorrelation and high linear complexity, especially for odd periods, has been a significant challenge. This paper aims to address this gap by proposing new construction methods and analyzing the properties of existing sequences.

Methods

The paper employs several key techniques:

  • Cyclotomic Classes: The authors leverage "cyclotomic classes of order eight" to construct new families of balanced quaternary sequences with odd periods. These classes are derived from number theory concepts related to finite fields.
  • Gray Mapping: This is a standard technique used to convert pairs of binary sequences into quaternary sequences. The paper utilizes this mapping to build new quaternary sequences from existing binary ones.
  • Autocorrelation Analysis: The paper rigorously analyzes the autocorrelation properties of the constructed sequences using mathematical formulas and definitions.
  • Linear Complexity Investigation: The authors investigate the linear complexity of sequences over finite fields, specifically $F_{2^2}$, using established theorems and definitions related to minimal polynomials of sequences.
  • Modification of Existing Constructions: The paper revisits and slightly modifies constructions proposed by Chung et al. and Shen et al. to simplify them and generate new families of sequences with desirable properties.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and analysis of sequences, not on empirical evaluation using specific datasets.

Key Insights and Ideas

  • New Families of Odd-Period Sequences: The paper successfully constructs novel families of balanced quaternary sequences with odd periods and low autocorrelation using cyclotomic classes. This expands the toolkit for designing such sequences.
  • Simplification of Existing Methods: A key contribution is the identification of a slight modification to an existing construction (Chung et al.) that not only yields new sequences but also simplifies a related construction (Shen et al.). This demonstrates how theoretical insights can lead to more practical methods.
  • Understanding Linear Complexity: The paper provides valuable insights into the linear complexity of various quaternary sequences, particularly those with odd periods. This is crucial for assessing their cryptographic strength.
  • Connection Between Binary and Quaternary Sequences: The use of Gray mapping highlights the strong connection between binary and quaternary sequences, showing how properties of binary sequences can be leveraged to construct quaternary ones.

Key Results

  • Construction of New Balanced Quaternary Sequences: The paper presents a new construction for balanced quaternary sequences of odd prime period with low autocorrelation using cyclotomic classes of order eight.
  • Analysis of Existing Sequences: The linear complexity of several known quaternary sequences of odd period is investigated.
  • Generalization of Existing Constructions: A modification of Chung et al.'s construction is shown to simplify Shen et al.'s construction in certain cases, leading to new families of balanced and almost balanced quaternary sequences of even period with low autocorrelation.
  • Numerical Verification: Remark 3.1 notes that the linear complexity of sequences from Theorem 3.1 has been checked numerically for several primes, showing specific values for $L(u)$ for different primes $p$. For example, for $p=17$, $L(u)=8$, and for $p=641$, $L(u)=320$.

Limitations and Future Work

  • Theoretical Focus: While the paper presents new constructions and theoretical analyses, it acknowledges that the linear complexity of sequences from Theorem 3.1 has only been examined theoretically and numerically. Further theoretical investigation into these complexities is suggested.
  • Specific Prime Conditions: The constructions often rely on specific properties of prime numbers (e.g., $p \equiv 1 \pmod{16}$, $p \equiv 1 \pmod{8}$). Future work could explore constructions that are less dependent on these specific conditions.
  • Exploration of Other Orders: The paper focuses on cyclotomic classes of order eight and four. Exploring other orders might lead to different families of sequences with unique properties.
  • Practical Applications: While the paper discusses applications in communications and cryptography, further research could explore the direct implementation and performance evaluation of these sequences in real-world systems.

Summary updated

Abstract

Quaternary sequences of both even and odd period having low autocorrelation are studied. We construct new families of balanced quaternary sequences of odd period and low autocorrelation using cyclotomic classes of order eight, as well as investigate the linear complexity of some known quaternary sequences of odd period. We discuss a construction given by Chung et al. in “New Quaternary Sequences with Even Period and Three-Valued Autocorrelation” (IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E93-A(1), 309–315 2010) first by pointing out a slight modification and then by showing that, in certain cases, this slight modification generalizes the construction given by Shen et al. in “New Families of Balanced Quaternary Sequences of Even Period with Three-level Optimal Autocorrelation” (IEEE Commun. Lett. 2017(10), 2146–2149 2017). We investigate the linear complexity of these sequences as well.
BibTeX
@inproceedings{michel2019some,
  author = {Jerod Michel and Qi Wang},
  title = {{Some new balanced and almost balanced quaternary sequences with low autocorrelation}},
  booktitle = {Cryptogr. Commun},
  year = {2019},
  url = {https://openreview.net/forum?id=FtBXgJMlOy},
}
Figure