Technical Report CS0954

Title: Two-Dimensional Interleaving Schemes with Repetitions: Bounds and Constructions
Authors: Tuvi Etzion and Alexander Vardy
PDFNot Available
Abstract: Two-dimensional interleaving schemes with repetitions are used for correcting two-dimensional burst (or clusters) of errors, where a cluster of errors is characterize by its area. Correction of two-dimensional error clusters is required in holographic storage, an emerging application of considerable interest. We consider interleaving schemes with multiple repetitions. The proposed interleaving schemes are based on $t$-interleaved arrays of integers defined by the property that in every connected component of area $t$, each integer appears a given limited number of times,depending on the number of allowed repetitions. The total number of integers is the interleaving degree. The constructions we present are based on lattices and the interleaving schemes, for two or three repetitions, are shown to be either optimal or asymptotically optimal among all the interleaving schemes which are based on lattices. Lower bounds on the interleaving degree for two repetitions are also presented. We consider two different models. In the first model, two elements are connected if the adjacent either horizontally or vertically. In the second model, they are also connected if they are adjacent diagonally. We show tight connections between the two models. Finally, we present a list of open problems and conjectures which have a considerable interest in interleaving techniques for correction of multidimensional error clusters.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1999
To the main CS technical reports page

Computer science department, Technion