Interleaving Schemes for Multidimensional Cluster Errors

We present 2 and 3-dimensional interleaving techniques for correcting 2 and 3- dimensional bursts (or clusters) of errors, where a cluster of errors is characterized by its area or volume. A recent application of correction of 2-dimensional clusters appeared in the context of holographic storage. Our main contribution is the construction of efficient 2 and 3-dimensional interleaving schemes. The schemes are based on arrays of integers with the property that every connected component of area or volume t consists of distinct integers (we call these t-interleaved arrays). In the 2-dimensional case, our constructions are optimal in the sense that they contain the smallest possible number of distinct integers, hence minimizing the number of codes required in an interleaving scheme.