Basis arrays and successive packing for M-D interleaving

In this paper, we first present a novel concept of 2-D basis interleaving array (also referred to as basis array for short). That is, an m × m interleaved array is said to be a basis array if the shortest distance among all pairs of elements in each of the so-called m-equivalent sets within the m × m array reaches the maximum. It is shown that this maximum is given by ⌊2m⌋ and an m × m basis array can be constructed by using a simple cyclic translation method. The previously developed concept of successive packing is then generalized in the sense that it can be applied to any basis array to generate an interleaved array with a larger size. Except that optimality cannot be guaranteed, the concept of basis arrays and successive packing are extended to M-D cases. It is shown that for any M ≥ 2, the proposed technique can spread any error burst of block size m^k ₁ × m^k₂ ⋯ × m ^k_m within an mⁿ₁ × m ⁿ₂ × ⋯ × mⁿ_m array (1 ≤ k ≤ n - 1) so effectively that the error burst can be corrected with some simple random error-correcting code (provided the error-correcting code is available). It is shown that important prior results in M-D interleaving such as the t-interleaved array based approach by Blaum et al. and the successive packing approach by Shi and Zhang now become special cases of the framework based on basis arrays and successive packing, proposed in this paper.