Optimal interleaving schemes for correcting two-dimensional cluster errors

We present an elementary theory of optimal interleaving schemes for correcting cluster errors in two-dimensional digital data. It is assumed that each data page contains a fixed number of, say n, codewords with each codeword consisting of m   code symbols and capable of correcting a single random error (or erasure). The goal is to interleave the codewords in the m×nm×n array such that different symbols from each codeword are separated as much as possible, and consequently, an arbitrary error burst with size up to t can be corrected for the largest possible value of t. We show that, for any given m, n, the maximum possible interleaving distance  , or equivalently, the largest size of correctable error bursts in an m×nm×n array, is given by t=⌊2n⌋ if n⩽⌈m2/2⌉n⩽⌈m2/2⌉, and t=m+⌊(n-⌈m2/2⌉)/m⌋t=m+⌊(n-⌈m2/2⌉)/m⌋ if n⩾⌈m2/2⌉n⩾⌈m2/2⌉. Furthermore, we develop a simple cyclic shifting algorithm   that can provide a systematic construction of an m×nm×n optimal interleaving array for arbitrary m and n. This extends important earlier work on the complementary problem of constructing interleaving arrays that, given the burst size t, minimize the interleaving degree, that is, the number of different codewords in a 2-D (or 3-D) array such that any error burst with given size t can be corrected. Our interleaving scheme thus provides the maximum burst error correcting power without requiring prior knowledge of the size or shape of an error burst.