
HP Labs Technical Reports
Click here for full text:
LocationCorrecting Codes
Roth, Ron M.; Seroussi, Gadiel
HPL9520
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 wellknown problem of erasure correction, where error values are found assuming the locations are known. The correction capabilities of these so called tlocation correcting codes (tLCCs) are characterized by a new metric, the decomposability distance, which plays a role analogous to that of the Hamming metric in conventional errorcorrecting codes (ECCs). Based on the new metric, we prove bounds on the parameters of tLCCs that are counterparts to the classical Singleton, sphere packing and GilbertVarshamov bounds for ECCs. In particular, we show examples of perfect LCCs, and we study optimal (MDSlike) LCCs that attain the Singletontype 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 tLCC that attains the Singletontype 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 tLCCs for t epsilon {1,2,n2,n1,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
