Given anmtimesnarray andkdistinct colors with 2lesmlesnand 2leskmn, we consider the problem of marking each location in the array using one of thekgiven colors such that any two locations in the array marked by the same color are separated as much as possible. This problem is related to two-dimensional (2-D) interleaving schemes for correcting cluster errors where the goal is to rearrange the codeword symbols so that an arbitrarily shaped error cluster of sizetcan be corrected for the largest possible value oft. In a recent paper, the authors have shown that, for the case 2lesklesmn/2, the maximum coloring distance is given by lfloorradic2krfloor ifkleslceilm2/2rceil, and bym+lfloor(k-lceilm2/2rceil)/mrfloor if lceilm2/2rceillesklesmn/2. In this work, we extend these results to the casemn/2kmn. We show that in such cases, the maximum coloring distance is given by tom+lfloor(k-lceilm2/2rceil)/mrfloor ifmn/2kmn-lfloorm2/2rfloor, and bym+n-lceilradic2(mn-k)rceil ifmn-lfloorm2/2rfloorleskmn. In particular, we generalize the partial sphere packing argument to derive the new bound and consequently propose a new type of construction achieving optimal coloring for the casekgesmn-lceilm2/2rceil.

Given an mtimesn 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 t can be corrected for the largest possible value of t. We show that for all such mtimesn arrays, the maximum possible interleaving distance, or equivalently, the largest value of t such that an arbitrary error burst of size up to t can be corrected, is bounded by lfloorradic2krfloor if kleslceil(min{m,n})2/2rceil, and by min{m,n}+lfloor(k-lceil(min{m,n})2/2rceil)/min{m,n}rfloor if kgeslceil(min{m,n})2/2rceil. 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

One of the key problems in the study of optimal interleaving schemes for correcting two-dimensional (2-D) cluster errors is how to place, say, n distinct symbols, each appearing m times, in an m/spl times/n array such that the resulting array has the maximum possible burst error-correcting power. In a previous paper, the authors have proved that for any given m, n, the maximum possible interleaving distance, and hence, the largest possible value t such that an arbitrary error burst of size t can be corrected in an m/spl times/n interleaved array, is given by t=/spl lfloor//spl radic/2n/spl rfloor/ for n = /spl les/ /spl lceil/m/sup 2//2/spl rceil/, and t=m+/spl lfloor/(n-/spl lceil/m/sup 2//2/spl rceil/)/m/spl rfloor/ for n /spl ges/ /spl lceil/m/sup 2//2/spl rceil/. In this work, we extend these results and show that for all m, n with n /spl ges/ m, an optimal m/spl times/n interleaving array can always be obtained by a Latin rectangle in which each row and each column contains each symbol at most once. This provides additional error-correcting power to the array in that all linear error bursts occupying a whole row or column can also be corrected.

Given an m/spl times/n array of n single-random-error-correcting codewords of length m, we present optimal interleaving schemes that achieve maximum possible interleaving distance t =/spl lfloor//spl radic/2n/spl rfloor/ for n/spl les//spl lceil/m/sup 2//2/spl rceil/, and t = m+/spl lfloor/(n-/spl lceil/m/sup 2//2/spl rceil/)/m/spl rfloor/ for n/spl ges//spl lceil/m/sup 2//2/spl rceil/. These interleaving schemes provide maximum burst error-correcting power without requiring prior knowledge of the size or shape of an error burst.