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

  • Buried in cloud files? We can help with Spring cleaning!

    Whether you use Dropbox, Drive, G-Suite, OneDrive, Gmail, Slack, Notion, or all of the above, Dokkio will organize your files for you. Try Dokkio (from the makers of PBworks) for free today.

  • Dokkio (from the makers of PBworks) was #2 on Product Hunt! Check out what people are saying by clicking here.

View
 

Scribe Notes 6_1

Page history last edited by Shiney Wanrong TANG 10 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 :

 Formula

 

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.

Formula

Define the error locator polynomial Formula as

Formula

The zeros of Formula are the reciprocals Formula:

Formula

 

It can be simplify to

Formula

 

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

Formula

 

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.