Schwartz, Moshe and Bruck, Jehoshua (2007) Constrained Codes as Networks of Relations. California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechPARADISE:2007.ETR082
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:2007.ETR082
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.
|Item Type:||Report or Paper (Technical Report)|
|Additional Information:||This work was supported in part by the Caltech Lee Center for Advanced Networking. Also available from http://www.paradise.caltech.edu/papers/etr082.pdf|
|Group:||Parallel and Distributed Systems Group|
|Usage Policy:||You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.|
|Deposited By:||Imported from CaltechPARADISE|
|Deposited On:||27 Jul 2007|
|Last Modified:||26 Dec 2012 13:53|
Repository Staff Only: item control page