Ph.D Thesis

Ph.D StudentSchwartz Moshe
SubjectTilings, Anticodes, and Multidimensional Coding
DepartmentDepartment of Computer Science
Supervisor PROF. Tuvi Etzion


We examine the 30 years old open question regarding the existence of perfect codes in the Johnson graph. We extend previous non-existence results. We present the first ever non-existence results which rule out codes by their radius. We then investigate the Grassman graph. We show that its vertices cannot be partitioned into optimal anticodes. We further examine properties of diameter perfect codes in the graph and their connection with Steiner systems.

We continue by considering multidimensional coding. Such codes use Zn to index their coordinates. Most current applications, such as memory chips, magnetic tapes and holographic memories, use Z2 and Z3. Several connectivity models define which pairs of points from Zn are neighbors. The errors we attempt to correct are those which occur within a connected set of t points in Zn.

We examine two-dimensional r-dispersion anticodes, in two variations on the rectangular grid, and in the hexagonal model. We classify all the optimal 3-dispersion anticodes and derive lower bounds on the interleaving degree of 3-dispersion interleaving schemes. We also provide lower bounds on the size of 3-dimensional 3-dispersion anticodes and two-dimensional 4-dispersion anticodes in the rectangular grid. We investigate two-dimensional 3-dispersion lattice interleavers. We provide tight lower bounds on the interleaving degree and show lattices which achieve the bounds.

We conclude with multidimensional coding without interleaving. We consider two-dimensional error-correcting codes capable of correcting unrestricted bursts. We provide optimal, or nearly optimal, 2-burst-correcting codes in all dimensions. We finish by improving the Reiger bound for two-dimensional unrestricted-burst-correcting linear codes.