A general decoding technique applicable to replicated file disagreement location and concatenated code decoding
John J. Metzner, E.J. Kapturowski · IEEE Transactions on Information Theory · 1990
Code symbols are treated as vectors in an r-dimensional vector space F/sup r/ over a field F. Given any (n, k) linear block code over F with minimum distance d, it is possible to derive an (n, k) code with symbols over F/sup r/, also with minimum distance d, which can correct any pattern of d-2 or fewer symbol errors for which the symbol errors as vectors are linearly independent. This is about twice the bound on the number of errors guaranteed to be correctable. Furthermore, if the error vectors are linearly dependent and d-2 or fewer in number, the existence of dependence can always be detected. A decoding techinque is described for which complexity increases no greater than as n/sup 3/, for any choice of code. For the two applications considered, situations are described where the probability of the error patterns being linearly dependent decreases exponentially with r.>