Motivation
A code may have useful algebraic structure beyond closure under addition. In a cyclic code, rotating a valid word produces another valid word. Representing a word by a polynomial turns this rotation into multiplication, making a concrete encoding rule and a compact parity check possible. We work over a finite field and fix a positive length .
Definitions
Identify the word with the residue of
in . Every residue has a unique representative of degree less than , by polynomial division. In , multiplication by sends this word to : the top term wraps around because . We fix this direction of shift; reversing the convention changes the displayed coordinates.
A cyclic code is a linear subspace closed under this shift. A polynomial is monic if its leading coefficient is one. A generator polynomial will be chosen monic, avoiding an ambiguity by nonzero scalar multiples.
Theorem/proposition
Theorem 2.2.1
(Cyclic codes and divisors)
Every nonzero cyclic code of length over has a unique monic polynomial of least degree in the code. It divides , and the code consists exactly of the residue classes of multiples of in .
Theorem 2.2.2
(Dimension and parity check)
If is a monic divisor of of degree , its cyclic code has dimension . Writing , a residue belongs to the code exactly when .
Concept lensStructural
Cyclic codes form the divisor lattice of the modulus polynomial
The two theorems give a bijection between cyclic codes of length and monic divisors of , with for the zero code. It reverses order: the code of contains the code of exactly when . Counting cyclic codes is therefore counting divisors. Over ,
has three distinct irreducible factors, so there are exactly binary cyclic codes of length seven.
Proof sketch or proof idea
Proof
(Division by an element of least degree)
Closure under one shift and linear combinations makes closed under multiplication by every polynomial, so it is an ideal of . Choose a nonzero representative of least degree and scale it to be monic. For a representative of any codeword, polynomial division gives with . Both and represent codewords; their difference does too. Minimality forces , so every codeword is represented by a multiple of . Conversely all multiples belong to .
Divide by : with . In the left side is zero, so represents a codeword. Since its degree is less than , it is its own unique representative; minimality forces . Thus divides . If another monic least-degree polynomial generates the same code, each divides the other, and equal degree and monicity force equality.
Proof X-ray
Where minimality and the field are used
Minimality of is used twice, against two different remainders. In the first division the remainder is a codeword because and are; in the second it is a codeword because is zero in . In both cases , so a nonzero would contradict the choice of . The field hypothesis enters before either division: making monic requires its leading coefficient to be invertible, and division by a monic polynomial then produces a remainder of smaller degree. The ideal property is what turns closure under one shift into closure under multiplication by ; without it, need not be a codeword at all. The zero code is excluded only because it has no nonzero element from which to choose .
Proof
(A basis of shifted generators, and cancellation)
If , the polynomials have distinct degrees below , so their residue classes are linearly independent. Every codeword is a multiple of ; reduce its multiplier modulo to express it as a combination of these elements. They are a basis. For the check, a multiple of annihilates modulo . Conversely, if divides in the polynomial ring, cancellation of the nonzero polynomial gives . No assumption that and are coprime is needed.
The zero code is an edge case: it contains no nonzero representative of degree below . It can be described separately by the divisor , whose residue in is zero and whose dimension is zero. The whole space corresponds to .
Worked examples
Worked example 2.2.3
(A length-seven generator)
Over , divides . Direct multiplication gives
Terms appearing twice cancel in characteristic two. The code has dimension and hence 16 words. Its check polynomial is .
Worked example 2.2.4
(Encode and shift)
Take message polynomial . The codeword is
with coordinate word . Its cyclic shift is , represented by modulo ; it is in the code by construction. Here no reduction is needed until the coefficient of appears.
Worked example 2.2.5
(Test a non-codeword)
The word represents . It is not divisible by the degree-three polynomial , and hence is not a codeword. Equivalently, its check product is , nonzero in because has degree four, less than seven.
Common mistakes
Common mistake
(A linear code need not be cyclic)
A vector space closed under addition need not be closed under the shift: the binary length-three code is linear, but shifting gives , which is not in it. Its polynomials are and , and is not among them, so the set is not an ideal of and has no generator polynomial.
Counterexample mode
A generator that does not divide the modulus polynomial
One might expect every monic of degree to generate a code of dimension . Over with , take , which does not divide . In its multiples are , , and their sum : four words, so the dimension is two rather than . Bézout explains this: with , we have in , so and generate the same ideal; here . The repair is the hypothesis: the dimension formula applies to a monic divisor of , and the generator of the theorem is always one.
Common mistake
(Multiplying by without wraparound)
Multiplication by is taken in , where . Ordinary multiplication without reduction modulo can produce a polynomial of degree or more, which is not a length- word. For the codeword shifts to , written .
Common mistake
(A membership test is not a decoder)
The check polynomial is not a promise to correct an arbitrary error. It tests code membership. A decoding algorithm and a minimum-distance argument are still needed to identify or correct errors.
Summary
The quotient ring records cyclic shifts. Polynomial division gives a unique monic generator dividing , its degree determines the code dimension, and the complementary factor gives a membership check. The zero and whole-space codes are included with explicitly stated conventions.
Exercises
Quick check
(Over , let and . Verify and find the code dimension.)
Factor and use .
Solution · Answer
In characteristic two, . The generator has degree one, so the dimension is .
Quick check
(For this length-three code, is a codeword? Is a codeword?)
A codeword is a multiple of .
Solution · Answer
is a codeword. The constant polynomial is not divisible by , so it is not a codeword.
Encoding by a basis
The dimension proof gives a direct encoder. Let and write a message as . Output . Its degree is at most , so this product already has a length- representative and no wraparound is needed during this particular encoding step. Different messages produce different codewords: if , then in the polynomial ring, and the absence of zero divisors implies .
The coefficient vectors of form the rows of a generator matrix. For the seven-bit example, in the chosen low-degree-first convention those rows are
The message selects the first and third rows. Their binary sum is , agreeing with the polynomial calculation. Changing to high-degree-first coordinates reverses the displayed vectors and changes the written shift direction; it does not change the underlying code when the convention is applied consistently.
This encoder is linear but not systematic in these coordinates: the message bits do not simply occupy four designated positions unchanged. A systematic encoder can be made by polynomial division, as described next. Different generator matrices can generate the same code, so seeing a different matrix is not by itself evidence of a different code.
Systematic encoding by division
Let and let have degree less than . Divide by :
Then is a codeword. Its coefficients in degrees are exactly the coefficients of , while the first coefficients are those of . This holds because the remainder has degree below and cannot affect the higher positions. In characteristic two subtraction and addition agree, but over a general field the minus sign matters.
For the length-seven binary example, let . Then . The relation gives , hence . The systematic codeword is , with coordinates . Its final four coordinates are , the original message. Dividing by gives exactly, providing an independent check of membership.
The systematic and direct encoders map the same message to different codewords in general: the direct encoder gave , while the systematic encoder gave . Both are in the same code, because each is a multiple of . An encoding convention must therefore accompany any worked message-to-codeword example.
The check product and a syndrome
Write . A received polynomial has check product . If it is zero, is a codeword; if nonzero, is not. In particular, if with a codeword, then . This parallels a matrix syndrome: the result depends on the error but not the transmitted codeword.
A different common syndrome is the remainder of on division by . It also vanishes exactly on codewords, since is the membership condition. The two syndromes have different representations; they should not be equated as polynomials. They carry equivalent membership information, and each depends only on the error when a codeword is added. To decode, one needs a convention mapping possible syndrome values to candidate error patterns. If several errors share a syndrome, the syndrome alone cannot establish which one occurred.
For the length-seven code, the single-coordinate error has remainder . The first three remainders are ; since , the fourth is . These are nonzero and distinct. A complete single-error decoding table would have to check all seven positions and show all seven remainders are nonzero and distinct. Merely listing four does not establish that property for the whole code.
Quick check
(For and over , form a systematic codeword for the message using .)
Solution · Answer
Divide by . It is exactly , so the remainder is zero and the codeword is , with coordinates . The final two positions contain the message coefficients .
Quick check
(In the same code, test the received polynomial using the remainder modulo .)
Solution · Answer
Modulo over , . Thus , which is nonzero. The received word is not a codeword. This test alone does not identify which coordinate, if any, was corrupted.
Minimum distance of the seven-bit example
Continue the remainder table using . Multiplying each entry by and reducing gives
For a linear code, the distance between two words is the weight of their difference; differences of codewords are codewords, and every codeword is a difference from zero. Thus minimum distance equals minimum nonzero weight.
These are all seven nonzero polynomials of degree below three, each exactly once. A weight-one codeword would have polynomial and hence nonzero remainder. A weight-two codeword would have polynomial for distinct positions; its remainder could vanish only if two table entries were equal. Neither is possible. On the other hand is itself a weight-three codeword. Thus the minimum distance is exactly three.
The table now supports single-error correction: if a received polynomial has nonzero remainder, identify the unique with remainder and add to the received word. Under the hypothesis that at most one error occurred, this returns the sent codeword. The zero remainder corresponds to no error under that hypothesis. Without it, an error of weight two or more can give the same remainder as a single error, and the procedure may output a different codeword.
The code has 16 words and each binary radius-one ball has words. Since and minimum distance three makes the balls disjoint, the balls partition the space. This makes the code perfect for the radius-one packing bound; it does not mean every actual noise pattern has weight at most one.
Quick check
(Use the table to decode a received polynomial whose remainder modulo is , assuming at most one error.)
Solution · Answer
The table identifies the remainder as that of . Add to the received polynomial. Its new remainder is zero, and the distance-three result shows that the resulting codeword is the only one within one coordinate change.
Quick check
(Why can a weight-three codeword be an undetected error when the zero word is sent?)
Solution · Answer
Adding a codeword to zero produces that codeword, whose remainder on division by is zero. The receiver sees a valid codeword, so membership testing alone detects no error. The minimum-distance theorem promises detection of up to two errors, not of every error of greater weight.
Checking the hypotheses
The field assumption ensures that polynomial division by a nonzero polynomial works and that the polynomial ring has no zero divisors. Both facts were used: division produced a lower-degree remainder, and cancellation proved the parity-check criterion. Over a general coefficient ring these steps may fail, so the same proof cannot simply be copied. The positive length assumption supplies the modulus and the length- coordinate convention.
A cyclic shift preserves Hamming weight because it only permutes coordinates. Thus all cyclic shifts of a codeword have the same weight, but this observation alone does not determine the minimum distance: one must consider all nonzero linear combinations as well. In the seven-bit example the remainder table supplies the missing lower bound, and the weight-three generator supplies a matching upper bound.
A repeated factor shows concretely why coprimality of was not assumed. Over with , . Take , so . The code generated by consists of and . The parity-check identity still works: is divisible by exactly when divides , by cancellation in . This is cancellation before passing to the quotient; the quotient itself can have zero divisors.