A Note on “Optimum Sets of Interference-Free Sequences With Zero Autocorrelation Zone”

Qiping Fang, Zilong Wang2022 · arXiv

TL;DR

This paper introduces a simplified method for constructing optimal Interference-Free Zero Correlation Zone (IF-ZCZ) sequence sets using the Finite Zak Transform (FZT). The authors prove that existing, complex general constructions are mathematically equivalent to their simple approach, while demonstrating significant reductions in both alphabet size and the computational complexity required for signal processing.

What Problem Does This Paper Address?

In modern communication (like LTE and 5G) and radar systems, sequences must have "good correlation" to distinguish signals from noise and other users. Ideally, a sequence should have zero correlation with itself at any time shift (auto-correlation) and zero correlation with other sequences (cross-correlation). However, the Welch bound proves that such "perfect" sequences are mathematically impossible.

Engineers use Zero Correlation Zone (ZCZ) sequences as a compromise: they provide perfect correlation properties within a specific time-delay window. Interference-Free (IF) ZCZ sequences go a step further by ensuring zero cross-correlation across the entire period. While "general constructions" for these sequences exist (notably by Popović), they are mathematically dense and difficult to implement efficiently. This paper seeks to simplify the construction and reduce the heavy computational load of the "matched filters" used to detect these signals.

Methods

The authors leverage the Finite Zak Transform (FZT), a mathematical tool that represents a 1D sequence as a 2D time-frequency lattice.

  1. Simple Construction ($\mathcal{S}_1$): They propose a construction where sequences are created by taking a "perfect" sequence, extending it periodically, and applying a specific phase rotation.
  2. Equivalence Proof: By defining a set of "transformations" (like permutations, shifts, and rational phase rotations) that preserve ZCZ properties, they prove that the complex "general construction" found in previous literature is actually equivalent to their simpler $\mathcal{S}_1$ method.
  3. Zak-Domain Implementation: Instead of processing signals in the time domain, they perform matched filtering in the Zak domain. Because their sequences have "sparse" Zak spectra (meaning most values in the 2D lattice are zero), the number of required multiplications drops drastically.

Datasets

As a theoretical paper in signal processing, no external datasets were used. The authors validate their findings through:

  • Mathematical Proofs: Demonstrating optimality against the Tang-Fan-Matsufuji bound.
  • Numerical Examples: Providing specific sequence sets (e.g., $N=16$ and $N=32$) to illustrate the construction and its properties.

Key Insights and Ideas

  • Sparsity is the "Aha!" Moment: The proposed sequences result in Zak spectra where only one row (or specific elements) contains non-zero values. This sparsity is the secret sauce that allows a receiver to skip thousands of unnecessary calculations.
  • The "General" isn't so General: By proving equivalence, the authors show that the previously known "general construction" didn't actually offer more variety—it was just a more complicated way of describing the same fundamental sequence structure.
  • Alphabet Size Matters: In hardware, the "alphabet size" (the number of distinct phase values a sequence can take) affects memory and precision. The authors show that for certain cases, the alphabet size can be a factor of the period ($KM$ instead of $KM^2$), making it more hardware-friendly.

Key Results

  • Theoretical Optimality: The sequences reach the Tang-Fan-Matsufuji bound, meaning they achieve the maximum possible ZCZ length for a given set size and period.
  • Massive Computational Speedup: The paper compares a traditional time-domain matched filter to their Zak-domain approach. For a sequence set with period $N=128$ and size $K=32$:
  • Time-domain complexity: ~1,044,480 operations.
  • Proposed Zak-domain complexity: 926 operations.
  • This represents a ~1,100x reduction in computational effort for the receiver.

Limitations and Future Work

  • Scope of Equivalence: While the authors proved that the most famous general construction is equivalent to their simple one, they leave an open question: Does there exist an optimal IF-ZCZ sequence set that cannot be reduced to this simple construction?
  • Hardware Realities: The paper focuses on the number of complex multiplications/additions. Future work could explore how these sequences perform under real-world hardware constraints like fixed-point quantization or non-linear power amplifier distortion.

Summary updated

Abstract

In this paper, a simple construction of interference-free zero correlation zone (IF -ZCZ) sequence sets is proposed by well designed finite Zak transform lattice tessellation. Each set is characterized by the period of sequences <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$KM$</tex> , the set size <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$K$</tex> and the length of zero correlation zone <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$M-1$</tex> , which is optimal with respect to the Tang-Fan-Matsufuji bound. Secondly, the transformations that keep the properties of the optimal IF -ZCZ sequence set unchanged are given, and the equivalent relation of the optimal IF -ZCZ sequence set is defined based on these transformations. Then, it is proved that the general construction of the optimal IF -ZCZ sequence set proposed by Popovic is equivalent to the simple construction of the optimal IF -ZCZ sequence set, which indicates that the generation of the optimal IF -ZCZ sequence set can be simplified. Moreover, it is pointed out that the alphabet size for the special case of the simple construction of the optimal IF -ZCZ sequence set can be a factor of the period. Finally, both the simple construction of the optimal IF -ZCZ sequence set and its special case have sparse and highly structured Zak spectra, which can greatly reduce the computational complexity of implementing matched filter banks.
BibTeX
@inproceedings{fang2022note,
  author = {Qiping Fang and Zilong Wang},
  title = {{A Note on “Optimum Sets of Interference-Free Sequences With Zero Autocorrelation Zone”}},
  booktitle = {2022},
  year = {2022},
}
Figure