Technical Report CS0850

 TR#: CS0850 Class: CS Title: LOCATION-CORRECTING CODES. Authors: R.M. Roth and G. Seroussi PDF Not Available Abstract: We study codes over $GF(q)$ that can correct $t$ channel errors assuming the error {\em 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 {\em 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(\sqrt{q})$, compared to length $q+1$ which is attainable in the conventional ECC case. We show constructions of optimal $t$-LCCs for $t \in \{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. Copyright The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1995/CS/CS0850), rather than to the URL of the PDF files directly. The latter URLs may change without notice.