An OACF-Preserving Operation Based on Parker's Transformation

Geyang Wang, Qi Wang

TL;DR

This paper introduces a novel operation called "nega-decimation" that preserves the odd-periodic autocorrelation function (OACF) of binary sequences. This new tool helps to simplify the classification of existing binary sequences with desirable correlation properties, reducing Parker's 16 sequence classes down to 8.

What Problem Does This Paper Address?

In modern communication systems, binary sequences with specific correlation properties are crucial for efficient and reliable data transmission. One such property is a low odd-periodic autocorrelation function (OACF). While some operations like negation and cyclic shifts are known to preserve these desirable OACF values, the landscape of such operations was not fully understood. Specifically, the paper addresses the challenge of classifying and understanding the relationships between various constructions of binary sequences with low OACF, particularly those derived from Parker's transformation. The authors aim to provide a more unified framework for these sequences by introducing a new OACF-preserving operation.

Methods

The core contribution of this paper is the definition and analysis of a new operation called nega-decimation. This operation is inspired by Parker's transformation, which relates sequences with low OACF to sequences with low periodic autocorrelation function (PACF). The authors formally define nega-decimation and then prove that it is indeed OACF-preserving. To demonstrate its utility, they apply this new operation to classify the 16 classes of binary sequences originally proposed by Parker. This classification effectively reduces the number of distinct classes from 16 to 8, highlighting redundancies and equivalences among them. The paper also includes proofs of several lemmas that establish the properties of OACF and PACF distributions, which are essential for proving the OACF-preserving nature of nega-decimation.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and classifications of binary sequences rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Nega-decimation is a new OACF-preserving operation: This is the central finding. It expands the toolkit for manipulating sequences while maintaining good correlation properties.
  • Simplification of Parker's 16 classes: The introduction of nega-decimation allows for a more parsimonious classification of existing sequences, reducing 16 classes to 8. This suggests that some of Parker's original constructions were equivalent under this new operation.
  • Unifying framework for sequence construction: The paper suggests that nega-decimation, along with negation and nega-cyclic shift, provides a more complete set of operations for understanding and generating sequences with low OACF. This could lead to a more systematic approach to designing such sequences in the future.
  • Decimation is NOT OACF-preserving: The paper explicitly provides an example to show that standard decimation, unlike its "nega" counterpart, does not preserve OACF values, clarifying a potential misunderstanding.

Key Results

  • The paper formally defines and proves that nega-decimation is an OACF-preserving operation for binary sequences.
  • The 16 classes of binary sequences proposed by Parker are classified into 8 equivalent classes using the nega-decimation operation.
  • The paper demonstrates that standard decimation is not OACF-preserving with a concrete example.

Limitations and Future Work

  • Limited to Parker's transformation: While the paper classifies Parker's 16 cases, it acknowledges that further work might be needed to classify all constructions of binary sequences based on Parker's transformation.
  • Theoretical focus: The paper is primarily theoretical, focusing on the properties of operations and classifications rather than empirical performance metrics on communication systems.
  • Future Directions: The authors suggest that this work may pave the way for a more comprehensive classification of binary sequences with desirable correlation properties, potentially leading to new sequence designs for communication systems. They also hint at the possibility of further simplifying existing classifications.

Summary updated

Abstract

Binary sequences with low odd-periodic correlation magnitudes have found important applications in communication systems. It is well known that the three operations, negacyclic shift, decimation, and negation, preserve the odd-periodic autocorrelation function (OACF) in general. In this paper, we define a new operation based on Parker's transformation, which also preserves the OACF of binary sequences. This enables us to classify Parker's 16 cases into 8 ones, and may possibly further allow to classify all constructions based on Parker's transformation.
BibTeX
@inproceedings{wang2019oacf,
  author = {Geyang Wang and Qi Wang},
  title = {{An OACF-Preserving Operation Based on Parker's Transformation}},
  booktitle = {IWSDA},
  year = {2019},
  url = {https://openreview.net/forum?id=i3P7pfJXSq6},
}
Figure