Zero/Positive Capacities of Two-Dimensional Runlength Constrained
Arrays
Kenny Paterson
Royal Holloway
A binary sequence satisfies a one-dimensional (d_1,k_1,d_2,k_2) runlength
constraint if every run of zeroes has length at least d_1 and at most k_2
and every run of ones has length at least d_2 and at most k_2. A
two-dimensional binary array is (d_1,k_1,d_2,k_2;d_3,k_3,d_4,k_4)
constrained if it satisfies a (d_1,k_1,d_2,k_2) constraint horizontally (on
every row) and a
(d_3,k_3,d_4,k_4) constraint vertically (on every column). Such constrained
arrays have applications in two-dimensional digital storage applications.
Given 8 parameters
d_1,k_1,d_2,k_2,d_3,k_3,d_4,k_4, a basic question is:
How many (d_1,k_1,d_2,k_2;d_3,k_3,d_4,k_4) constrained arrays of size m by n
are there?
This will determine the rate at which information can be encoded by arrays
satisfying the constraint. Let N(m,n) denote this number, and define the
capacity of the constraint to be
the limit as m and n tend to infinity of (1/mn) log_2 N(m,n). We study the
question of deciding for which parameters the capacity of a constraint is
zero, and for which parameters it is positive. We obtain a complete answer
in the case where the zeroes and ones are constrained in the same way in
each dimension (but where the horizontal and vertical constraints may be
different). We obtain a partial answer in the case where the same
constraints are applied in each dimension, but where the zeroes and ones may
be constrained differently. Finally, we have some results for completely
general parameters.
Joint work with Professor Tuvi Etzion, Department of Computer Science,
Technion, Israel.