03.4 Reed Solomon Codes

Not suprisingly, we can have the notion of polynomials in finite fields.

We associate each coefficient to a vector’s coordinate, so $\vec{u}$, with $P(x)=u_1+u_{2}x+\cdots +u_n{x}^{n-1}$

Langrage’s Interpolation Polynomials

Is there a polynomial of degree $k-1$ that intersects over a bunch of other polynomials at $y_i$

Example

We fix a field $\mathbb{F}$ and distinct field elements $a_1,a_2,a_3$ and $y_1,y_2,y_3$ We seek a polynomial of degree $\le 2$ and coefficients in $\mathbb{F}$, such that $P(a_i)=y_i$

We can suppose that a polynomial $Q_1(x)$ of degree $\le 2$ such that

$$Q_1(x)=\{\begin{array}{ll}1,& x=a_1\\ 0,& x=a_i\ne a_1\end{array}$$

We suppose that $Q_2$ and $Q_3$ behave similarly

The desired polynomial is given by $P(x)=y_1{Q}_1(x)+y_2{Q}_2(x)+y_3{Q}_3$

We find $Q_1(x)$ by knowing that $(x-a_2)(x-a_3)=0$ at all $a_i$ except $a_1$

Hence $Q_1(x)=\frac{(x-a_2)(x-a_3)}{(a_1-a_2)(a_1-a_3)}$

We can find $Q_2(x)$ and $Q_3(x)$ similarly

We can proceed similarly for any field and any integer $k$

Roots of Polynomials

Theorem

Let $P(x)$ be a polynomial of degree at most $k-1$ over a field. If $P(x)\ne 0$ then the number of distinct roots is at most $k-1$

Reed Solomon

Code construction

1. We choose a finite field $\mathbb{F}$ and integers $k,n$ such that $0<k\le n\le q$, with $q=\text{card}(\mathbb{F})$
2. We choose $n$ distinct elements as $a_i\in \mathbb{F}$
3. The codewords are defined by $\vec{u}\mapsto \vec{c}=(P_{\vec{u}}(a_1),\dots ,P_{\vec{u}}(a_n))$
4. We have a block code of length $n$ over $\mathbb{F}$

Reed-Solomon codes are linear

They satisfy singleton’s bound as MDS (so with equality)