Let be a finite field, let be coprime to , and choose an element of multiplicative order in an field extension. A BCH code of length , starting exponent , and design distance is the cyclic code whose generator polynomial of a cyclic code iswhere is the algebraic minimal polynomial of over . Equivalently, is the least-degree monic polynomial over the base finite field vanishing at consecutive powers. This least-degree condition distinguishes the BCH code from its proper cyclic code subcodes with additional zeros. The BCH bound gives minimum Hamming distance at least .
For example, over the field with two elements, let and let be a polynomial root of . The roots and have the same algebraic minimal polynomial, so and give , a Hamming code of length seven.[ref]
Shift-Register Synthesis and BCH Decoding by James L. Massey. Sections IV–V: BCH codes and synthesis-based decoding
The designed distance of a BCH code is the value specified by requiring consecutive defining zeros of a cyclic code. The BCH bound guarantees minimum Hamming distance at least , but the actual minimum Hamming distance can be larger. To prove equality, one can exhibit a nonzero codeword of Hamming weight exactly .
For odd , multiplication by two permutes the residues modulo . Its orbit through is the binary cyclotomic coset modulo an odd integer. If has order in a finite field whose field characteristic is two, the Frobenius automorphism sends to . Hence the minimal polynomial of an algebraic element over is . Its coefficients are fixed by Frobenius and lie in , and its degree is the orbit size. Thus a binary cyclic code containing one defining zero of a cyclic code must contain the full orbit as zeros.
For error locations in a cyclic code with primitive root , the error locator polynomial is . Its roots encode the error positions.
A Chien search finds error positions by evaluating an error locator polynomial at every possible inverse location value . A zero identifies coordinate . Using the recurrence between successive powers of avoids recomputing all monomials from scratch.
For errors at distinct nonzero locations , the evaluator associated with syndromes is . Its degree is smaller than the number of errors. Together with the error locator polynomial it gives the Reed-Solomon key equation and the Forney algorithm for error magnitudes.
For distinct error locations and the syndrome convention , the displayed formula recovers the error magnitudes from the error evaluator polynomial and error locator polynomial. At , the evaluator is , whereas the locator's formal derivative is . Their quotient gives the formula; the denominator is nonzero because the locations are distinct.
// Target: polynomial.bigb
Articles by others on the same topic
BCH (Bose–Chaudhuri–Hocquenghem) codes are a class of error-correcting codes that are used in digital communication and storage to detect and correct multiple random error patterns in data. These codes are named after the three researchers who developed them in the 1960s: Raj Chandra Bose, Alexis Hocquenghem, and D. R. McEliece, who contributed to their understanding and application.