Constrained Codes as Networks of Relations

Abstract

We revisit the well-known problem of determining the capacity of constrained systems. While the one-dimensional case is well understood, the capacity of two-dimensional systems is mostly unknown. When it is non-zero, except for the (1,1)-RLL system on the hexagonal lattice, there are no closed-form analytical solutions known. Furthermore, for the related problem of counting the exact number of constrained arrays of any given size, only exponential-time algorithms are known. We present a novel approach to finding the exact capacity of two-dimensional constrained systems, as well as efficiently counting the exact number of constrained arrays of any given size. To that end, we borrow graph-theoretic tools originally developed for the field of statistical mechanics, tools for efficiently simulating quantum circuits, as well as tools from the theory of the spectral distribution of Toeplitz matrices.