Also known as: Chien search, Chien's search
Chien search is the step in algebraic decoding that finds the roots of the error-locator polynomial Λ(x) by simply evaluating it at every element of the code’s finite field.1 Each root corresponds to one error position in the received Reed–Solomon or BCH codeword, so Chien search converts the abstract locator polynomial — produced by the Berlekamp–Massey algorithm — into a concrete list of which symbols are wrong.2
How it works
The error-locator polynomial Λ(x) has the property that its roots are the inverses of the field elements that mark the error positions. Because a finite field has only a fixed number of nonzero elements — every one a power α⁰, α¹, α², … of a primitive element α — you can find all the roots by exhaustive substitution: plug in each α^i in turn and check whether Λ(α^i) comes out to zero.
Chien’s contribution is making that sweep cheap. Instead of recomputing every power of every term from scratch, it keeps a running set of registers, one per polynomial coefficient. To move from testing α^i to testing α^(i+1), each register is multiplied by a fixed constant (α raised to that term’s degree), and the values are summed. A zero sum means α^i is a root and therefore position i is in error:
- Set up one accumulator per coefficient of Λ(x), scaled by increasing powers of α.
- For each candidate position, add the accumulators; if the total is zero, record the position.
- Advance every accumulator by one multiplication and repeat across the whole codeword.
The cost is one field multiply-and-add per coefficient per position, giving simple, regular, highly parallelisable hardware — which is why Chien search is the standard root finder in RS/BCH decoder chips even though it is, at heart, brute-force evaluation.
In practice
Chien search sits in the middle of the classic three-stage algebraic decoder: Berlekamp–Massey (or extended Euclid) builds Λ(x); Chien search finds its roots to give the error positions; then the Forney algorithm computes the error magnitudes at exactly those positions. For a code that corrects t errors, the degree of Λ(x) tells you how many roots to expect; if Chien search finds fewer distinct roots in the valid range than the degree, the received word contained more errors than the code can handle, and the decoder can flag an uncorrectable block rather than emit a wrong correction. That built-in failure detection is one reason the exhaustive sweep is valued over cleverer but less transparent root finders for short codes.
Relevance to SDR
The short Reed–Solomon and BCH codes used in digital radio signalling — for example the RS protection on parts of P25 and the BCH-guarded sync/status words in several trunking formats — are decoded with exactly this position-then-value pipeline. Chien search is an internal step of the forward error correction stage, invisible in the traffic itself. GopherTrunk validates and corrects these protected fields as part of decoding; Chien search names the general-purpose method for the root-finding half of that block-code math, whether realised as a full field sweep or, for the smallest codes, a lookup.
Sources
-
Chien search — Wikipedia, for the field-sweep root finding of the error-locator polynomial. ↩
-
Cyclic decoding procedures for BCH codes — R. T. Chien, IEEE Trans. Information Theory (1964), the original search procedure. ↩