The PBD-Closure of Constant-Composition Codes

Yeow Meng Chee, Alan C. H. Ling, San Ling, Hao Shen

TL;DR

This paper introduces a powerful technique called "PBD-closure" to determine the exact size of optimal constant-composition codes for an infinite number of code lengths. This breakthrough allows researchers to derive the size of these codes from just a single example, significantly advancing the field of coding theory and its applications.

What Problem Does This Paper Address?

Constant-composition codes are a generalization of traditional constant-weight codes, finding applications in areas like error correction, data transmission, and DNA computing. A central challenge in this field is determining the maximum possible size of such codes for given parameters (length, distance, alphabet size, and composition of codewords). While progress has been made, finding these optimal sizes for all possible parameters has been a long-standing problem, particularly for infinite families of code lengths. This paper tackles this challenge by developing a general method to solve for these sizes across many parameter sets.

Methods

The core of this paper lies in the concept of Pairwise Balanced Design (PBD) closure. A PBD is a combinatorial structure where sets of points are grouped into "blocks" such that every pair of points appears in exactly one block. The PBD-closure of a set of integers $K$ is the set of all integers $n$ for which a PBD with block sizes from $K$ exists.

The authors leverage a key theorem that states that if a set of code lengths $M_c(d, w; q)$ (representing lengths for which optimal codes of a certain size $c \cdot n(n-1)$ exist) is PBD-closed, then we can determine the optimal code size for all lengths in its PBD-closure. This is achieved by constructing a new code from an existing PBD and a set of known optimal codes for the block sizes.

To make this practical, the paper also utilizes Group Divisible Designs (GDDs), which are related to PBDs but allow for a more structured construction. By combining the PBD-closure principle with existing GDD constructions and known optimal codes for small lengths, the authors can derive optimal code sizes for infinite families of lengths. Wilson's theory of PBD-closure is a cornerstone of this approach, providing conditions under which PBDs exist for sufficiently large lengths.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and existence proofs rather than empirical evaluation on datasets.

Key Insights and Ideas

  • PBD-Closure as a Unifying Tool: The paper demonstrates that the PBD-closure property is a powerful, general concept that can be applied to determine optimal code sizes across various parameters, not just for a single specific case.
  • Bridging Small and Large Instances: By connecting the existence of PBDs (which are often guaranteed for large lengths by Wilson's theory) with known optimal codes for small lengths, the PBD-closure method effectively bridges the gap between small, manually verifiable cases and infinite families of larger cases.
  • Leveraging GDDs for Construction: The paper highlights the importance of Group Divisible Designs (GDDs) as a practical tool for constructing the codes needed to prove the PBD-closure property.
  • Solving Long-Standing Problems: The paper successfully resolves the problem of determining the size of optimal ternary constant-composition codes with distance four and weight three for all sufficiently large odd lengths, a problem that was previously open for many cases.

Key Results

The paper provides explicit formulas for the size of optimal constant-composition codes for several infinite families of parameters. Notably:

  • Ternary Codes (q=3), Distance d=4, Weight w=[2,1]: The exact size $A_3(n, 4, [2,1])$ is determined for all sufficiently large odd $n$. For $n \equiv 1 \pmod 4$, $A_3(n, 4, [2,1]) = n(n-1)/4$. For $n \equiv 3 \pmod 4$, the size is given by $n(n-1)/4 - \epsilon(n)/6$, where $\epsilon(n)$ is a specific function of $n \pmod{12}$.
  • Quaternary Codes (q=4), Distance d=3, Weight w=[1,1,1]: $A_4(n, 3, [1,1,1]) = n(n-1)$ for all $n \ge 4$, with a few exceptions for small $n$.
  • Quaternary Codes (q=4), Distance d=4, Weight w=[1,1,1]: $A_4(n, 4, [1,1,1]) = n(n-1)/2$ for all sufficiently large $n \equiv 1 \pmod 2$, and $n(n-2)/2$ for sufficiently large $n \equiv 0 \pmod 2$.
  • Quaternary Codes (q=4), Distance d=5, Weight w=[1,1,1]: $A_4(n, 5, [1,1,1]) = n$ for $n \ge 7$.

Limitations and Future Work

  • Asymptotic Results: The PBD-closure approach primarily yields results for "sufficiently large" lengths $n$. The paper acknowledges that determining the exact size for all small lengths can still be challenging and often requires specific constructions or exhaustive searches.
  • Scope of Application: While the PBD-closure technique is general, the paper focuses on illustrating its power with specific examples. The authors suggest that this approach can be applied to many more parameter sets by discovering new GDD constructions and optimal codes for smaller lengths.
  • "Good" Non-optimal Codes: The paper notes that the techniques developed can also be used to construct "good" non-optimal constant-composition codes, an area for future exploration.
  • New GDDs and Optimal Codes: Future work will likely involve finding more GDDs and optimal codes for smaller lengths to extend the applicability of the PBD-closure method to a wider range of parameters.

Summary updated

BibTeX
@article{chee2007pbd,
  author = {Yeow Meng Chee and Alan C. H. Ling and San Ling and Hao Shen},
  title = {{The PBD-Closure of Constant-Composition Codes}},
  journal = {IEEE Trans. Information Theory},
  year = {2007},
  doi = {10.1109/tit.2007.901175},
}

Loading related content...

Figure