A linear code is negacyclic if being a codeword implies that is a codeword. Polynomial identification makes it an ideal modulo . For odd , the substitution gives a monomial equivalence of linear codes between negacyclic and cyclic codes.
A zero of a cyclic code is a polynomial root of its generator polynomial, taken in a splitting field. Every codeword, represented as a polynomial, vanishes there. For a repeated-root cyclic code, the multiplicity of a root must also be retained: ordinary evaluations alone need not determine the code.
A repeated-root cyclic code has length divisible by the characteristic of its field, so the polynomial has repeated factors. Its generator can involve powers of those factors. In characteristic two, length gives .
// Target: algebra.bigb
If the generator polynomial of a cyclic code has distinct roots with multiplicities , a word belongs to the code exactly when for , where is its Hasse derivative. The corresponding rows have entries for and zero otherwise. Expansion in a basis of the splitting field gives equations over the original finite field; an independent selection has rank .
For , the binary cyclic codes are exactly the nested ideals generated by for . They have dimensions and canonical check polynomials . The endpoint ideals are the entire word space and the zero code.
// Target: algebra.bigb
For a cyclic code with monic generator , the canonical check polynomial is . A word belongs to the code exactly when is zero modulo , since cancellation in the polynomial ring turns this condition into . The kernel condition alone allows additional polynomials: it is equivalent to . Requiring the monic divisor of the modulus singles out the canonical choice.
// Target: algebra.bigb
Over , and the degree-four factor is irreducible: it has no linear root and is not divisible by the sole irreducible quadratic . The four monic divisors give precisely four cyclic codes: the full five-dimensional space, the four-dimensional even-weight code, the one-dimensional repetition code, and the zero code. Their generator polynomials of a cyclic code are respectively , , , and .
The unique monic divisor of generating a cyclic code is its generator polynomial. The code has dimension .
Let be a polynomial root of the generator polynomial of a cyclic code over a finite field , viewed in an field extension. Every codeword satisfies , so a received polynomial has syndrome . A single-symbol error givesTo identify both value and position from this one syndrome, the maps must be injective over the allowed nonzero values and coordinate positions. Equivalently, the powers for distinct positions must not be proportional by a nonzero element of the base finite field. In the binary case , distinct powers suffice.
For nonbinary errors, distinct powers alone do not suffice. Over , take and two positions. Errors in position zero and in position one both evaluate to , although and are distinct. Additional syndromes or stronger conditions on the powers are then necessary.
Let a binary cyclic code of length have defining zeros of a cyclic code and , with of multiplicative order . A single error in position has error polynomial and syndromesThus and are necessary for a single-error pattern. Search the distinct powers of for ; if it is absent, this is not a single-error syndrome. Otherwise flip the unique coordinate and test membership in the full cyclic code, for example by divisibility by its entire generator polynomial of a cyclic code.
Checking only the two roots is sufficient only when they generate all defining checks, including their field conjugates. A cyclic code with additional defining roots requires those checks too. If the full membership test succeeds and the minimum Hamming distance is at least five, the corrected codeword is the unique codeword within two errors of the received word: two such codewords would be at Hamming distance at most four. The two-syndrome relation alone does not establish membership.
The dual of a cyclic code is cyclic. If , then the dual generator is the monic reciprocal polynomial .
Over ,Its eight monic divisors generate the eight cyclic codes of length seven: the whole-space, even-weight, two Hamming, two simplex, repetition, and zero codes.
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
There are currently no matching articles.