Constructions of Optimal and Near-Optimal Multiply Constant-Weight Codes

Yeow Meng Chee, Han Mao Kiah, Hui Zhang, Xiande Zhang

Abstract

Multiply Constant-Weight Codes (MCWCs) are a specialized class of error-correcting codes essential for securing hardware through Physically Unclonable Functions (PUFs). This paper advances the theory of MCWCs by bridging coding theory with combinatorial design to construct new families of optimal codes. The authors demonstrate that theoretical upper bounds on code size are asymptotically reachable and extend these findings to Two-Dimensional MCWCs, providing a foundation for reliable authentication in emerging memory technologies.

Introduction

In hardware security, Physically Unclonable Functions (PUFs) serve as unique digital fingerprints for silicon chips, leveraging microscopic manufacturing variations. However, these fingerprints are often noisy and require error correction to be reliable for authentication in devices like RFIDs or smart cards. Multiply Constant-Weight Codes (MCWCs) are ideally suited for this task.

An MCWC is a binary code where each codeword is partitioned into $m$ parts of length $n$, with each part maintaining a fixed weight $w$. While standard constant-weight codes are well-studied, the theory for their "multiply" counterparts remained rudimentary. Prior to this research, the maximum possible size for many MCWCs was unknown, and efficient construction methods were lacking. This paper addresses these gaps and explores Two-Dimensional MCWCs, which are vital for holographic memory and memristor arrays where data is arranged in matrices with both row and column weight constraints.

Methods

The authors utilize a sophisticated toolkit from combinatorial design theory to solve these coding challenges:

  • Generalized Packing Designs: The research establishes a mathematical equivalence between finding an optimal MCWC and solving specific set-system packing problems, allowing the application of established design theory results.
  • Product Constructions: A method was developed to "multiply" smaller, optimal constant-weight codes to form larger, optimal MCWCs.
  • Hypergraph Theory: To prove that theoretical bounds are "tight," the authors applied Kahn’s Theorem on fractional matchings in hypergraphs. This demonstrates that as code length grows, the space of possible codewords can be filled almost perfectly.
  • Latin Squares: For 2D codes, Latin rectangles and squares were employed to ensure weight constraints are met simultaneously across both rows and columns.

Key Results

The study provides several breakthroughs in the understanding of MCWC limits and constructions. The paper identifies exact maximum sizes for MCWCs with a total weight of 4 and distance 4, and introduces new infinite families of optimal codes for distance 4 with weights of 2 or 3 per part.

A major contribution is the proof that "Johnson-type" upper bounds for these codes are asymptotically tight. This means the gap between theoretical limits and realizable code sizes vanishes as the code length $n$ increases. Additionally, new upper bounds for 2D-MCWCs were established, and concrete examples of optimal 2D codes were provided.

Table showing maximum sizes $D((n_1, n_2), (3, 1), 3)$ for specific parameter sets.

Discussion and Future Work

While this work significantly advances the field, several areas remain for future exploration. Some specific small-scale cases, such as $k=(2,2)$ with certain odd lengths, remain undetermined. Furthermore, the construction of 2D-MCWCs is notably more complex than 1D versions; while product constructions exist, finding optimal codes for all possible parameters is an ongoing challenge. Finally, while this paper focuses on the existence and construction of codes, future research is needed to develop efficient real-time decoding algorithms for these specialized 2D structures.

Summary updated

BibTeX
@article{chee2017constructions,
  author = {Yeow Meng Chee and Han Mao Kiah and Hui Zhang and Xiande Zhang},
  title = {{Constructions of Optimal and Near-Optimal Multiply Constant-Weight Codes}},
  journal = {IEEE Trans. Information Theory},
  year = {2017},
  doi = {10.1109/tit.2017.2690450},
}
Figure