New Array Codes for Multiple Phased Burst Correction

A new optimal family of array codes over GF(q) for correcting multiple phased burst errors and erasures, where each phased burst corresponds to an erroneous or erased column in a code array, is presented. As for erasures, these array codes have an efficient decoding algorithm which avoids multiplications (or divisions) over extension fields, replacing these operations with cyclic shifts of vectors over GF(q). The erasure decoding algorithm can be adapted easily to handle, in addition, single column errors as well. The new array codes are characterized geometrically by means of parity constraints along certain diagonal lines in each code array, thus generalizing a previously known construction for the special case of two erasures. Algebraically, these array codes can be interpreted as Reed-Solomon codes over the ring of polynomials over GF(q) modulo 1 + x +. + x^p-2+ x^p-1 for some prime p, which is not the characteristic of GF(q). When q is primitive in GF(q), the resulting codes become (conventional) Reed-Solomon codes of length p over GF(q^p-1), in which case the new erasure decoding technique can be incorporated into the Berlekamp-Massey algorithm, yielding a faster way to compute the values of any prescribed number of errors. © 1993 IEEE