Back to the on-screen lesson ·
Codes closed under rotation; codewords as multiples of a generator polynomial; CRCs.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to define cyclic codes, translate between bit strings and polynomials modulo $x^n - 1$, explain why a cyclic code is generated by a single polynomial dividing $x^n - 1$ and read its dimension from the degree, encode and check with polynomial multiplication and division, and see cyclic redundancy checks as cyclic codes used for detection. You will describe Reed-Solomon codes as evaluations of low-degree polynomials over a finite field, prove they are maximum distance separable, compute their length, dimension and correction capability from the symbol size and the number of check symbols, and explain why symbol-based codes with interleaving are the right tool against bursts of errors.
A linear code is cyclic when every cyclic shift of a codeword is again a codeword. Write a word $c_0 c_1 \cdots c_{n-1}$ as the polynomial $c(x) = c_0 + c_1 x + \cdots + c_{n-1} x^{n-1}$ over $\mathbb{F}_2$; a cyclic shift is multiplication by $x$ modulo $x^n - 1$, so a cyclic code is an ideal of the ring $\mathbb{F}_2[x]/(x^n - 1)$ and is generated by a single monic generator polynomial $g(x)$ that divides $x^n - 1$, of degree $n - k$. The codewords are exactly the multiples $m(x) g(x)$ with $\deg m < k$; systematic encoding sends $m(x) x^{n-k}$ minus its remainder modulo $g$, and the syndrome of a received word is its remainder modulo $g(x)$. All of this runs on shift registers, which is why cyclic codes dominate hardware: the cyclic redundancy checks (CRCs) that guard every Ethernet frame and ZIP file are cyclic codes used for detection, $g(x) = x + 1$ being the humble parity bit. Hamming codes, BCH codes and Reed-Solomon codes are all cyclic, and factoring $x^n - 1$ over finite fields is the route to designing them with a prescribed minimum distance.
Another way: example
Over $\mathbb{F}_2$, $x^7 - 1 = (x + 1)(x^3 + x + 1)(x^3 + x^2 + 1)$. Taking $g(x) = x^3 + x + 1$ gives a cyclic $[7, 4]$ code: it is the Hamming code. The message $1 + x$ (bits $1100$) encodes to $(1 + x)(1 + x + x^3) = 1 + x^2 + x^3 + x^4$, the word $1011100$; its rotations $0101110$, $0010111$, and so on are codewords too.
Another way: steps
A linear code is cyclic when every cyclic shift of a codeword is again a codeword. The right language for that is polynomials: write $c_0 c_1 \cdots c_{n-1}$ as $$c(x) = c_0 + c_1 x + \cdots + c_{n-1} x^{n-1}$$ over $\mathbb{F}_2$. Multiplying by $x$ raises every index by one, and reducing modulo $x^n - 1$ wraps the top coefficient back to the bottom — so a cyclic shift is multiplication by $x$ modulo $x^n - 1$.
| bits $c_0 c_1 \ldots c_6$ | polynomial | one right shift | polynomial |
|---|---|---|---|
| $1011000$ | $1 + x^2 + x^3$ | $0101100$ | $x + x^3 + x^4$ |
| $0001011$ | $x^3 + x^5 + x^6$ | $1000101$ | $1 + x^4 + x^6$ |
| $1110100$ | $1 + x + x^2 + x^4$ | $0111010$ | $x + x^2 + x^3 + x^5$ |
Closed under shifts and under sums means closed under multiplication by any polynomial: a cyclic code is an ideal of the ring $\mathbb{F}_2[x]/(x^n - 1)$. Every such ideal is generated by a single monic generator polynomial $g(x)$, which must divide $x^n - 1$, of degree $n - k$. The codewords are exactly the multiples $m(x) g(x)$ with $\deg m < k$; the syndrome of a received word is its remainder modulo $g(x)$, and systematic encoding sends $m(x) x^{n-k}$ minus that remainder. All of it runs on a shift register with a few XOR taps, which is why cyclic codes are everywhere in hardware.
The simplest generator of all is $g(x) = x + 1$. Dividing by $x + 1$ over $\mathbb{F}_2$ is the same as evaluating at $x = 1$, which adds up all the coefficients — so the remainder is the parity of the message's weight: $1$ for an odd number of ones, $0$ for an even number. The single-parity code is a cyclic code, and the simplest CRC there is.
| message | weight (number of $1$s) | remainder mod $x + 1$ |
|---|---|---|
| $1101$ | $3$ | $1$ |
| $1111$ | $4$ | $0$ |
| $1000$ | $1$ | $1$ |
| $1010$ | $2$ | $0$ |
| $0111$ | $3$ | $1$ |
| $110011$ | $4$ | $0$ |
Common mistakes
Shifting $c(x)$ gives $x c(x) \bmod (x^n - 1)$: the top coefficient wraps to the bottom.
Closed under shifts and sums means closed under multiplication by any polynomial: an ideal, hence principal, hence generated by one $g(x) \mid x^n - 1$.
$\mathbb{F}_2[x]$ is a principal ideal domain.
$g(x) = x^3 + x + 1$, message $1011$ i.e. $m(x) = 1 + x^2 + x^3$. Multiply by $x^3$: $x^3 + x^5 + x^6$; divide by $g$: remainder $x^2 + x$ (bits $011$).
Long division over $\mathbb{F}_2$.
Transmit $0111011$ (remainder then message): it is divisible by $g$, and any single error, or any burst shorter than $4$ bits, leaves a nonzero remainder.
A degree-$r$ CRC detects all bursts of length $\le r$.
As a polynomial: $1 + x + x^2 + x^4$.
Leftmost bit is the constant term in this convention.
Divide by $x^3 + x + 1$: $x^4 = x \cdot x^3 \equiv x(x + 1) = x^2 + x$, so the polynomial reduces to $1 + x + x^2 + x^2 + x = 1$.
The remainder is $1 \ne 0$, so it is not a codeword — and the nonzero remainder is its syndrome.
$g(x) = x^3 + x + 1$, message $1011$, that is $m(x) = 1 + x^2 + x^3$.
Shift by $x^3$ to make room for three check bits, then take the remainder modulo $g$.
This is the systematic form: check bits first, then the message untouched.
Transmit remainder followed by message. Every single error, and every burst shorter than four bits, changes the remainder and is caught.
$c(x) = 1 + x + x^2 + x^4$; divide by $x^3 + x + 1$: $x^4 = x \cdot x^3 \equiv x(x + 1) = x^2 + x$, so $c \equiv 1 + x + x^2 + x^2 + x = 1$.
Remainder $1 \ne 0$: not a codeword; an error is detected.
$0100111$ is a codeword of a cyclic code of length $7$. Write the codeword obtained by shifting it one place to the right (cyclically).
shifted = s
A cyclic $[\,28, 18\,]$ code has generator polynomial $g(x)$. What is the degree of $g(x)$, and what must $g(x)$ divide? Enter the degree.
Computed value: answer
The simplest cyclic redundancy check uses $g(x) = x + 1$. Treat the message $1101$ as a polynomial over $\mathbb{F}_2$ (leftmost bit the highest power). What is the remainder on division by $x + 1$?
Computed value: answer
$0001011$ is a codeword of a cyclic code of length $7$. Write the codeword obtained by shifting it one place to the right (cyclically).
shifted = s
What makes a linear code cyclic, and what does that buy?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A cyclic $[\,14, 13\,]$ code has generator polynomial $g(x)$. What is the degree of $g(x)$, and what must $g(x)$ divide? Enter the degree.
Computed value: answer
You can build cyclic codes from a generator polynomial and size a Reed-Solomon code for a given burst. This completes the course: from the entropy of a source to the codes that carry it across a noisy channel at rates the theorems allow.
9. Your turn: is $1110100$ a codeword of the cyclic code with $g(x) = x^3 + x + 1$?, step 2