[IEEE Trans. on Information Theory, July 1999, pp. 1527-1540]
On the Capacity of Two-Dimensional Run Length Constrained Channels
Akiko Kato and Kenneth Zeger
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_{d,k}$
is defined as
$C_{d,k} = \lim_{m,n\rightarrow\infty}{\log_2N_{m,n}^{(d,k)}/ mn}$,
where $N_{m,n}^{(d,k)}$ denotes the number of $m\times n$ rectangular
patterns that satisfy the two-dimensional $(d,k)$ run length constraint.
Bounds on $C_{d,k}$ are given and
it is proven for every $d\ge1$
and every $k>d$
that $C_{d,k}=0$ if and only if $k=d+1$.
Encoding algorithms are also discussed.