On List Decoding of Generalized Reed–Solomon Codes Under Partial Codeword Knowledge

Abstract:
List decoding of generalized Reed–Solomon codes is considered under the prerequisite that the transmitted codeword is partially known to the receiver. It is shown that this turns the standard noisy interpolation problem associated with the Guruswami–Sudan list decoder into a partially noisy and partially noise-free interpolation problem, which results in an improved error-correcting radius. It is further shown that the computational complexity of this approach is comparable to traditional bounded minimum distance decoding and that the only price for the exploitation of partial codeword knowledge is list size larger than one. In practice, partial codeword knowledge is available in decoding concatenated constructions such as staircase codes.