Reed–Solomon Codes

Encode a message as a polynomial, sample it, and recover from errors.

The idea

A Reed–Solomon code encodes a message as a polynomial over a finite field and transmits the polynomial's values at fixed sample points.

The construction rests on one fact: a polynomial of degree at most $k-1$ is determined by its values at any $k$ distinct points — two points determine a line, three a parabola. Values at more than $k$ points are therefore redundant, and that redundancy is what the receiver spends on correcting errors.

Fix a finite field $\mathbb{F}_q$ and choose $n$ distinct points $\alpha_1, \ldots, \alpha_n$ in it, so $n \le q$. Read a message of $k$ symbols as the coefficients of $m(x) = m_0 + m_1 x + \cdots + m_{k-1} x^{k-1},$ and transmit its values $\bigl(m(\alpha_1), \ldots, m(\alpha_n)\bigr)$ as the codeword. Any $k$ of the $n$ values recover $m(x)$ by interpolation.

The code has length $n$, dimension $k$, and minimum distance $d = n - k + 1$; we abbreviate the three parameters as $[n, k, d]$. The distance is exact: two distinct messages give polynomials whose difference is nonzero of degree at most $k-1$, so it vanishes at no more than $k-1$ sample points, and the two codewords differ in at least $n - k + 1$ coordinates. By the Singleton bound, no code of length $n$ and dimension $k$ has larger minimum distance, so Reed–Solomon codes meet that bound with equality.

Ways to work on it

• Walkthrough. The evaluation-map construction and why d = n - k + 1.
• Practice. Compute the distance or correction radius of an RS code.
• Hardest. Dimension a code for a target error count, and compare erasures.

Not sure where to start? Take the ten-question placement test.