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.