Motivation
A parity check is an equation that every transmitted word must satisfy. For a cyclic code, evaluating its word polynomial at a root of the generator gives such an equation. The useful question is how to choose several roots so that a small number of altered coordinates cannot satisfy every check. Consecutive powers of one field element provide an answer: the resulting equations form an invertible Vandermonde system whenever the proposed error has sufficiently small support.
This construction separates two roles of the alphabet. The transmitted symbols can remain binary even though we evaluate their polynomials in a larger field. The extension field supplies enough different check points. It does not turn each binary coordinate into an independently selectable extension-field symbol. That distinction explains both the strength of the construction and the dimension calculation below.
We assume polynomial division over a field and the earlier description of cyclic codes as ideals modulo . We will prove the root bound used here, including the hypotheses that make its determinant nonzero. The final binary example is a fully specified code; the general designed distance is a lower bound, not a promise of equality for every parameter choice.
Definitions
Let be a prime power. Work in a supplied extension field containing . Choose a positive integer and an element of multiplicative order exactly . Thus are different and nonzero. A word over corresponds to
Coordinate zero is the constant coefficient. Multiplication by modulo rotates coordinates with the old last coordinate moving to position zero.
Definition 15.1.1
(Minimal polynomial)
For , its minimal polynomial over is the monic polynomial of least positive degree having as a root. Polynomial division shows that it divides every polynomial over vanishing at : divide by the minimal polynomial and evaluate the smaller remainder. The remainder must vanish identically by minimality.
Definition 15.1.2
(BCH code and designed distance)
Fix an integer and an integer . Let be the monic least common multiple of the minimal polynomials of
Exponents are interpreted modulo . The cyclic code generated by is called a BCH code with these consecutive defining roots and designed distance . The common narrow-sense choice is . Different designed parameters can produce the same generator and hence the same code.
Theorem/proposition
Theorem 15.1.3
(The generator exists over the transmitted alphabet)
The polynomial lies in and divides . Its multiples modulo form a linear cyclic code of dimension . Equivalently, its words are precisely the degree-less-than- polynomials vanishing at every chosen defining root.
Theorem 15.1.4
(Consecutive-root distance bound)
If the code is nonzero, every nonzero codeword has weight at least . Consequently its minimum distance is at least , and it uniquely corrects every pattern of at most symbol errors. This distance statement alone does not supply a decoding algorithm.
Concept lensAlgebraic
The code as the base-field part of an extension-field kernel
Let be the matrix over with entry in row and column . Then lists the values , so the code is . Removing the factor from column turns any columns into an invertible Vandermonde matrix, so every columns are independent over , which is exactly distance at least . Over this kernel has dimension ; keeping only its vectors with entries in preserves the distance bound but leaves dimension , which can be smaller.
Proof sketch or proof idea
Minimal polynomials package conjugate checks
Proof
(Frobenius orbits and the ideal generated by g)
If a polynomial over vanishes at , then . Thus a root brings its entire Frobenius orbit with it. Conversely, form the product of over the distinct orbit elements of . Frobenius permutes these factors, so it fixes every coefficient. A coefficient fixed by Frobenius satisfies . This polynomial has at most roots in a field and already vanishes on all elements of , so its fixed elements are exactly that subfield. The orbit product therefore belongs to .
Every polynomial vanishing at vanishes at the whole orbit and is divisible by that product of distinct linear factors in . Division by the monic orbit product also takes place in , proving that it is the minimal polynomial. This gives a practical way to compute generators: group the exponents into orbits under multiplication by modulo , then take one minimal polynomial per required orbit. Repeated appearances of one orbit do not impose new independent factors.
Each defining root is a root of . Its minimal polynomial divides that polynomial, hence their least common multiple does too. Write . Every multiple of modulo has a unique representative with : divide the multiplier by . Uniqueness follows because a nonzero such product has degree less than and cannot be zero modulo . These multipliers give a basis of size . Multiplication by preserves the ideal, proving cyclicity.
Vanishing at the chosen roots is equivalent to divisibility by their minimal polynomials, hence by . This proves the alternative check description. Extension-field equations may be expanded into several base-field equations by choosing a basis of over ; counting the displayed extension-field equations without accounting for conjugacy would overcount their rank.
The generator also gives a concrete encoder without solving a fresh system for every message. List the message coefficients as a polynomial of degree less than the dimension and multiply by the fixed . The product has degree less than , so no reduction is needed at this stage. Distinct messages give distinct products because a polynomial ring over a field has no zero divisors. At the receiver, division by checks a candidate word. These operations justify calling this a construction, even before any efficient error-correction procedure has been derived. They also expose the rate cost: adding a genuinely new conjugacy class increases the generator degree and reduces the number of free message coefficients. Adding another root from an already required class has no such cost.
A short support forces a Vandermonde contradiction
Proof
(A short support cannot satisfy the checks)
Suppose a nonzero codeword had weight , at distinct support positions . Put . The first consecutive root equations give, for ,
The matrix with row and column equal to has determinant . One way to see this identity is to regard the determinant as an alternating polynomial: each difference divides it, the total degrees agree, and comparison of the leading monomial gives coefficient one. The factors are nonzero because has order exactly and the support positions are different modulo .
The system is therefore invertible over . It forces for every . But every is nonzero, even if is negative, and each support coefficient is nonzero. This contradiction proves the weight bound. Linearity turns minimum nonzero weight into minimum distance. Two codewords both within changes of one received word would be within of each other, proving uniqueness in the stated radius.
Proof X-ray
What makes consecutive roots special
Three hypotheses are used, each at one identifiable point. Consecutive exponents let the column factor be pulled out, leaving the rows of a Vandermonde matrix; an arbitrary set of roots gives no such factorization. The exact order of makes the distinct, so the determinant is nonzero. Finally, every is nonzero, which turns into .
The key move is to keep only the supposed support coordinates and only of the available equations, so that the question becomes a square linear system. The argument closes by contradicting the choice of support. It never counts roots of , whose degree may be close to , so no root-count bound could have replaced the determinant.
Worked examples
Worked example 15.1.5
(Build the field and identify two conjugacy classes)
Take , writing for the residue of . The polynomial has no root in . A reducible quartic with no linear factor would be a product of irreducible quadratics; the only monic irreducible quadratic over is . The quartic has remainder one modulo this quadratic, so it is irreducible and the quotient really is a field with sixteen elements.
The relation is . Its nonzero multiplicative group has fifteen elements, so the order of divides fifteen. It is not one or three, since either possibility would give a nonzero polynomial relation of degree below four. Also , since equality would give a relation of degree two. Thus its order is fifteen.
The Frobenius orbits of exponents one and three modulo fifteen are and . The first minimal polynomial is . Since has order five, it is a root of ; its orbit has four elements, so this quartic is its minimal polynomial. The two root sets are disjoint.
Worked example 15.1.6
(A binary code with exact parameters [15,7,5])
Choose and . The defining roots are . Their two conjugacy classes give
The generator has degree eight, so the binary dimension is seven. The consecutive-root theorem gives distance at least five. The polynomial itself is a nonzero codeword of weight five, so the distance is also at most five. Hence the exact parameters are , and every pair of bit errors is uniquely correctable. Equality was established by a specific word, not by interpreting the designed distance as an equality theorem.
Worked example 15.1.7
(Encode and rotate without changing the code)
Using the coefficient-message convention, encode by multiplying by . Terms of degrees eight and six occur twice and cancel in characteristic two, leaving
Its six nonzero coordinates are positions . The seven message coefficients are not generally visible unchanged in seven designated coordinates; this encoder is not being claimed systematic.
For a rotation that crosses the endpoint, multiply by . Since in the quotient, the result is . It remains a codeword. Evaluating a rotated word at a defining root multiplies its old value zero by that root, providing another direct explanation of the preserved checks.
Common mistakes
Common mistake
(Extension-field checks do not change the message alphabet)
The code just constructed has words, not . Every coordinate and every multiplier coefficient belongs to . Evaluations in are a device for expressing binary linear constraints. Treating each displayed field equation as sixteen independent choices changes the construction entirely.
Common mistake
(One conjugacy class contributes one factor)
Counting every consecutive root as a new minimal-polynomial factor overcounts. The roots , and already belong to one binary conjugacy class. Multiplying the same minimal polynomial several times imposes a repeated factor; since is odd, has no repeated roots in characteristic two, so such a product would not divide at all. For the roots the naive product has degree , whereas the least common multiple has degree .
Counterexample mode
An element of too small an order
One might expect any nonzero with to serve. Take , the field of the examples, and , which satisfies but has order five. With and , the defining roots form one conjugacy class, so . Then
is a codeword of weight two, below the designed value five. Directly, each defining root is a power of , so and . In the proof, positions and give and , and the Vandermonde determinant vanishes. The repair is the stated hypothesis: must have order exactly , so that distinct positions modulo give distinct .
A distance proof gives a unique answer under an error promise; locating the altered positions requires the syndrome algorithm developed in the companion unit.
Summary
BCH construction chooses extension-field roots while retaining a base-field alphabet. Frobenius orbits determine the generator and its dimension. Consecutive root powers force every short support to satisfy an invertible Vandermonde system, proving a designed-distance lower bound. The binary length-fifteen example reaches that bound because its generator already has weight five.
Exercises
Quick check
(Explain why follows from , and why then has no repeated roots.)
Look at the prime factors of and at the derivative of .
Solution
A prime dividing cannot divide , so it cannot divide . The derivative is , nonzero in the field. A common root of it and would have to be zero, but zero is not a root of the latter. Thus the polynomials are coprime and there are no repeated roots.
Quick check
(Prove the dimension estimate for this construction, allowing the right-hand side to be negative.)
Bound the degree of each minimal polynomial by the size of its Frobenius orbit.
Solution
Each minimal polynomial has degree at most , because the Frobenius orbit closes after at most steps. The degree of an lcm is at most the sum of the degrees of its factors, giving and the asserted dimension bound. Shared orbits can make this estimate very loose.
Quick check
(Over , let have order seven and choose roots , so the designed distance is four. Determine the generator and actual minimum distance.)
List the binary cyclotomic orbits modulo seven.
Solution
The binary exponent orbits are and . The selected roots meet both, so . The code has dimension one and consists of the zero word and the all-one word. Its distance is seven, strictly larger than the designed value four.
Quick check
(Explain why the length-fifteen code is not a perfect two-error-correcting code, although its distance equals its designed distance.)
Compare the total size of the disjoint radius-two balls with .
Solution
A radius-two binary ball of length fifteen contains words. The codewords have disjoint such balls, but together these contain only words. Thus some received words lie outside every radius-two ball. Reaching a designed-distance bound is different from filling the ambient space with decoding balls.