Motivation
A minimum-distance theorem tells us that a nearby codeword is unique, but the receiver still needs to find it. Exhaustively comparing all messages can be expensive as codes grow. A syndrome instead removes the unknown transmitted word from the equations and retains only information about the error. For the binary length-fifteen BCH code, two extension-field syndromes determine a quadratic whose nonzero roots identify the altered positions.
The key simplification is specifically binary. A changed bit differs from the transmitted bit by one, so every error contributes its location with the same coefficient. We can express the sum and product of at most two location elements using their first and third power sums. The quadratic then records the unknown locations without requiring a search over all messages.
We derive the complete algorithm, including the no-error branch, a single error, rejected syndromes and verification of the candidate. Its guarantee concerns at most two bit errors. A decoder can output a plausible but incorrect message outside that radius, even if every algebraic check passes. Understanding that limitation is part of understanding the algorithm.
Definitions
Use the field and the order-fifteen element constructed in the preceding unit. Coordinates are indexed , and a word is its low-degree-first polynomial. The code is generated by
with parameters . Equivalently, its word polynomials vanish at . Every received coefficient is assumed to be a bit. This unit treats errors, not erased positions with missing symbols.
Definition 15.2.1
(Syndromes of a received word)
For the received word , define syndromes
Addition and subtraction are identical in characteristic two. Since the codeword vanishes at these points, the same syndromes are and . If the error support is , then
Definition 15.2.2
(Location element)
The location element for coordinate is , a nonzero field element. Each of the fifteen nonzero field elements corresponds to exactly one coordinate. This decoder uses a polynomial whose roots are the location elements themselves. Another common convention uses reciprocal locations; its formulas must be changed consistently.
Theorem/proposition
Theorem 15.2.3
(A quadratic identifies one or two errors)
If the received word differs from a codeword in at most two positions, then either and there are no errors, or . In the latter case put
For two errors, the roots of are exactly their two distinct nonzero location elements. For one error, the roots are zero and its one nonzero location element. The zero root is a placeholder and does not identify a coordinate.
Theorem 15.2.4
(A verified bounded-distance decoder)
Compute the syndromes and use the quadratic procedure described below. It returns the unique codeword within distance two whenever such a codeword exists, and reports failure when none exists. Consequently, if the transmitted codeword suffers at most two errors, it is recovered. Beyond that transmission promise, the returned nearby codeword need not be the transmitted one.
Proof sketch or proof idea
The power-sum identity
Proof
(Power sums of the location elements)
Represent the possible location elements as . For one error take its location as and use only for the derivation. Then and . In characteristic two, expansion gives
because the binomial coefficient three equals one in this field. Thus . A single nonzero error gives . Two distinct nonzero locations also give , since in characteristic two would imply . Hence division by is justified under the nonempty at-most-two-error promise and gives .
Expanding now gives . In the one-error case its roots are zero and ; in the two-error case its roots are the two actual locations. The derivative of is the nonzero constant , so a root cannot be repeated. These statements also explain why an arbitrary quadratic produced outside the promise may have no roots in .
Why two syndromes check the whole code
Proof
(Two syndromes check all four defining roots)
For a binary polynomial , squaring commutes with evaluation: and . Therefore already checks the roots , and checks the fourth defining root . Their minimal-polynomial factors are precisely the two factors of . The vanishing characterization from the previous unit proves
A zero syndrome does not mean that the transmitted word was unaltered without an error bound: a nonzero codeword can itself be the error. Under the at-most-two promise, however, a nonzero error with both syndromes zero would be a nonzero codeword of weight at most two, contradicting distance five.
The syndrome map from the fifteen-dimensional binary word space into is linear over . Its kernel has dimension seven, so its rank is eight. Since also has binary dimension eight, every syndrome pair occurs. The two field symbols therefore supply exactly the eight independent check bits needed by this code; they do not discard an additional constraint that the receiver would later need.
This calculation has a useful geometric interpretation. All received words with the same syndrome form one coset of the code, because their difference has zero syndrome. Decoding chooses a small-weight representative for that coset and subtracts it. There is no need to know which codeword was transmitted while choosing the representative. Distance five says that a coset contains at most one representative of weight at most two; it does not say every coset contains one. A failure message is therefore meaningful information about the error-radius model, rather than evidence that linearity or field arithmetic broke down. The final exercises count exactly how many cosets have such a representative.
Concept lensAlgorithmic
The decoder as a computed lookup table
Distinct error patterns of weight at most two have distinct syndromes, so decoding within radius two is the same as consulting a table from syndrome pairs to error patterns; pairs without an entry mean failure. Such a table could be precomputed and stored. The quadratic instead computes the entry for a given pair on demand: and are the coefficients of the locator, and its nonzero roots read off the error pattern. By the correctness theorem, both procedures define the same function from received words to outputs.
The algorithm, including failure branches
First compute . If both vanish, return . If but , report failure: the preceding identity rules out any error pattern of weight at most two having those syndromes.
If , form and . Evaluate at all fifteen powers . Record the coordinate of every zero. If , require exactly one such nonzero root; if , require exactly two. Otherwise report failure. The nonzero derivative excludes repeated roots, but does not guarantee that an arbitrary polynomial splits in the supplied field.
Flip precisely the recorded bits to obtain . Finally verify that the number of flips is at most two and that . Return only if both checks pass. Polynomial division by can equivalently verify membership. These checks make the algorithm's output contract explicit and catch malformed intermediate computations; they are not a substitute for the preceding proof that the correct roots will be present under the promise.
Proof
(Correctness of every branch)
If any codeword is within distance two, take it as in the derivation. Its actual error locations must be exactly the nonzero roots obtained above, so the algorithm finds it. Conversely, any returned candidate is a codeword at distance at most two by verification. If two such candidates existed, their distance would be at most four, contradicting the code's distance five. Thus all branches satisfy the stated bounded-distance contract.
Proof X-ray
Two promises used at two different places
The existence half uses the hypothesis that some codeword lies within distance two of . Only then does the power-sum derivation apply to an actual error of weight at most two, guaranteeing that the nonzero roots of lie in and are exactly the error locations. The uniqueness half uses no promise about the transmission: verification makes every returned word a codeword within distance two, and two such words would be at distance at most four, which distance five forbids.
The key move is the elimination behind the quadratic. Evaluation at generator roots cancels completely, and binary error magnitudes leave only two unknown locations, whose elementary symmetric functions are and . The failure branches close the case analysis: , a wrong number of roots, or a failed final check can each occur only when no codeword lies within distance two, so a failure report never discards a correct answer.
Worked examples
Worked example 15.2.5
(Errors at positions zero and one)
Suppose errors occur at positions , so . The transmitted codeword does not affect the syndrome calculation. We obtain and . The power-sum identity gives , and
The nonzero roots correspond to positions zero and one, so these two bits are flipped. Both received syndromes are then canceled. Notice that field element one means coordinate zero, while field element zero means no coordinate at all; confusing these two would shift the decoded error pattern.
Worked example 15.2.6
(Reduce field powers before identifying positions)
Take errors at positions . The location elements are and , so . Also , since and . Therefore
For the division, follows by multiplying it by and using . The quadratic is . Looking up powers or evaluating all fifteen candidates locates positions two and five. A binary coefficient list is essential when reducing these expressions: ordinary integer coefficients modulo sixteen do not describe arithmetic in .
Worked example 15.2.7
(One error and a syndrome that must be rejected)
For a single error at position four, , so and . Hence , and . Discard the zero root and flip coordinate four. In contrast, if there is no error then both syndromes vanish and the quadratic branch is not entered, avoiding division by zero.
For the three-error polynomial , the first syndrome is , but the third is . Here . The decoder rejects this pair. This example illustrates a detectable pattern beyond the radius; it does not imply that every pattern of three or more errors is detectable.
Common mistakes
Counterexample mode
A verified codeword can still be the wrong transmitted word
Let . If zero was sent, three errors produced . But is only two errors away from , so the decoder returns . Its answer is a valid uniquely nearby codeword, yet differs from the transmitted zero word. Outside the promised radius, algebraic verification cannot reconstruct which transmission history occurred.
Common mistake
(Binary power sums do not transfer to other alphabets or conventions)
The formula for also cannot be copied unchanged to a nonbinary code. There the error coefficients may have different nonzero values, so the syndromes are weighted power sums rather than and . Nor should one mix our location-root polynomial with a reciprocal-root convention: either is usable, but changing one definition requires changing the lookup rule and formulas together.
For this fixed code, Horner evaluation and checking fifteen possible roots are small exact finite-field computations. This is not a proof of a general fast BCH decoder for arbitrary error budgets. Algorithms for longer codes and larger designed distances require a fuller error-locator calculation and a separate cost analysis.
Summary
Two extension-field syndromes completely express the parity checks of this binary code. Under at most two errors, their first and third power sums recover the sum and product of the location elements. A quadratic, explicit zero-syndrome branches and final membership checks give a complete bounded-distance decoder. Its guarantee is exact within radius two and deliberately limited outside that radius.
Exercises
Quick check
(For two distinct error locations, why can the denominator not vanish? Why does this argument use characteristic two?)
Write and ask when a sum of two field elements vanishes.
Solution
The equation gives . In characteristic two, , contradicting distinct locations. Over another characteristic opposite nonzero elements can be different, so that implication fails; the binary-error power-sum setup would also need modification.
Quick check
(If and , identify both roots of and explain which coordinate is flipped.)
Factor when its constant term is zero.
Solution
The polynomial factors as . Its roots are zero and . Only the latter is a nonzero power and hence a coordinate location. Find that unique exponent and flip its bit; zero is discarded as a placeholder, rather than interpreted as coordinate zero.
Quick check
(Count how many of the syndrome pairs correspond to a correctable error of weight at most two. Explain why these pairs are all different.)
Compare two error patterns with the same syndrome.
Solution
There are error patterns. If two had the same syndrome, their sum would be a codeword of weight at most four, impossible unless they are identical. Thus exactly syndrome pairs are correctable, leaving pairs with no error representative of weight at most two. The decoder reports failure on those cosets.
Quick check
(Suppose zero was sent but the error polynomial equals . What does the decoder return, and why does that not contradict its theorem?)
Compute the syndromes of a codeword.
Solution
The received word is , whose syndromes vanish because it is a codeword. The decoder returns without changes. Five bits were altered, so the transmission violated the at-most-two-error hypothesis. Its observed word is also consistent with transmitting without errors; the receiver cannot distinguish these histories from the received word alone.