Motivation
Interpolation repairs missing values because their locations are known. With unknown errors, selecting an arbitrary set of interpolation points may select corrupted values and recover the wrong polynomial. Trying every possible error-location set is finite, but can require far too many trials. The useful observation is that a polynomial can vanish at every corrupted location, making those equations harmless without knowing the locations in advance.
At first this seems to introduce a nonlinear problem: the unknown message polynomial must be multiplied by an unknown error-locator polynomial. Instead, introduce their product as a new independent unknown. The received values are already known scalars, so the resulting equations are linear. We will prove why their solutions recover a polynomial quotient under the decoding promise, and why divisibility must be checked when that promise is absent.
We use the field root bound and distance calculation of the evaluation-code chapter. The argument counts field operations; practical bit complexity also depends on how the finite field and its arithmetic are represented.
Definitions
Fix a field , distinct points , and integers , satisfying . Codewords evaluate polynomials of degree less than . Let be the received word. A candidate message polynomial is within budget if it disagrees with in at most coordinates. A zero polynomial has degree for degree-bound statements.
Seek polynomials
satisfying
The polynomial is the error locator, chosen monic of degree exactly . For , it is the fixed polynomial one. The equations are linear in the lower coefficients of and the coefficients of : the factors are data, not unknowns. There are unknown coefficients and equations.
Monicity prevents the vacuous pair , which would satisfy the equations for every received word while conveying no message. Fixing the leading coefficient to one also removes scalar ambiguity. If fewer than errors occurred, need not be the polynomial with exactly those error locations as simple roots; extra factors are allowed.
Write the actual coefficient rows
Write . Moving the unknown lower locator terms to the left gives one row for each received coordinate:
Every entry of this coefficient matrix is known once the evaluation points and received values are known. No product of two unknown coefficients occurs. The unknown product has been replaced by the independent coefficient list of ; divisibility later checks that this replacement really came from a message polynomial. This is the step that makes ordinary linear algebra applicable.
Concept lensAlgebraic
The equations as one polynomial congruence
Let and let be the interpolating polynomial of degree less than with . The equations say exactly that vanishes at all points, that is,
Since , the polynomial is the remainder of modulo . Decoding asks for a monic of degree for which that remainder has degree less than .
A zero evaluation point causes no difficulty. When , its row reduces to . We never divide by the evaluation point. When , the second sum is empty and the row is simply , because the constant monomial evaluates to one, including at zero. These conventions make the boundary cases ordinary instances of the same system rather than special numerical exceptions.
The system may have more equations than unknowns, or dependent equations. Gaussian elimination must therefore handle inconsistency and free variables, not merely invert a presumed square nonsingular matrix. The later correctness proof deliberately allows all of these possibilities. A received codeword with an unused error budget is a natural source of free locator coefficients; it is not an exceptional input that should be rejected merely because the matrix has deficient rank.
Theorem/proposition
Theorem 16.2.1
(Every solution has the same message quotient under the promise)
Suppose a polynomial of degree less than disagrees with in at most positions. The linear system has a solution with monic of degree . Every such solution satisfies . Thus its quotient is the same , even when the linear system has several solutions.
Theorem 16.2.2
(A polynomial-time unique decoder with a checked output)
Solve the linear system. If it is inconsistent, report that no codeword lies within budget. Otherwise take any solution, divide by , and accept its quotient only if the remainder is zero, the quotient has degree less than , and its evaluations disagree with at at most positions. If a check fails, report no codeword within budget. For this procedure is correct on every received word and uses polynomially many field operations.
Proof sketch or proof idea
Proof
(A padded true locator, and a root count)
A promised message supplies a solution. Let be the set of incorrect positions for , and write . Define
The padding factor makes monic of degree exactly . It may introduce repeated roots or zeros at correct positions, which are allowed. The product has degree less than . At a correct position, . At an incorrect position, both sides are zero because . Hence this is a solution. No claim that the receiver can construct it without decoding is being used; it proves that the linear system is consistent whenever the promised message exists.
An arbitrary solution has the right quotient. Take any solution with the specified degree and monicity, and compare it with the actual . The polynomial has degree at most . At every correct position,
There are at least such distinct points. The root bound therefore forces . Since , exact polynomial division gives quotient and zero remainder. This argument does not require unique locator coefficients, nonzero received values or knowledge of the corrupted indices.
Proof X-ray
The equation count is not the correctness proof
There are at least as many equations as unknowns, but that observation alone proves neither consistency nor a correct quotient. Consistency comes from the padded true locator. Correctness comes from the roots of at all correct positions. The inequality appears in that root count, where it has a mathematical purpose beyond the dimensions of a matrix.
The decoder of the second theorem adds a rejection rule and a cost bound to this argument.
Proof
(Uniqueness within the radius, and the cost)
Rejection is justified. The evaluation code has distance , so two different message polynomials cannot both be within budget. If one exists, the first theorem shows that the system is consistent and that every solution passes the quotient and distance checks with that message. Therefore inconsistency or a failed check implies that no such candidate exists. Conversely, an accepted quotient is explicitly verified to be a valid degree-bounded polynomial within budget, so accepting cannot invent an invalid candidate.
This explains why “take any solution” is legitimate. We do not have to search the solution space for a lucky locator. If the data are decodable within the budget, all solutions give the same quotient; if they are not, none can pass the final candidate check. A nonzero remainder is a meaningful rejection result, not a failure of the decoding theorem.
Cost. Gaussian elimination solves a system with equations and at most unknowns in field operations using an elementary implementation. Writing powers, dividing polynomials of degree , evaluating the quotient and counting disagreements also take polynomially many operations. A free-variable solution can be chosen directly when the matrix is singular; uniqueness of the unknown coefficient vector is unnecessary. These bounds do not include an unspecified cost for a field operation. With an explicit efficient field representation those operations must in turn be implemented and counted in bits; the algebraic proof itself does not certify a particular software implementation.
Worked examples
Worked example 16.2.3
(Decode one corrupted evaluation over the field of seven elements)
Use points , dimension and budget . Receive . Write and . The equations have the form
Row reduction gives and . To check this solution directly, takes values and takes values at the five points; the products give the same list.
Divide by . The first quotient term leaves remainder ; the next term leaves ; the final term leaves zero. The quotient is . Its word is , differing only at the third coordinate. The locator root is the evaluation point , not the ordinal label “second coordinate.”
Worked example 16.2.4
(A smaller budget is a different promise)
Over , use points and . The word for is . If the received word is and the budget is zero, then and the system asks for a linear polynomial agreeing at all four positions. Values at zero and two already force , whose value at one is three, so the system is inconsistent. This does not contradict one-error correction: that run asked for zero errors.
With budget one, and a valid solution is , modulo five. Exact division recovers the message. The chosen budget determines the linear system and the claim its failure can establish.
Worked example 16.2.5
(Extra locator factors do not create extra messages)
Use all seven points of , and budget two. Suppose the received word has no errors and equals the evaluations of . Both with and with solve the system. Their coefficient vectors differ, yet their quotients are the same . The first locator even vanishes at a correct point. Its roots cannot be interpreted as an exact list of actual errors when the error budget has slack.
Common mistake
(Reading error values from the locator)
After recovering the message, the actual error value at position is . Locator coefficients do not directly encode those values. In the first example the corrupt position is the field point , and the error value is ; the locator's constant coefficient is . Confusing those three numbers would mix a coordinate label, an error magnitude and a polynomial coefficient. The linear system uses the received symbols as data, but its locator records where multiplication should suppress an equation.
Common mistakes
Counterexample mode
A rational fit need not be a polynomial message
Over at points , take and received values . The pair , satisfies every equation: each is the inverse of . But does not divide .
There is no quadratic message within one error. If one agreed at four points, would have degree at most three and four distinct roots, so it would be zero. Evaluating that identity at gives , impossible in the field. The linear system can therefore be consistent on nondecodable data; division is an essential check.
Common mistake
(Raising the budget past the unique-decoding radius)
The radius condition cannot simply be removed. For the five-point dimension-three code, the polynomial has word . The received word is within one error of the zero word and two errors of that nonzero word. A budget of would admit both messages, so no decoder can uniformly identify which was transmitted. This is a limitation of the information, not a defect of Gaussian elimination.
With erasures, delete the erased coordinates and run the same algorithm on the remaining distinct evaluation points. If symbols are erased and at most remaining values are wrong, the condition is , equivalently . One must count the errors among the surviving positions; an erased position is not simultaneously charged as an unknown error in this convention.
Summary
A locator makes bad evaluation equations vanish, and a product variable turns the problem into linear algebra. A root-count argument proves that every solution has the correct quotient within the unique-decoding radius. Exact division and candidate checks distinguish genuine message polynomials from spurious rational fits, including on inputs that violate the error promise.
Exercises
Quick check
(For , , what is the largest integer error budget covered without erasures? What if two positions are erased?)
Use , then .
Solution · Answer
Without erasures, allows . With two erasures, ten evaluations remain, so allows at most two unknown errors. The mixed inequality gives the same answer, .
Quick check
(Why is choosing , unacceptable, even though it satisfies the interpolation equations?)
Ask what the pair says about the received word.
Solution
It would make every received vector appear to satisfy the equations while division by is undefined. The monic leading coefficient fixes a nonzero degree- locator and makes the remaining equations inhomogeneous linear constraints.
Quick check
(In the first worked example, verify the system equation at point by computing , and modulo .)
Solution · Answer
. The integer value of is , hence . Also . This checks that one row of the system is satisfied; all rows are needed for a solution.
Quick check
(Suppose two monic locator solutions under the promise have different extra factors. Prove their quotients still agree without assuming the linear system has full rank.)
Apply the root count to for each solution separately.
Solution
Each pair satisfies by the same correct-position root count. Its nonzero therefore divides with quotient . The argument identifies the quotient, not the free locator factors, so a rank-deficient coefficient system causes no ambiguity in the message.