M.Sc Thesis

M.Sc StudentCensor Hillel Keren
SubjectConstrained Codes for Two-Dimensional Channels
DepartmentDepartment 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:


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 dh1(mod4), d≥5, we show a tight characterization: C(d,k)>0 if and only if kd+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.