Capacity of Hexagonal Checkerboard Codes

Zhun Deng, Jie Ding, Mohammad Noshad, Vahid Tarokh

TL;DR

This paper introduces a novel, more efficient method for calculating the capacity of hexagonal checkerboard codes, which are crucial for data storage on surfaces. Their approach yields tighter bounds than previous methods, offering a significant improvement in both accuracy and computational complexity.

What Problem Does This Paper Address?

The paper tackles the challenge of determining the "capacity" of hexagonal checkerboard codes. These codes are used to represent binary data (0s and 1s) arranged on a hexagonal lattice, mimicking the densest packing of circles in 2D. This arrangement is relevant for data storage systems where physical constraints dictate how data points can be placed. The core problem is to find the maximum rate at which information can be reliably transmitted or stored using these codes, subject to specific "hexagonal constraints." These constraints dictate that a '1' can only be surrounded by '0's, while a '0' can be surrounded by any combination of '0's and '1's. Calculating this capacity precisely is computationally difficult, and existing methods provide bounds that are either not tight enough or too computationally expensive.

Methods

The authors propose a modified "transfer matrix" method to derive rigorous lower and upper bounds on the hexagonal checkerboard code capacity. The transfer matrix method is a standard technique for analyzing sequences with local constraints. Their innovation lies in how they construct and utilize these matrices for the hexagonal lattice.

Key methodological steps include:

  • Zigzag Regions: They define specific "zigzag" shaped regions on the hexagonal lattice to analyze. This choice is crucial for constructing nonnegative and irreducible matrices, which are requirements for applying the Perron-Frobenius theorem.
  • Row and Column Types: They categorize rows of these zigzag regions into "L" (left) and "R" (right) types based on the position of their first element relative to adjacent rows. This distinction is important for defining valid transitions between rows.
  • Transfer Matrix Construction: They define a transfer matrix ($T_m$) whose dimensions depend on the width ($m$) of the zigzag region. The entries of this matrix represent the valid transitions between different row configurations.
  • Eigenvalue Analysis: The capacity is related to the largest eigenvalue ($\sigma_{max}$) of these transfer matrices. The paper leverages properties of eigenvalues and matrix powers to derive bounds.
  • Modified Transfer Matrix: They also introduce a related matrix, $X_n$, which is used to analyze the "shaded part" of the hexagonal grid. This matrix is derived from the original transfer matrix and helps in obtaining tighter bounds.
  • Upper Bound Matrix: For upper bounds, they introduce a matrix $B_n$ derived from the trace of powers of the transfer matrix, which also relies on eigenvalue analysis.

The core novelty is the specific construction of these matrices tailored to the hexagonal lattice and the zigzag regions, leading to more accurate bounds compared to prior work on integer lattices.

Datasets

Not discussed in the paper. The paper focuses on theoretical bounds for a constrained coding problem, not on empirical evaluation using datasets.

Key Insights and Ideas

  • Hexagonal Lattice Density is Key: The paper highlights that the hexagonal lattice is chosen because it represents the densest packing of circles in 2D, making it a relevant model for certain data storage scenarios.
  • Zigzag Regions Simplify Analysis: The choice of zigzag regions is a clever simplification that allows for the construction of well-behaved matrices (nonnegative and irreducible) essential for applying powerful mathematical tools like the Perron-Frobenius theorem.
  • Tighter Bounds with Less Complexity: The primary insight is that their modified transfer matrix approach, by carefully defining row types and using related matrices ($X_n$, $B_n$), yields significantly tighter bounds on the capacity than previous methods, while requiring comparable or even less computational effort for similar accuracy.
  • Convergence of Bounds: The paper demonstrates that their bounds converge to the true capacity, and the convergence is faster than some existing methods, especially for practical matrix sizes.

Key Results

The paper provides rigorous lower and upper bounds for the capacity of hexagonal checkerboard codes.

  • Lower Bound: The paper derives a lower bound using the largest eigenvalue of the $X_n$ matrix. For $n=18$, this bound is $0.4807676144$.
  • Upper Bound: An upper bound is derived using the trace of powers of the transfer matrix and the largest eigenvalue of the $B_n$ matrix. For $n=3$, this upper bound is $0.4813$.
  • Comparison: Their calculated bounds ($0.4807676144 < C < 0.4813$) are shown to be much tighter than those obtained by Weeks et al. [1] for similar computational complexity. For instance, Weeks' method with $X_{18}$ yields bounds of $0.4640 < C < 0.4897$.
  • Accuracy: The paper's method provides an estimate that is consistent with more recent, highly precise estimations (e.g., Halevy et al. [7], [16]), matching up to 7 decimal places for the lower bound.

Limitations and Future Work

  • Computational Complexity: While their method is more efficient than some prior work, calculating the largest eigenvalues of large matrices ($X_n$ and $B_n$) can still become computationally demanding as $n$ increases, due to the Fibonacci-like growth in matrix size. The paper notes this as a trade-off between accuracy and complexity.
  • Generalization: The paper focuses on a specific hexagonal constraint. Future work could explore variations of these constraints or apply the developed methodology to other lattice structures or coding problems.
  • Exact Capacity: The paper provides bounds, not the exact capacity. Determining the exact capacity remains an open challenge, though their bounds are very close.

Summary updated

Abstract

In this paper, we propose a new method to bound the capacity of checkerboard codes on the hexagonal lattice. This produces rigorous bounds that are tighter than those commonly known.
BibTeX
@misc{deng2015capacity,
  author = {Zhun Deng and Jie Ding and Mohammad Noshad and Vahid Tarokh},
  title = {{Capacity of Hexagonal Checkerboard Codes}},
  year = {2015},
  eprint = {1506.02163},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1506.02163},
}

Loading related content...

Figure