Optimal 2-D interleaving with latin rectangles

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×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×n interleaved array, is given by t=└√2n┘ for n = ≤ ┌m²/2┐, and t=m+└(n-┌m²/2┐)/m┘ for n ≥ ┌m²/2┐. In this work, we extend these results and show that for all m, n with n ≥ m, an optimal m×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.