THE ERROR LOCATOR a polynomial whose roots are exactly the positions that went wrong
When more than one symbol is corrupted, a single syndrome is not enough — you need the error-locator polynomial. Its defining trick: build a polynomial σ(x) whose roots mark the error positions. Find the roots (a Chien search tries every position) and you have located every error at once; a second step recovers their magnitudes. This is the heart of Reed–Solomon and BCH decoding — the reason a QR code survives a coffee stain and a hard drive shrugs off a bad sector. The positions are not stored; they are reconstructed as the zeros of a polynomial the syndromes determine. The structure — roots encode locations — is what turns a search into an evaluation.
THE TECHNIQUE σ(x) with roots at the error positions; a Chien search finds them
An error-locator polynomial σ(x) = x² − 5x + 6 (roots at 2 and 3). The demo runs a Chien search — evaluate at each position, a zero is an error: live demo
HISTORY & CREDIT Peterson 1960 · Chien 1964
“Finding several errors means checking every combination.” — the locator polynomial packs all positions into its roots; one pass of evaluations finds them together. A combinatorial search becomes a polynomial's zeros. cited
1960 · W. Wesley Peterson — the error-locator polynomial for BCH codes. 1964–68 · Robert Chien (root search) and Berlekamp–Massey (building σ from syndromes). now · the decoding core of Reed–Solomon: QR codes, DVDs, deep-space, storage.
Pack the error positions into the roots of one polynomial, then evaluate your way to them. Locations recovered as zeros — structure turning a search into arithmetic. Peterson-Chien
RECOMMEND FOR I-13 error positions found as polynomial roots, computed
On the canonical compiler, a Chien search over σ(x)=x²−5x+6 finds its first root at position 2 (the other at 3) — the error locations:
$ i13 run rec_errorlocator.i13 # Chien search for sigma's roots
first_error_pos = 2 -- sigma(2)=0 -> an error at position 2 (the other root, 3)
Recommend: the error locator is reconstruction of where from the structure of a polynomial. i13 runs the Chien search — evaluate σ(x)=x²−5x+6 at each position by recursion — and finds the root at 2, an error location, without trying combinations. The positions are recoverable only because they were encoded as the roots: the structure is that σ(p)=0 ⇔ position p is in error. i13 enacts the evaluation; the locator polynomial's design is what makes the answer readable. It pairs with syndrome decoding (dart 299): the syndrome says something is wrong, the locator says exactly where.