Error-Correction of Multidimensional Bursts
Tuvi Etzion, Eitan Yaakobi · IEEE Transactions on Information Theory · 2009
We present several methods and constructions to generate binary codes for correction of a multidimensional cluster- error, whose shape can be a box-error, a Lee sphere error, or an error with an arbitrary shape. Our codes have very low redundancy, close to optimal, and a large range of parameters of arrays and clusters. Our main results are summarized as follows. 1) A construction of two-dimensional codes capable to correct a rectangular-error with considerably more flexible parameters from previously known constructions. This construction is easily generalized for D dimensions. 2) A novel method based on D colorings of the D -dimensional space for constructing D -dimensional codes correcting a D -dimensional cluster-error of various shapes. 3) A transformation of the D -dimensional space into another D -dimensional space in a way that a D -dimensional Lee sphere is transformed into a shape located in a D-dimensional box of a relatively small size. 4) Applying the coloring method to correct more efficiently a two-dimensional error whose shape is a Lee sphere. 5) A construction of D -dimensional codes capable to correct a D -dimensional cluster-error of size b in which the number of erroneous positions is relatively small compared to b. 6) We present a code which corrects a D -dimensional arbitrary cluster-error with relatively small redundancy.