Three New Families of Zero-difference Balanced Functions with Applications

Cunsheng Ding, Qi Wang, Maosheng Xiong

Introduction

Zero-difference balanced (ZDB) functions are a specialized class of functions that play a crucial role in combinatorics, coding theory, and communications engineering. A function $f$ from an additive group $(G, +)$ to a set $V$ is called ZDB if the difference between function values $f(x+a) - f(x)$ takes each non-zero value in $V$ a constant number of times for any fixed non-zero shift $a \in G$. These functions are foundational for constructing optimal error-correcting codes and synchronization systems.

The Challenge of Parameter Flexibility

While several families of ZDB functions have been documented, they often suffer from rigid parameter constraints. For instance, many existing constructions are limited to cyclic groups of odd order, which restricts their applicability in designing Constant Composition Codes (CCCs) for power-line communications and flash memories, or Difference Systems of Sets (DSSs) for data stream synchronization. This research addresses these limitations by introducing three new families of ZDB functions with more flexible parameters and broader group applicability.

New Constructions of ZDB Functions

The authors propose three distinct mathematical constructions that expand the known set of ZDB parameters.

1. Generalized Cyclotomy on Abelian Groups

Moving beyond simple cyclic groups ($\mathbb{Z}_n$), the first construction utilizes the product of multiple finite fields ($GF(q_1) \times \dots \times GF(q_k)$). By partitioning these fields into cosets of specific cyclic subgroups, the authors define ZDB functions on non-cyclic abelian groups. This allows for even values of $n$, a significant departure from previous odd-order constraints.

2. 2-Cyclotomic Cosets (Families A and B)

The second and third constructions focus on cyclic groups where the order $n = 2^m - 1$.

  • Family A (Theorem 2): Defined for prime $m$, this construction uses the "leaders" of 2-cyclotomic cosets to map function values.
  • Family B (Theorem 3): Designed for odd primes $m$, this variation groups a coset with its negative to produce ZDB functions with larger difference parameters.
Table 1: Comparison of parameters for known and new ZDB functions. The last three rows highlight the new contributions (Theorems 1, 2, and 3) of this paper.

Applications in Coding and Synchronization

The primary value of these new ZDB functions lies in their application to optimal code construction.

Optimal Constant Composition Codes (CCCs)

CCCs are codes where every codeword has the same weight distribution. The paper demonstrates that the CCCs derived from these new ZDB functions are optimal, meaning they reach the theoretical maximum size for a given length and distance.

Table 2: Parameters of optimal Constant Composition Codes (CCCs) derived from the newly proposed ZDB functions.

Perfect Difference Systems of Sets (DSSs)

DSSs are used to synchronize data streams. The constructions based on 2-cyclotomic cosets yield DSSs that are both optimal and perfect, representing the highest standard for synchronization applications.

Conclusion

By breaking the cyclic constraint and leveraging the properties of 2-cyclotomic cosets, this work provides a "master key" for solving complex problems in storage and signal synchronization. The new families of ZDB functions offer unprecedented flexibility in parameter selection, paving the way for more efficient communication and cryptographic systems.

Summary updated

Abstract

Zero-difference balanced (ZDB) functions integrate a number of subjects in combinatorics and algebra, and have many applications in coding theory, cryptography and communications engineering. In this paper, three new families of ZDB functions are presented. The first construction, inspired by the recent work \cite{Cai13}, gives ZDB functions defined on the abelian groups $(\gf(q_1) \times \cdots \times \gf(q_k), +)$ with new and flexible parameters. The other two constructions are based on $2$-cyclotomic cosets and yield ZDB functions on $\Z_n$ with new parameters. The parameters of optimal constant composition codes, optimal and perfect difference systems of sets obtained from these new families of ZDB functions are also summarized.
BibTeX
@article{ding2014three,
  author = {Cunsheng Ding and Qi Wang and Maosheng Xiong},
  title = {{Three New Families of Zero-difference Balanced Functions with Applications}},
  journal = {IEEE Trans. Information Theory},
  year = {2014},
  url = {https://openreview.net/forum?id=lIhD7HdPgjH},
}

Loading related content...

Figure