• 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!

View

# Scribe Notes 6_1

last edited by 12 years 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.