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

• Whenever you search in PBworks, Dokkio Sidebar (from the makers of PBworks) will run the same search in your Drive, Dropbox, OneDrive, Gmail, and Slack. Now you can find what you're looking for wherever it lives. Try Dokkio Sidebar for free.

View

# Scribe Notes 6_1

last edited by 11 years, 2 months ago

## 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.