2024/03/12 by Singhvi, Shubhransh, Con, Roni, Kiah, Han Mao +1
#FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2403.07754
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 each corrupted by at most t 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 O(nN) field operations, where n is the codeword length.