New Construction of Complementary Sequence (or Array) Sets and Complete Complementary Codes (I)

Zilong Wang, Dongxu Ma, Guang Gong

TL;DR

This paper introduces a novel, general method for constructing complementary sequence (or array) sets (CSSs) and complete complementary codes (CCCs) for various alphabet sizes ($q$) and lengths. The new constructions are shown to generate a larger number of sequences and offer explicit functional forms, potentially leading to improved performance in applications like OFDM.

What Problem Does This Paper Address?

Orthogonal Frequency Division Multiplexing (OFDM) is a popular communication technique, but it suffers from a high Peak-to-Mean Envelope Power Ratio (PMEPR). Golay sequences and their generalizations (CSSs and CCCs) have been proposed as codewords to mitigate this issue, offering a PMEPR of at most 2. However, existing construction methods for these sequences often lack explicit functional forms, are limited in their applicability (e.g., to binary sequences), or do not generate a sufficiently diverse set of sequences. This paper aims to provide a unified and general framework for constructing CSSs and CCCs with explicit functional forms, expanding their utility and potentially improving PMEPR control.

Methods

The authors propose a new construction method based on multivariate polynomial matrices that satisfy both "polyphase" and "para-unitary" conditions. These matrices are built using delay matrices and Butson-type Hadamard matrices. The core of the method involves constructing these multivariate polynomial matrices and then deriving the explicit functional forms of the sequences from them. The paper also introduces a systematic approach to compute these functions, leveraging concepts from group rings and module theory, and utilizing basis functions and representatives of equivalence classes of phase matrices.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Unified Construction: The paper presents a single, general framework that can produce various types of complementary sequences and arrays, including Golay sequences, ternary sequences, and binary/quaternary sequences of size 4.
  • Explicit Functional Forms: A significant contribution is the derivation of explicit Boolean function forms for the constructed sequences, which were previously lacking for many construction methods.
  • Larger Code Space: The new constructions generate sequences that fill a larger number of cosets of a linear code compared to existing methods, suggesting potential for better PMEPR control and higher code rates.
  • Novelty in Quaternary Sequences: For quaternary sequences of size 4, the paper highlights that many of the constructed sequences cannot be generalized from binary sequences, indicating a departure from previous approaches and the discovery of new sequence families.
  • Connection to Hadamard Matrices: The method leverages Butson-type Hadamard matrices, providing a structured way to generate diverse sets of sequences.

Key Results

  • Golay Sequences: For $N=2$ and even $q$, the construction precisely matches standard Golay sequences and arrays.
  • Ternary Sequences: New ternary complementary sequences of size 3 are reported for the first time.
  • Binary/Quaternary Size 4: Explicit Boolean function forms are obtained for binary and quaternary complementary sequences of size 4. These sequences are largely new and form a significant number of cosets of a linear code.
  • Generalization: The framework is shown to generalize CSSs to Complementary Array Sets (CASs) and CCCs to Complete Complementary Arrays (CCAs).

Limitations and Future Work

The authors acknowledge that their construction for binary and quaternary sequences of size 4 results in sequences of length $4m$, whereas some existing methods can achieve lengths of $2^m$. A key future direction is to investigate whether their method can be extended to construct CSSs of size $2^n$ with length $2^m$ for arbitrary $n$ and $m$. They also pose questions about the role of permutations in their construction versus existing methods and whether their approach can encompass all complementary sequences proposed in prior work, which would be crucial for exploring PMEPR control with higher code rates. The paper also suggests that further work will explore constructing larger sets of Boolean functions and sequences using block matrices.

Summary updated

Abstract

A new method to construct $q$-ary complementary sequence (or array) sets (CSSs) and complete complementary codes (CCCs) of size $N$ is introduced in this paper. An algorithm on how to compute the explicit form of the functions in constructed CSS and CCC is also given. A general form of these functions only depends on a basis of functions from $\Z_N$ to $\Z_q$ and representatives in the equivalent class of Butson-type Hadamard matrices. Surprisingly, all the functions fill up a larger number of cosets of a linear code, compared with the existing constructions. From our general construction, its realization of $q$-ary Golay pairs exactly coincides with the standard Golay sequences. The realization of ternary complementary sequences of size $3$ is first reported here. For binary and quaternary complementary sequences of size 4, a general Boolean function form of these sequences is obtained. Most of these sequences are also new. Moreover, most of quaternary sequences cannot be generalized from binary sequences, which is different from known constructions. More importantly, both binary and quaternary sequences of size 4 constitute a large number of cosets of the linear code respectively.
BibTeX
@article{wang2021new,
  author = {Zilong Wang and Dongxu Ma and Guang Gong},
  title = {{New Construction of Complementary Sequence (or Array) Sets and Complete Complementary Codes (I)}},
  journal = {IEEE Trans. Information Theory},
  year = {2021},
  url = {https://openreview.net/forum?id=lbXaUqQuYH},
}
Figure