A Caltech Library Service

Constrained Codes as Networks of Relations

Schwartz, Moshe and Bruck, Jehoshua (2008) Constrained Codes as Networks of Relations. IEEE Transactions on Information Theory, 54 (5). pp. 2179-2195. ISSN 0018-9448. doi:10.1109/TIT.2008.920245.

See Usage Policy.


Use this Persistent URL to link to this item:


We address the well-known problem of determining the capacity of constrained coding systems. While the one-dimensional case is well understood to the extent that there are techniques for rigorously deriving the exact capacity, in contrast, computing the exact capacity of a two-dimensional constrained coding system is still an elusive research challenge. The only known exception in the two-dimensional case is an exact (however, not rigorous) solution to the (1,∞)-run-length limited (RLL) system on the hexagonal lattice. Furthermore, only exponential-time algorithms are known for the related problem of counting the exact number of constrained two-dimensional information arrays. We present the first known rigorous technique that yields an exact capacity of a two-dimensional constrained coding system. In addition, we devise an efficient (polynomial time) algorithm for counting the exact number of constrained arrays of any given size. Our approach is a composition of a number of ideas and techniques: describing the capacity problem as a solution to a counting problem in networks of relations, graph-theoretic tools originally developed in the field of statistical mechanics, techniques for efficiently simulating quantum circuits, as well as ideas from the theory related to the spectral distribution of Toeplitz matrices. Using our technique, we derive a closed-form solution to the capacity related to the Path-Cover constraint in a two-dimensional triangular array (the resulting calculated capacity is 0.72399217...). Path-Cover is a generalization of the well known one-dimensional(0,1)-RLL constraint for which the capacity is known to be 0.69424....

Item Type:Article
Related URLs:
URLURL TypeDescription
Schwartz, Moshe0000-0002-1449-0026
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© Copyright 2008 IEEE. Reprinted with permission. Manuscript received August 5, 2007; revised January 6, 2008. [Date Published in Issue: 2008-04-22] This work was supported in part by the Caltech Lee Center for Advanced Networking. Communicated by T.J. Richardson, Associate Editor for Coding Theory. The first author would like to thank Matthew Cook for introducing him to networks of relations. Both authors would like to thank Albrecht Böttcher, Paolo Tilli, and Harold Widom, for providing help with the theory of Toeplitz determinants. The authors also wish to thank Peter Keevash and Eyal Rozenman for commenting on earlier versions of this work. Finally, the authors would like to thank the two anonymous reviewers, whose comments improved the presentation of this paper.
Subject Keywords:Capacity of constrained systems, capacity of two-dimensional constrained systems, Fisher–Kasteleyn–Temperley (FKT) method, holographic reductions, networks of relations, spectral distribution of Toeplitz matrices
Issue or Number:5
Record Number:CaltechAUTHORS:SCHWieeetit08
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:10660
Deposited By: Archive Administrator
Deposited On:30 May 2008
Last Modified:08 Nov 2021 21:09

Repository Staff Only: item control page