Editing Reed–Solomon error correction (section)

=== Theoretical decoder ===

Reed and Solomon described a theoretical decoder that corrected errors by finding the most popular message polynomial.<ref name="ReedSolomon"/> The decoder only knows the set of values <math>a_1</math> to <math>a_n</math> and which encoding method was used to generate the codeword's sequence of values. The original message, the polynomial, and any errors are unknown. A decoding procedure could use a method like Lagrange interpolation on various subsets of n codeword values taken k at a time to repeatedly produce potential polynomials, until a sufficient number of matching polynomials are produced to reasonably eliminate any errors in the received codeword. Once a polynomial is determined, then any errors in the codeword can be corrected, by recalculating the corresponding codeword values. Unfortunately, in all but the simplest of cases, there are too many subsets, so the algorithm is impractical. The number of subsets is the [[binomial coefficient]], <math display="inline"> \binom{n}{k} = {n! \over (n-k)! k!}</math>, and the number of subsets is infeasible for even modest codes. For a {{math|(255,249)}} code that can correct 3 errors, the naïve theoretical decoder would examine 359 billion subsets.{{citation needed|date=March 2025}} <!-- = 255 * 254 * 253 * 252 * 251 * 250 / 720 rounded down; could say 360B -->