On the capacity of two-dimensional run-length constrained channels

Abstract

Two-dimensional binary patterns that satisfy one-dimensional (d, k) run-length constraints both horizontally and vertically are considered. For a given d and k, the capacity C/sub d,k/ is defined as C/sub d,k/=lim/sub m,n/spl rarr//spl infin//log/sub 2/N/sub m,n//sup d,k//mn, where N/sub m,n//sup d,k/ denotes the number of m/spl times/n rectangular patterns that satisfy the two-dimensional (d,k) run-length constraint. Bounds on C/sub d,k/ are given and it is proven for every d/spl ges/1 and every k>d that C/sub d,k/=0 if and only if k=d+1. Encoding algorithms are also discussed.