Technical Report MSC-2006-11

Title: Constrained Codes for Two-Dimensional Channels
Authors: Keren Censor
Supervisors: Tuvi Etzion
Abstract: In digital data storage systems, such as magnetic and optical storage devices, the recorded data has to satisfy certain constraints that are imposed by the physical structure of the media. One of the most frequently investigated type of constraints are the \emph{(d,k) run-length limited} (RLL) constraints. A binary sequence satisfies a one-dimensional $(d,k)$ constraint if every run of zeroes has length at least $d$ and at most $k$.

Recent developments in optical storage, especially in holographic memory, regard the recorded data as two-dimensional. A one-dimensional constraint has to be satisfied in each of the array directions. Similarly to the one-dimensional case, the capacity of a two-dimensional constraint $\Theta$ is defined as: \[C(\Theta) = \lim_{n,m \rightarrow \infty} \frac{\log_2(n,m~|~\Theta)}{nm},\] where $N(n,m~|~\Theta)$ is the number of arrays of size $n \times m$ that satisfy $\Theta$. Few connectivity 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 may be asymmetric, i.e. vary among the different directions.

In this work, we derive some new methods for determining zero and positive capacity. We generalize a technique for proving zero capacity, which is based on scanning a $\Theta$-constrained array whose labels are partially known, and counting the number of possible ways to label the rest of the array. This method provides an upper bound for the number of constrained arrays of size $n \times m$, which is small enough to determine that $C(\Theta)=0$.

For proving positive capacity of some constraints, we define shapes which can tile the plane. Given such a shape, we find two different valid ways to label it. We then show that tiling the plane with copies of the shape, where each copy can have either one of the two labels, results in a $\Theta$-constrained array. This provides a lower bound for the number of constrained arrays of size $n \times m$, which is large enough to determine that $C(\Theta)>0$.

We apply the above methods to the different connectivity models in order to characterize their zero/positive capacity regions. We consider asymmetric constraints in the diamond model, and provide an almost complete characterization of the positive capacity region.

In the triangular model, we show that $C(d,d+3)=0$ for every $d \geq 3$. For $d \equiv 1(mod~4)$, $d \geq 5$, we show a tight characterization: $C(d,k)>0$ if and only if $k \geq d+4$. Together with the former result, it implies that for other values of $d$, the gaps between the known zero and positive capacity regions are relatively small.

Finally, in the square model we show that $C(d,d+3)=0$ for every $d\geq 1$.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2006
To the main CS technical reports page

Computer science department, Technion