M.Sc Thesis | |

M.Sc Student | Censor Hillel Keren |
---|---|

Subject | Constrained Codes for Two-Dimensional Channels |

Department | Department of Computer Science |

Supervisor | PROF. Tuvi Etzion |

In digital data storage systems, such as magnetic and
optical storage devices, the physical structure of the media imposes
constraints on the recorded data. One of the most frequently investigated type
of constraints are the *(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 Ө is defined as:

*C*(Ө)=lim_{n}_{,m→∞}log_{2}*N*(*n*,*m*|Ө)/(*n*∙*m*),

where *N*(*n*,*m*|Ө) is the number of
arrays of size *n*%*m*
satisfying Ө. 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 Ө-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*%*m*,
which is small enough to determine that *C*(Ө)=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
Ө-constrained array. This provides a lower bound for the number of
constrained arrays of size *n*%*m*,
which is large enough to determine that *C*(Ө)>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*≥3. For *d*h1(mod4),
*d*≥5, we show a tight characterization: *C*(*d*,*k*)>0
if and only if *k*≥*d*+4. This 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*≥1.