Location-correcting codes

We study linear 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. We prove a Singleton-type bound on the redundancy of any t-location-correcting code (t-LCC) of length >t. Furthermore, using sphere-packing arguments, we prove a lower bound of [t/2](log_q(q-1)+2log_q(n/t)) on the redundancy of any t-LCC. This, in turn, implies an upper bound of O(√q) on the length of any t-LCC that attains the Singleton-type bound whenever 2⩽t≪q. We show optimal constructions of t-LCCs for t∈{1,2,n-2,n-1,n}, and constructions for other values of t that attain minimal redundancy but fall short of the asymptotic length upper bound