# 24.9 Reed-Solomon Codes

The Reed-Solomon codes, constructed in 1960, are an example of BCH codes. Because they work well for certain types of errors, they have been used in spacecraft communications and in compact discs.

Let $\mathbf{F}$ be a finite field with $q$ elements and let $n=q-1$. A basic fact from the theory of finite fields is that $\mathbf{F}$ contains a primitive $n$th root of unity $\alpha $. Choose $d$ with $1\le d<n$ and let

This is a polynomial with coefficients in $\mathbf{F}$. It generates a BCH code $C$ over $\mathbf{F}$ of length $n$, called a **Reed-Solomon code**.

Since $g(\alpha )=\cdots =g({\alpha}^{d-1})=0$, the BCH bound implies that the minimum distance for $C$ is at least $d$. Since $g(X)$ is a polynomial of degree $d-1$, it has at most $d$ nonzero coefficients. Therefore, the codeword corresponding to the coefficients of $g(X)$ is a codeword of weight at most $d$. It follows that the minimum weight for $C$ is exactly $d$. The dimension of $C$ is $n-deg(g)=n+1-d$. Therefore, a Reed-Solomon code is a cyclic $[n\text{,}\text{}n+1-d\text{,}\text{}d]$ code.

The codewords in $C$ correspond to the polynomials

There are ${q}^{n-d+1}$ such polynomials $f(X)$ since there are $q$ choices for each of the $n-d+1$ coefficients of $f(X)$, and thus there are ${q}^{n-d+1}$ codewords in $C$. Therefore, a Reed-Solomon code is a MDS code, namely, one that makes the Singleton bound (Section 24.3) an equality.

# Example

Let $\mathbf{F}={\mathbf{Z}}_{7}=\{0\text{,}\text{}1\text{,}\text{}2\text{,}\text{}\dots \text{,}\text{}6\}$, the integers mod 7. Then $q=7$ and $n=q-1=6$. A primitive sixth root of unity $\alpha $ in $\mathbf{F}$ is the same as a primitive root mod 7 (see Section 3.7). We may take $\alpha =3$. Choose $d=4$. Then

The code has generating matrix

There are ${7}^{3}=343$ codewords in the code, obtained by taking all linear combinations mod 7 of the three rows of $G$. The minimum weight of the code is 4.

# Example

Let $\mathbf{F}=GF(4)=\{0\text{,}\text{}1\text{,}\text{}\omega \text{,}\text{}{\omega}^{2}\}$, which was introduced in Section 3.11. Then $\mathbf{F}$ has 4 elements, $n=q-1=3$, and $\alpha =\omega $. Choose $d=2$, so

The matrix

is a generating matrix for the code. The code contains all 16 linear combinations of the two rows of $G$, for example,

The minimum weight of the code is 2.

In many applications, errors are not randomly distributed. Instead, they occur in bursts. For example, in a CD, a scratch introduces errors in many adjacent bits. A burst of solar energy could have a similar effect on communications from a spacecraft. Reed-Solomon codes are useful in such situations.

For example, suppose we take $\mathbf{F}=GF({2}^{8})$. The elements of $\mathbf{F}$ are represented as bytes of eight bits each, as in Section 3.11. We have $n={2}^{8}-1=255$. Let $d=33$. The codewords are then vectors consisting of 255 bytes. There are 222 information bytes and 33 check bytes. These codewords are sent as strings of $8\times 255=2040$ binary bits. Disturbances in the transmission will corrupt some of these bits. However, in the case of bursts, these bits will often be in a small region of the transmitted string. If, for example, the corrupted bits all lie within a string of 121 ($=15\times 8+1$) consecutive bits, there can be errors in at most 16 bytes. Therefore, these errors can be corrected (because $16<d/2$). On the other hand, if there were 121 bit errors randomly distributed through the string of 2040 bits, numerous bytes would be corrupted, and correct decoding would not be possible. Therefore, the choice of code depends on the type of errors that are expected.