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

Zilong Wang, Dongxu Ma, Erzhong Xue, Guang Gong, Srdjan Budisin

TL;DR

This paper introduces a novel framework for constructing complementary sequence and array sets (CSSs and CSAs) and their complete counterparts (CCCs and CCAs) by extending existing para-unitary (PU) matrix-based methods. The key innovations are a new class of delay matrices and a block matrix construction for PU matrices, enabling the generation of a significantly larger and more diverse set of these sequences and arrays, including previously known constructions as special cases.

What Problem Does This Paper Address?

The paper tackles the challenge of constructing and enumerating complementary sequence sets (CSSs) and complete complementary codes (CCCs), which are crucial for applications like low Peak-to-Mean Envelope Power Ratio (PMEPR) in OFDM systems and efficient error control. While existing methods, particularly those based on para-unitary (PU) matrices, have shown promise, they have limitations. Specifically, previous PU-based constructions were restricted in the size and type of arrays they could generate, and they didn't encompass all known CSS and CCC constructions, leaving open questions about the full potential of PU matrices in this domain. The authors aim to address these limitations by proposing a more general and powerful framework.

Methods

The core of the paper's contribution lies in two main methodological advancements:

  • New Delay Matrices: The authors introduce a new class of "delay matrices" that are the array version of existing delay matrices. This innovation allows for the representation of generalized Boolean functions (GBFs) derived from PU matrices in an array format of size $2 \times 2 \times \cdots \times 2$. This is a significant step towards generating sequences and arrays with specific properties.
  • Block Matrix PU Construction: A new method for constructing PU matrices using block matrices is presented. This approach, combined with the new delay matrices, allows for the creation of a much larger number of new CSAs, CCAs, CSSs, and CCCs. The GBFs for these newly constructed sequences and arrays can be determined recursively.

The paper also demonstrates that existing constructions of CSSs (by Paterson and Schmidt) and CCCs (based on Reed-Muller codes) are special cases within their proposed framework.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and does not involve empirical evaluation on datasets.

Key Insights and Ideas

  • Unifying Framework: The paper provides a more comprehensive framework that unifies existing constructions of CSSs and CCCs, demonstrating that many prior methods are special instances of their generalized PU matrix approach.
  • Enabling Smaller Array Representations: The introduction of new delay matrices allows GBFs, previously represented by larger arrays, to be represented by smaller $2 \times 2 \times \cdots \times 2$ arrays. This is crucial for generating sequences that can be more efficiently utilized in systems like OFDM.
  • Recursive Construction of Complex Structures: The block matrix approach for PU matrices enables a recursive construction of complex sequences and arrays, leading to a significantly larger set of potential candidates for applications.
  • Explaining Open Questions: The framework offers an explanation for an open question regarding the PMEPR bound of certain sequences, providing a deeper understanding of their properties.

Key Results

The paper presents a generalized framework for constructing complementary sequence and array sets and complete complementary codes. Key results include:

  • Construction of New CSAs, CCAs, CSSs, and CCCs: The proposed framework, leveraging new delay matrices and block matrix PU constructions, generates an "extremely large number" of new CSAs, CCAs, CSSs, and CCCs.
  • Inclusion of Existing Constructions: Known constructions of CSSs (Paterson, Schmidt) and CCCs (Reed-Muller codes) are shown to be special cases of the proposed framework.
  • Recursive GBF Determination: The GBFs of the newly constructed sequences and arrays are determined recursively.
  • Explanation of PMEPR Bound: The paper provides an explanation for the PMEPR bound of sequences related to an open question posed in 2000.

Limitations and Future Work

  • Computational Complexity: While the paper introduces a powerful framework, the computation of quadratic terms for GBFs can be computationally intensive, especially for larger parameters. The authors note that the computation complexity can be significant, even for moderate N.
  • Open Questions on Hadamard Matrices: The paper highlights that the number of equivalence classes of Butson-type Hadamard matrices is still an open problem, which impacts the full enumeration of possible constructions.
  • General Explicit GBF Forms: The authors pose the question of whether a general explicit GBF form can be found for specified Butson-type Hadamard matrices (e.g., Fourier or Walsh matrices).
  • PMEPR Control: While the paper contributes to understanding PMEPR, the problem of optimal linear code selection and coset representatives for PMEPR control remains an open area.
  • Further Exploration of Binary/Quaternary Sequences: The paper suggests further investigation into general forms for binary and quaternary sequences in CSSs of size 4.

Summary updated

Abstract

Previously, we have presented a framework to use the para-unitary (PU) matrix-based approach for constructing new complementary sequence set (CSS), complete complementary code (CCC), complementary sequence array (CSA), and complete complementary array (CCA). In this paper, we introduce a new class of delay matrices for the PU construction. In this way, generalized Boolean functions (GBF) derived from PU matrix can be represented by an array of size $2\times 2 \times \cdots \times 2$. In addition, we introduce a new method to construct PU matrices using block matrices. With these two new ingredients, our new framework can construct an extremely large number of new CSA, CCA, CSS and CCC, and their respective GBFs can be also determined recursively. Furthermore, we can show that the known constructions of CSSs, proposed by Paterson and Schmidt respectively, the known CCCs based on Reed-muller codes are all special cases of this new framework. In addition, we are able to explain the bound of PMEPR of the sequences in the part of the open question, proposed in 2000 by Paterson.
BibTeX
@article{wang2021new,
  author = {Zilong Wang and Dongxu Ma and Erzhong Xue and Guang Gong and Srdjan Budisin},
  title = {{New Construction of Complementary Sequence (or Array) Sets and Complete Complementary Codes (II)}},
  journal = {IEEE Trans. Information Theory},
  year = {2021},
  url = {https://openreview.net/forum?id=lbXaUqQuYH},
}
Figure