A Caltech Library Service

Interleaving schemes for multidimensional cluster errors

Blaum, Mario and Bruck, Jehoshua and Vardy, Alexander (1998) Interleaving schemes for multidimensional cluster errors. IEEE Transactions on Information Theory, 44 (2). pp. 730-743. ISSN 0018-9448. doi:10.1109/18.661516.

See Usage Policy.


Use this Persistent URL to link to this item:


We present two-dimensional and three-dimensional interleaving techniques for correcting two- and three-dimensional bursts (or clusters) of errors, where a cluster of errors is characterized by its area or volume. Correction of multidimensional error clusters is required in holographic storage, an emerging application of considerable importance. Our main contribution is the construction of efficient two-dimensional and three-dimensional interleaving schemes. The proposed schemes are based on t-interleaved arrays of integers, defined by the property that every connected component of area or volume t consists of distinct integers. In the two-dimensional case, our constructions are optimal: they have the lowest possible interleaving degree. That is, the resulting t-interleaved arrays contain the smallest possible number of distinct integers, hence minimizing the number of codewords required in an interleaving scheme. In general, we observe that the interleaving problem can be interpreted as a graph-coloring problem, and introduce the useful special class of lattice interleavers. We employ a result of Minkowski, dating back to 1904, to establish both upper and lower bounds on the interleaving degree of lattice interleavers in three dimensions. For the case t≡0 mod 6, the upper and lower bounds coincide, and the Minkowski lattice directly yields an optimal lattice interleaver. For t≠0 mod 6, we construct efficient lattice interleavers using approximations of the Minkowski lattice.

Item Type:Article
Related URLs:
URLURL TypeDescription
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© Copyright 1998 IEEE. Reprinted with permission. Manuscript received August 30, 1995; revised July 24, 1997. The work of J. Bruck was supported by the NSF Young Investigator Award CCR-9457811, by the Sloan Research Fellowship, and by DARPA and BMDO through an agreement with NASA/OSAT. The work of A. Vardy was supported by the David and Lucile Packard Foundation Fellowship, by the National Science Foundation CAREER Award NCR-9501345, and by the JSEP under Grant N00014–9610129. The material in this paper was presented in part at the IEEE International Symposium on Information Theory, Ulm, Germany, June 1997. A. Vardy would like to acknowledge discussions with H. Edelsbrunner and D.B. West. He is also grateful to Hagit Itzkowitz for her invaluable help.
Subject Keywords:Bursts, chromatic number, clusters, error-correcting codes, lattices, L1-distance, multidimensional interleaving, power graphs of Z^3
Issue or Number:2
Record Number:CaltechAUTHORS:BLAieeetit98
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:9160
Deposited By: Archive Administrator
Deposited On:04 Nov 2007
Last Modified:08 Nov 2021 20:56

Repository Staff Only: item control page