| A one-dimensional binary sequence satisfies the (d, k) run length constraint if the number of consecutive 0s is at most k, and between any two 1s in the sequence are at least d 0s. An n-dimensional binary array satisfies the (d, k) run length constraint if the one-dimensional ( d, k) constraint is satisfied along every direction parallel to the coordinate axes. Other classes of constraints can also be defined. For example, a two-dimensional checkerboard constraint is a bounded measurable set S ⊂ R2 that contains the origin. A binary labeling of Z2 satisfies the checkerboard constraint S, if for every t ∈ Z2 that is labeled with 1, every other point of Z2 in S + t is labeled with 0s. Constrained codes are used in digital recording applications such as magnetic and optical data storage systems, where the constraints model certain physical properties of the recording device.; Every constraint reduces the average amount of information that can be stored per unit area. The average number of information bits that can be stored per position in a constrained code is upper bounded by the capacity associated with the constraint, and the capacity can be achieved asymptotically as the number of information bits grows. In this dissertation we investigate some problems related to two and higher dimensional (d, k) run length constrained codes, two-dimensional checkerboard codes, and a constrained code defined on a two-dimensional triangular grid. In each problem we determine the value of or bounds on the capacity associated with the given constraint, and also efficient encoding algorithms. |
