Optimal 2-D Interleaving With Latin Rectangles
Wenliang Xu, Solomon W. Golomb · IEEE Transactions on Information Theory · 2005
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.