M.Sc Thesis | |

M.Sc Student | Yaakobi Eitan |
---|---|

Subject | Codes for Correcting Multi-Dimensional Bursts |

Department | Department of Computer Science |

Supervisor | PROF. Tuvi Etzion |

Full Thesis text |

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 *b*_{1}×*b*_{2}.
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.