M.Sc Student Sharov Artyom Coding Techniques for Multidimensional Constrained Channels Department of Computer Science Professor Ronny Roth Abstract

In this work we present a new variable-rate coding technique for 2-D constraints. The technique is based on tiling, namely, periodic partitioning of the 2-D plane into several classes of patterns (or tiles). We distinguish between different classes of tiles by tagging them with colors; the simplest scenario considered in this work deals with two classes of tiles: the white ones and the black ones. The tiles are chosen in a way that enables the encoder to first encode the contents of white tiles independently (that is, in a way that no assignment of contents to one white tile depends on the assignment of contents to another white tile), then to encode the black tiles depending only on the contents of the surrounding white tiles. The rate of such an encoder is easily calculated out of the contribution of the white tiles and the contribution of the black tiles. Moreover, the rate of the encoder yields a lower bound on the capacity of the corresponding constraint. For certain constraints, such as the 2-D (0, 2)-RLL and 2-D (3, )-RLL constraints, our technique is shown to improve on previously-known lower bounds on the capacity of the constraint. For certain constraints, such as the 3-D (1, )-RLL constraint, our technique gives rise to variable-rate encoders whose rates are higher than the rates of any previously-known efficient encoders for these constraints.

The generalizations and variations of the basic scenario include introducing an example where more tiles colors are necessary, introducing statistical dependence among white tiles (based on Markov chains and Pickard fields), and considering 3-D constraints. The work is concluded by defining a fixed-rate tiling-based encoder, attaining the rate of the variable-rate encoder for the corresponding constraint. For several constraints, such as the n.i.b. constraint or the 2-D (d, k)-RLL constraints for certain values of d and k, our fixed-rate encoder appears to improve on the rates of previously-known efficient fixed-rate encoders.