Summary
Reed-Solomon codes are a type of error-correcting code that help computers and devices fix mistakes in data transmission. The paper shows a new way to decode these codes faster and more reliably when lots of errors happen. The method works for all sets used to create the codes and keeps the decoding efficient even when trying to correct many errors. The authors' algorithm runs in a reasonable time and gets close to the best possible performance these codes can have.
Reed-Solomon codeslist decodingerror correctionprime fieldspolynomial-time algorithmcapacityevaluation setconstant ratedecoding limit
Authors
Joshua Brakensiek, Yeyuan Chen, Aaron Putterman, Zihan Zhang, Kai Zhe Zheng
Abstract
We give a deterministic polynomial-time list-decoding algorithm for Reed-Solomon codes over prime fields that approaches list-decoding capacity for every evaluation set and every constant rate.