Ph.D Thesis
Ph.D Student Tal Ido Coding and Bounds for Two-Dimensional Constraints Department of Computer Science Professor Ronny Roth Professor Tuvi Etzion

Abstract

Many mass-storage devices have related inputs which have a relatively high probability of being misread. One gets around this problem by allowing only a subset of ‘good’ inputs to be written on the device. The subset of ‘good’ inputs is termed a constrained system, or a constraint.

A one-dimensional (1-D) constraint deals with inputs that are words. The capacity of the constraint is an easily calculated number. Moreover, the state-splitting algorithm gives a very general and practical method for building an encoding/decoding pair for the constraint. If we assume a noiseless case, then the performance of the encoder/decoder pair can be made arbitrarily close to the capacity of the constraint.

A two-dimensional (2-D) constraint deals with allowable two-dimensional arrays, as opposed to the 1-D words. In contrast with 1-D constraints, 2-D constraints are much less understood. There is no known 2-D counterpart of the state-splitting algorithm, and there is an inherent difficulty in calculating the capacity of a general 2-D constraint.

Our first result is a fixed-rate encoder/decoder pair for a fairly large family of 2-D constraints. Encoding and decoding is done in a row-by-row manner, and is sliding-block decodable. Essentially, the 2-D constraint is turned into a set of independent and relatively simple 1-D constraints. The maxentropic stationary Markov chain of the corresponding graph is next considered: a perturbed version of the corresponding probability distribution on the edges of the graph is used in order to build an encoder. This perturbation is found by means of a network flow.

Our second result is a method for bounding the rate of a given bit-stuffing encoder for a 2-D constraint. Instead of considering the original encoder, we consider a related one which is quasi-stationary. We then formulate linear requirements that must hold on the probabilities of the constrained arrays that are generated by the encoder. These requirements are used as part of a linear program. The minimum and maximum of the linear program bound the rate of the encoder from below and from above, respectively.

The capacity of 1-D constraints is given by the entropy of a corresponding stationary maxentropic Markov chain. In our third result, we try to extend certain aspects of this characterization to 2-D constraints. The result is a method for calculating an upper bound on the capacity of 2-D constraints. The bound is the value of a concave program, which can be easily solved numerically.