MDS Array Codes for Correcting Criss-Cross Errors
Mario Blaum, Jehoshua Bruck · 1997
We present a family of MDS array codes of size (p \\Gamma 1) \\Theta (p \\Gamma 1), p a prime number, and minimum criss-cross distance 3, i.e., the code is capable of correcting any row or column in error, without apriori knowledge of what type of error occurred. The complexity of the encoding and decoding algorithms is lower than that of known codes with the same error-correcting power, since our algorithms are based on exclusiveOR operations over lines of different slopes, as opposed to algebraic operations over a finite field. We also provide efficient encoding and decoding algorithms for errors and erasures. Supported in part by the NSF Young Investigator Award CCR-9457811 and by the Sloan Research Fellowship. 1 Introduction In this paper we describe 2-dimensional array codes that can correct errors given by either a row or a column in error (without apriori knowledge of which one occurred). There exist codes that can do so. Moreover, the known codes are stronger in the sense tha...