Back to the on-screen lesson ·
Symbols in GF(2^m), n = 2^m − 1, d = n − k + 1; burst correction in practice.
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.
Reed-Solomon (RS) codes work over a finite field $\text{GF}(q)$, in practice $\text{GF}(2^m)$ with $m$-bit symbols such as bytes ($m = 8$). A message of $k$ symbols is the coefficient list of a polynomial $m(x)$ of degree below $k$; the codeword is its values $(m(\alpha^0), m(\alpha^1), \ldots, m(\alpha^{n-1}))$ at the $n = q - 1$ nonzero field elements, $\alpha$ a primitive element. Two distinct polynomials of degree below $k$ agree in at most $k - 1$ points, so distinct codewords differ in at least $n - k + 1$ positions: $d = n - k + 1$, the Singleton bound with equality, so RS codes are MDS and correct $t = (n - k)/2$ symbol errors, or fill $n - k$ erasures. They are cyclic, with generator $g(x) = \prod_{i=1}^{2t}(x - \alpha^i)$, and have efficient algebraic decoders. Because a symbol is $m$ bits, a burst of bit errors that spans few symbols costs few symbol errors: a code correcting $t$ symbols corrects any burst of up to $m(t - 1) + 1$ bits. The $[255, 223]$ RS code over bytes, correcting $16$ symbol errors, guards CDs, DVDs, QR codes and deep-space transmissions, usually as the outer code of a concatenated scheme.
Another way: picture
A polynomial curve of degree below $k$ sampled at $n$ points. Corrupt $t$ of the samples: since any $k$ correct samples pin the curve down and $n - t > k + t$ remain clean, the original polynomial still fits more points than any impostor, and the decoder recovers it.
Another way: steps
Reed-Solomon codes live over a finite field $\text{GF}(2^m)$ whose elements are $m$-bit symbols — bytes when $m = 8$. Take the $k$ message symbols as the coefficients of a polynomial $m(x)$ of degree below $k$, and let the codeword be its values at the $n = 2^m - 1$ nonzero field elements: $$c = \big(m(\alpha^0), m(\alpha^1), \ldots, m(\alpha^{n-1})\big).$$ Two distinct polynomials of degree below $k$ agree in at most $k - 1$ points, because their difference is a nonzero polynomial of degree below $k$ and has at most $k - 1$ roots. So two codewords differ in at least $n - (k - 1) = n - k + 1$ positions: $$d = n - k + 1,$$ the Singleton bound with equality. Reed-Solomon codes are MDS.
| symbol size $m$ | $n = 2^m - 1$ | example $k$ | $d = n - k + 1$ | errors $t$ | burst $m(t-1) + 1$ bits |
|---|---|---|---|---|---|
| $3$ | $7$ | $3$ | $5$ | $2$ | $4$ |
| $4$ | $15$ | $9$ | $7$ | $3$ | $9$ |
| $8$ | $255$ | $223$ | $33$ | $16$ | $121$ |
| $8$ | $255$ | $239$ | $17$ | $8$ | $57$ |
Being MDS gives the arithmetic you need for every practice item: $n - k = 2t$ check symbols correct $t$ symbol errors, or fill $n - k$ erasures (positions known to be damaged) — twice as many, because an erasure costs one symbol to correct and none to locate.
The reason storage and space links choose them is burst tolerance. A symbol error is one damaged symbol however many of its $m$ bits are wrong, so a run of consecutive bad bits ruins few symbols: a burst of $m(t - 1) + 1$ bits touches at most $t$ symbols and is corrected in full. With $8$-bit symbols and $t = 16$, that is $121$ consecutive bits. Interleaving several codewords stretches that further, which is how a compact disc survives a scratch across about $4000$ bits, and how the Voyager probes sent pictures home.
Common mistakes
Bytes, $m = 8$; the compact disc uses shortened RS codes $[32, 28]$ and $[28, 24]$ over $\text{GF}(256)$, each with $n - k = 4$, so $d = 5$ and $t = 2$.
MDS: four check bytes, two corrected.
With interleaving between the two codes, a scratch destroying about $4000$ consecutive bits is repaired: the burst is spread over many blocks, each seeing only a couple of bad symbols.
Symbols plus interleaving beat bursts.
Codewords are evaluations of polynomials of degree $< k$; the difference of two is a nonzero polynomial of degree $< k$ with at most $k - 1$ roots.
So two codewords agree in at most $k - 1$ of the $n$ positions and differ in at least $n - k + 1$: Singleton with equality, MDS.
$m = 4$, so $n = 2^4 - 1 = 15$ symbols per block.
$t = 3$ needs $2t = 6$ check symbols, so $k = 15 - 6 = 9$ and $d = 7$.
Check with Singleton: $d = n - k + 1 = 15 - 9 + 1 = 7$.
A $[15, 9]$ code over nibbles, correcting any three symbol errors or any burst of $4 \cdot 2 + 1 = 9$ bits.
Bytes, $m = 8$; the disc uses shortened codes $[32, 28]$ and $[28, 24]$, each with four check symbols.
Four check symbols correct $t = 2$ errors, or fill four erasures — and the first decoder tells the second where the damage is, so the second works with erasures.
With interleaving between the two codes, damage spread over about $4000$ consecutive bits is spread thinly across many codewords and repaired.
$m = 4$, $n = 15$, $n - k = 6$, so $k = 9$, $d = 7$.
Bursts of up to $4 \cdot 2 + 1 = 9$ bits are always corrected.
A Reed-Solomon code over $\text{GF}(2^{8})$ has full length $n = 2^{8} - 1$ and is designed to correct $4$ symbol errors. What is its dimension $k$?
Computed value: answer
A Reed-Solomon code has $n = 31$ and $k = 27$ over $\text{GF}(2^{5})$. How many symbol errors does it correct?
Computed value: answer
A Reed-Solomon code with $6$-bit symbols corrects $11$ symbol errors. What is the longest burst of consecutive bit errors it is guaranteed to correct?
Computed value: answer
A Reed-Solomon code over $\text{GF}(2^{8})$ has full length $n = 2^{8} - 1$ and is designed to correct $3$ symbol errors. What is its dimension $k$?
Computed value: answer
Why are Reed-Solomon codes the standard choice for storage media and deep-space links?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A Reed-Solomon code has $n = 127$ and $k = 99$ over $\text{GF}(2^{7})$. How many symbol errors does it correct?
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: RS over $\text{GF}(16)$ correcting $3$ symbol errors, step 2