Back to Coding Theory
Back to notes

# Reed-Solomon Code

In this note, we introduce some basic properties of Reed-Solomon code and present a simple decoding algorithm.

## Definition and basic facts

Let $n$ denote the block length, prime power $q$ denote the alphabet size, $k$ denote the message length, and $d$ denote the minimum distance. Define the Reed-Solomon code as follows.

For integer $1\leq k<n\leq q$ and a set $S={\alpha_1,\dots,\alpha_n}\subseteq\mathbb{F}_q$, we define the Reed-Solomon code

$\text{RS}_{q,S}[n,k] := \{(p(\alpha_1),\dots,p(\alpha_n)):\ p\text{ is a polynomial of degree at most }k-1 \}.$

Intuitively, we think of the code of Reed-Solomon code as a low degree ($k-1$) polynomial and the codeword is the evaluation of the polynomial on set $S$ of size $n$. Thus, we have the following facts directly from the definition and the properties of polynomials.

• The rate is $1-k/n$.
• The minimum distance is $n-k+1$.
• This follows from the fact (“Degree Mantra”) that two distinct univariate degree $d$ polynomial intersect on at most $d$ points.

The good thing about Reed-Solomon code is that its rate achieves the Singleton bound, i.e., Reed-Solomon code has optimal rate. However, the alphabet size required is pretty large: $q>n$. Thus, many people have been worked hard to reduce the alphabet size of the Reed-Solomon code while preserving the optimality of code rate.

### Linear code characterization

Recall that there are three important issues in linear code: the generator matrix, the parity checking matrix, and the dual code. In the following, we consider a special case of Reed-Solomon code where $n=q$ and $S={0,1,2,\dots,q-1}$.

• The generator matrix of Reed-Solomon code

The generating matrix of Reed-Solomon code is simply the sumatrix of Vandermonde matrix of $S$ up to degree $k-1$. We denote the code as $\text{RS}_q[n,k]$.

• The parity checking matrix of Reed-Solomon code

From the generator matrix characterization of Reed-Solomon code, one can see that every codeword lie in the row space of $G$. Thus, to find the parity checking matrix, it is equivalent to find the perp of the row space of $G$. Thus, we need some properties from the Vandermonde matrix as follows. (Note that these properties hold when $n=q$)

Let $V_i$ denote the $i$th row of the Vandermonde matrix, then for any $i,j\in[n]$,

$% $

From the above lemma, we know that the first $n-k$ row of the Vandermonde matrix is perpendicular to $\text{RS}_q[n,k]$. As the dimension of $\text{RS}_q[n,k]$ is $k$ and the dimension of the universe is $n$, we conclude that the parity checking matrix of $\text{RS}_q[n,k]$ is

• The dual code of Reed-Solomon code

By the property of linear code, we know that the generator matrix of the dual code of $\text{RS}_q[n,k]$ is the transpose of the parity checking matrix of $\text{RS}_q[n,k]$. That is, the dual code of $\text{RS}_q[n,k]$ is $\text{RS}_q[n,n-k+1]$.

## Nice resources

• Book chapter by Madu Sudan, Venkatesan Guruswami, and Atri Rudra.
• Background in polynomials and finite fields.
• A very comprehensive introduction to Reed-Solomon code.
• A property of MDS codes.
• Nice exercises cover many useful properties of Reed-Solomon code and some variants.
• Lecture notes of an IT course at University of Wyoming.
• Short and self-contained.