An Optimal Sequence Reconstruction Algorithm for Reed-Solomon Codes
Shubhransh Singhvi, Roni Con, Han Mao Kiah, Eitan Yaakobi · 2024
The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a scenario where the sender transmits a codeword from some codebook, and the receiver obtains$N$noisy outputs of the codeword. We study the problem of efficient reconstruction using$N$outputs that are corrupted by substitutions. Specifically, for the ubiquitous Reed-Solomon codes, we adapt the Koetter-Vardy soft-decoding algorithm, presenting a reconstruction algorithm capable of correcting beyond Johnson radius. Furthermore, the algorithm uses$\mathrm{O}(nN)$field operations, where$n$is the codeword length.