The Positive Capacity Region of Two-Dimensional Run-Length-Constrained Channels

A binary sequence satisfies a one-dimensional (d,k) constraint if every run of zeros (with possible exception of the first and the last runs) has length at least d and at most k. A binary two-dimensional array satisfies a (d,k) constraint if each row and each column satisfies the one-dimensional (d,k) constraint. Few models have been proposed in the literature to handle two-dimensional data: the diamond model, the square model, the hexagonal model, and the triangular model. The constraints in the different directions might be asymmetric and hence many kind of constraints are defined depending on the number of directions in the model. For example, a two-dimensional array in the diamond model satisfies a (d₁,k₁,d₂,k ₂) constraint if it satisfies the one-dimensional (d₁ ,k₁) constraint horizontally and the one-dimensional (d ₂,k₂) constraint vertically. In this correspondence, the region in which the capacity is zero or positive, in the various models, is examined. Asymmetric constraints in the diamond model and symmetric constraints in the other models are considered. In particular, an almost complete solution for asymmetric constraints in the diamond model is provided