• If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • You already know Dokkio is an AI-powered assistant to organize & manage your digital files & messages. Very soon, Dokkio will support Outlook as well as One Drive. Check it out today!


Scribe Notes 6_1

Page history last edited by Shiney Wanrong TANG 12 years, 6 months ago

5. Reed-Solomon code


Consider a code generated as follows. Let Formula be the sequence of source symbols. The polynomial Formula is of degree k-1 in the variable r, and the coefficient corresponding to Formula is Formula. 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 Formula, Formula, where H is n-k times n and x is n times 1.

Formula , see the figure as follows:

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


1. Proof of minimum distance

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

Suppose  Formula 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 Formula columns in matrix Formula, we cannot get a zero vector (any square of sub-matrix Formula is non-singular). This contradict to the setting of Formula.


2. Encode

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

We want to generate matrix Formula,

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

Hence, Formula , so Formula

This matrix also satisfies the capacity Formula.


3. Decode

We can reconstruct Formula efficiently as follows :



Let's make a reference to wiki:

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

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

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


Define the error locator polynomial Formula as


The zeros of Formula are the reciprocals Formula:



It can be simplify to



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



Consequently, if we have this relationship, we can figure out Formula , given that Formula , 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.