M.Sc Thesis

M.Sc StudentYaakobi Eitan
SubjectCodes for Correcting Multi-Dimensional Bursts
DepartmentDepartment of Computer Science
Supervisor PROF. Tuvi Etzion
Full Thesis textFull thesis text - English Version


In current memory devices for advanced storage systems the information is stored in two or more dimensions. In such systems errors usually take the form of multidimensional bursts. Typically, a cluster of errors will either be affected by the position in which the error event occurred or will be of arbitrary shape. But, since an arbitrary cluster-error is hard to correct efficiently it is common to assume some type of cluster-error, e.g., rectangles or Lee spheres in two dimensions. We will consider these types of errors as well as arbitrary ones. In this work, we survey some of the known constructions for correcting one and two-dimensional bursts. Our point of departure is the construction presented by Breitbach, Bossert, Zybalov, and Sidorenko for correcting bursts of size b1×b2. We improve this construction and generalize it to higher dimensions. This generalization results in a construction for D-dimensional binary codes correcting a single D-dimensional box error of odd volume size. We present a novel method for correction of D-dimensional bursts. The construction uses D colorings of the D-dimensional space. This construction is a generalization of the previous one, and enables us to handle different burst patterns. We use this construction to handle D-dimensional box errors, where the volume of the box is an even integer. We discuss correction of D-dimensional Lee sphere cluster errors. Two types of constructions are explored. The first uses a transformation between two D-Dimensional spaces such that each Lee sphere is transformed into a shape bound by a reasonably small D-Dimensional box. Consequently, we can utilize the constructions of the previous sections. The second construction uses colorings as described above. For two-dimensional binary arrays of size n × n we present a code for correcting Lee sphere errors with radius R. We show how to handle bursts of size b, where the number of erroneous positions is limited. We present constructions for binary and non-binary alphabets, and for one-dimensional and D-dimensional arrays. These constructions are combined with the construction for correcting Lee sphere errors in order to correct arbitrary bursts for two and multi dimensions.