HP Labs Technical Reports

Location-Correcting Codes

Roth, Ron M.; Seroussi, Gadiel

HPL-95-20

Keyword(s):

Abstract: We study codes over GF(q) that can correct t channel errors assuming the error values are known. This is a counterpart to the well-known problem of erasure correction, where error values are found assuming the locations are known. The correction capabilities of these so called t-location correcting codes (t-LCCs) are characterized by a new metric, the decomposability distance, which plays a role analogous to that of the Hamming metric in conventional error-correcting codes (ECCs). Based on the new metric, we prove bounds on the parameters of t-LCCs that are counterparts to the classical Singleton, sphere packing and Gilbert-Varshamov bounds for ECCs. In particular, we show examples of perfect LCCs, and we study optimal (MDS-like) LCCs that attain the Singleton-type bound on the redundancy. We show that these optimal codes are generally much shorter than their erasure (or conventional ECC) analogues: The length n of any t-LCC that attains the Singleton-type bound for t > 1 is bounded from above by t + O(square root of q), compared to length q+1 which is attainable in the conventional ECC case. We show constructions of optimal t-LCCs for t epsilon {1,2,n-2,n-1,n} that attain the asymptotic length upper bounds, and constructions for other values of t that are optimal, yet their lengths fall short of the upper bounds. The resulting asymptotic gap remains an open research problem. All the constructions presented can be efficiently decoded.

Back to Index