Optimal Interleaving Schemes for Two-Dimensional Arrays.

Given an m × n array of k single random error correction (or erasure) codewords, each having length l such that mn = kl, we construct optimal interleaving schemes that provide the maximum burst error correction power such that an arbitrarily shaped error burst of size can be corrected for the largest possible value of t. We show that for all such m × n arrays, the maximum possible interleaving distance, or equivalently, the largest value oft such that an arbitrary error burst of size up tot can be corrected, is bounded by └√2k┘ if k ≤, ┌(min{m, n})²/2┐, and by min{m, n} + └(k - ┌(min{m, n})²/2┐)/min{m, n}┘ if k ≥ ┌(min{m, n} )²/2]. We generalize the cyclic shifting algorithm developed by the authors in a previous paper and construct, in several special cases, optimal interleaving arrays achieving these upper bounds. Additionally, for codewords of variable lengths, we solve a related array coloring problem for which the same upper bounds hold and can be achieved. [ABSTRACT FROM AUTHOR]