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.
Comments (0)
You don't have permission to comment on this page.