5. Reed-Solomon code

Consider a code generated as follows. Let be the sequence of source symbols. The polynomial is of degree k-1 in the variable r, and the coefficient corresponding to is . The n output symbols are chosen by evaluating this polynomial for n distinct values of r.

Choose a prim number q.

For all code in the codebook , , where H is n-k times n and x is n times 1.

, see the figure as follows:

where is a primitive root, and , by defining multiple to be (a*b)mod q.

1. Proof of minimum distance

Proof: all x in the above has  (minimum distance above )

Suppose  the different between any two code words is also a code word, applying they should have at least n-k+1 different location in code matrix. If we choose those n-k ones and all other are zeros, by combining columns in matrix , we cannot get a zero vector (any square of sub-matrix is non-singular). This contradict to the setting of .

2. Encode

 Any sub-matrix square of the parity check matrix must be invertible,  then we consider the following system:

We want to generate matrix ,

which satisfies . Then we get , since the equation is valid for arbitrary .

Hence, , so

This matrix also satisfies the capacity .

3. Decode

We can reconstruct efficiently as follows :

Let's make a reference to wiki:

For convenience, define the '''error locators''' '''' and '''error values''' '''' as:

Then the syndromes can be written in terms of the error locators and error values as

However, if the '''' were known (see below), then the syndrome equations provide a linear system of equations that can easily be solved for the '''' error values.

Define the error locator polynomial as

The zeros of are the reciprocals :

It can be simplify to

This yields a system of linear equations that can be solved for the coefficients of the error location polynomial:

Consequently, if we have this relationship, we can figure out , given that , we can find the primitive roots, given that primitive roots, finally we can get which locations are non-zero.