From a polynomial to a distance guarantee
A cyclic code is not useful merely because its words can be rotated. We want to know how far apart its words are, and then use a received word to locate an error. This unit proves a consecutive-root lower bound and constructs every entry of a small decoder. It builds on the earlier distance and syndrome unit.
Let be a finite field, , and represent by . Coordinates are written constant term first. Work modulo , so multiplying by shifts the last coordinate to the first. A linear code closed under this shift is cyclic: closure under repeated shifts and linear combinations makes it an ideal of .
Theorem 2.1.1
(Generator polynomial and dimension of a cyclic code)
Every cyclic code of length over has a unique monic generator , and divides . Conversely every monic divisor of generates a cyclic code. If , then the codewords are exactly the products with , each written in only one way, so .
Proof
(Least degree and polynomial division)
Take the inverse image of in , an ideal containing . Choose a monic nonzero element of least degree. Polynomial division shows every element of the inverse image is divisible by , since a nonzero remainder would lie in the ideal and have smaller degree. In particular divides . If is another monic element of the same degree, then lies in the ideal and has smaller degree, so . Conversely each monic divisor generates an ideal of the quotient. The divisor gives the zero code; in distance statements below, we assume the code contains a nonzero word.
Each product with has degree less than , so it is its own reduced representative. Conversely every codeword is represented by some . Divide by , which has degree : if with , then . Uniqueness follows because in the polynomial ring implies . Hence form a basis.
The consecutive-root bound
Suppose an extension field contains an element of multiplicative order exactly . Evaluation at each power of is well defined on the quotient because . We assume such an exists; in particular its order is coprime to the characteristic. Let be an integer and .
Theorem 2.1.2
(A consecutive-root distance bound)
If every codeword satisfies , then every nonzero codeword has Hamming weight at least . Thus .
Proof
(A Vandermonde system with too few positions)
Suppose a nonzero codeword has nonzero coefficients, at distinct positions . Put . These values are distinct and nonzero because and has order . The first root equations say
The coefficient matrix is Vandermonde, with determinant . Hence every is zero, contradicting the choice of nonzero coefficients. This proves a lower bound, not automatically equality. To establish exact distance one must also exhibit a codeword attaining it.
Proof X-ray
Where the weight bound, consecutive exponents and the order enter
Three hypotheses enter at three separate places. The bound guarantees that the equations used are among the given roots, so the system has as many equations as unknowns. Consecutiveness of the exponents is what makes the coefficient matrix a Vandermonde matrix once the common factor is absorbed into the unknowns; roots at scattered exponents give a generalized Vandermonde matrix, whose determinant can vanish. The order of being exactly makes the distinct, so the determinant is nonzero, and lets one pass from to . Nothing in the argument produces a codeword of weight , which is why the conclusion is only a lower bound.
A complete seven-position syndrome table
Work in and set . It has no root in , so this cubic is irreducible. Let and . Then . Repeated multiplication gives
The seven displayed elements are distinct and nonzero, and , so has order seven. Direct multiplication gives
The cyclic code generated by has dimension four and 16 words. Since and , the theorem with gives distance at least three. The generator itself has weight three, so the distance is exactly three. In the stated coordinate order its vector is : it is a codeword, not a one-bit error.
Common mistake
(Counting all roots instead of a consecutive run)
The generator has three roots among the powers of , namely , and . Treating them as three consecutive roots would give , yet itself has weight three. The bound needs consecutive exponents: , so the longest run is , giving , which is sharp here.
For a received polynomial of degree below seven, define its syndrome as the remainder on division by , equivalently . A codeword has zero remainder, so if , the syndrome is . The table identifies every possible single flipped coordinate. If the syndrome is zero, output unchanged; otherwise flip the uniquely indexed coordinate. This corrects every error of weight at most one. The claim is conditional on that error model, not a promise about arbitrary corruption.
Concept lensStructural
This code is the binary Hamming code of length seven
Write each in the basis and use these coordinate vectors as the columns of a binary matrix . Then is the coordinate vector of , so the code is the kernel of . By the table, the columns are exactly the seven nonzero vectors of , each once: the defining check matrix of the Hamming code. The sixteen radius-one balls hold words, so every received word lies within distance one of exactly one codeword, and no syndrome can signal a two-bit error.
Common mistake
(Reading the vector highest degree first)
The string means because coordinates are written constant term first. Read the other way it would be , whose syndrome is . A decoder with the reversed convention would call the generator a corrupted word and flip a coordinate. Fix the convention before computing any syndrome.
Worked example 2.1.3
(Follow one received word)
Let , written . Modulo , , so the syndrome is . The table identifies coordinate ; flipping it produces , written . Since the code distance is three, this is the unique codeword within distance one of .
Worked example 2.1.4
(An error in the last coordinate)
Transmit the codeword , written , and suppose coordinate is flipped, so , written . Using the table,
The syndrome indexes coordinate , and flipping it returns . The computation never used which codeword was sent: the codeword part contributes to the syndrome.
Worked example 2.1.5
(Two errors are miscorrected)
Transmit the zero word and let coordinates and flip, so , written . Its syndrome is , so the one-error rule flips coordinate and outputs , written . The output is a codeword, but at distance three from the word that was sent. When the error has weight two, the decoder still returns a codeword; it is the wrong one, and nothing in the syndrome signals the failure.
Counterexample mode
Zero syndrome does not mean no error
If the zero word is transmitted and the weight-three error occurs, the received word is the nonzero codeword and its syndrome is zero. The decoder outputs it unchanged. Syndrome zero certifies code membership, not that the channel made no errors.
Exercises
Quick check
(Why does follow from in characteristic two?)
Square the equation .
Solution · Answer
Squaring is a field homomorphism in characteristic two and the coefficients of lie in , so .
Quick check
(A received word has syndrome . Which coordinate does the one-error rule flip?)
Find this element in the table of powers.
Solution · Answer
The table gives , so flip coordinate , counting from zero.
Quick check
(Explain why distance at least three rules out two codewords both within distance one of the same received word.)
Use the triangle inequality for Hamming distance.
Solution · Answer
The triangle inequality would put those two codewords at distance at most two, contradicting the lower bound three.
Quick check
(What is the dimension of the code generated by ? What about ?)
Use , and note what represents in the quotient.
Solution
generates the whole -dimensional space. The divisor represents zero in the quotient and generates the zero code, of dimension zero; its minimum distance is not defined by the nonzero-code convention used here.
Further reading
MIT notes on polynomial codes develop polynomial encoding and remainder-based error location. CMU coding-theory notes discuss BCH codes and the consecutive-root distance argument.