*[Lectures scribed by Eric Blais]*

[The notes are also available in pdf format on the course webpage. Unless there is some explicit demand for it, I suspect that these might be the *last set* of notes for this course that I make available in wordpress html format.]

In this lecture, we begin the algorithmic component of the course by introducing some explicit families of good algebraic codes. We begin by looking at Reed-Solomon codes.

**1. Reed-Solomon codes **

Reed-Solomon codes are a family of codes defined over large fields as follows.

**Definition 1 (Reed-Solomon codes)** * For integers , a field of size , and a set , we define the Reed-Solomon code *

* *

A natural interpretation of the code is via its encoding map. To encode a message , we interpret the message as the polynomial

We then evaluate the polynomial at the points to get the codeword corresponding to .

To evaluate the polynomial on the points , we multiply the message vector on the left by the Vandermonde matrix

The matrix is a generator matrix for , so we immediately obtain that Reed-Solomon codes are linear codes over .

** 1.1. Properties of the code **

Let’s now examine the parameters of the above Reed-Solomon code. The block length of the code is clearly . As we will see, the code has minimum distance . This also means that the encoding map is injective and therefore the code has dimension equal to .

The key to establishing the minimum distance of Reed-Solomon codes is the `degree mantra’ that we saw in the previous lecture: *A non-zero polynomial of degree with coefficients from a field has at most roots in .*

**Theorem 2** * The Reed-Solomon code has distance . *

*Proof:* Since is a linear code, to prove the theorem it suffices to show that any non-zero codeword has Hamming weight at least .

Let . The polynomial is a non-zero polynomial of degree at most . So by our degree mantra, has at most roots, which implies that has at most zeros.

By the Singleton bound, the distance cannot exceed , and therefore must equal . The upper bound on distance can also be seen by noting that the codeword corresponding to the polynomial has Hamming weight exactly .

Note that the minimum distance of Reed-Solomon codes meets the Singleton bound. This is quite interesting: Reed-Solomon codes are a simple, natural family of codes based only on univariate polynomials, and yet their rate is optimal.

In our definition above, we have presented Reed-Solomon codes in the most general setting, where can be any arbitrary subset of of size . This presentation highlights the flexibility of Reed-Solomon codes. In practice, however, there are two common choices of used to instantiate Reed-Solomon codes:

- Take , or
- Take to be the set of non-zero elements in .

These two choices attain the best possible trade-off between the field size and the block length.

** 1.2. Alternative characterization **

We presented Reed-Solomon codes from an encoding point of view. It is also possible to look at these codes from the “parity-check” point of view. This approach is used in many textbooks, and leads to the following characterization of Reed-Solomon codes.

**Theorem 3 (Parity-check characterization)** * For integers , a field of size , a primitive element , and the set , the Reed-Solomon code over with evaluation set is given by *

* *

In other words, Theorem 3 states that the codewords of the Reed-Solomon code with evaluation points correspond to the polynomials of degree that vanish at the points .

The characterization of Reed-Solomon codes in Theorem 3 has the same dimension as the code obtained with our original definition; to complete the proof of Theorem 3, we only need to check that every codeword obtained in Definition 1 satisfies the parity-check condition (1).

**Exercise 1** * Complete the proof of Theorem 3. *

*(Hint: The proof uses the fact that for every in , .) *

(more…)