A new two-dimensional interleaving technique using successive packing

Correction of two-dimensional (2-D) and three-dimensional (3-D) error bursts finds wide applications in secure data handling such as 2-D and 3-D magnetic and optical data storage, charged-coupled devices (CCDs), 2-D barcodes, and information hiding in digital images and video sequences, to name a few. In this paper, we present a new 2-D interleaving technique, called successive packing, to combat 2-D spot burst errors, which is potential to extend to multidimensional (M-D) interleaving. Square arrays of 2 ⁿ × 2 ⁿ are considered. It is shown that the proposed successive packing technique can spread any error burst of 2 ^k × 2 ^k (with 1≤k≤n-1), 2 ^k×2 ^k+1 (with 0≤k≤n-1), and 2 ^k+1×2 ^k (with 0≤k≤n-1) effectively so that the error burst can be corrected with some simple random-error-correction code (provided the error-correction code is available). It is further shown that the technique is optimal for combating all the above-mentioned error bursts in the sense that the interleaving degree reaches its lower bound. This implies that the algorithm needs to be implemented only once for a given 2-D array and is thereafter optimal for the set of error bursts having different sizes. A performance comparison between the proposed method and some existing techniques is given and the future research is discussed.