Links und Funktionen
Sprachumschaltung

Navigationspfad
You are here: Home / Teaching / Winter 2016/17 / Coding Theory / coding-cs16-06


Inhaltsbereich

coding-cs16-06

Plain Text icon coding-cs16-06.txt — Plain Text, 3 KB (3149 bytes)

File contents

Reed Solomon
============

Reed Solomon
------------

Galois Field GF(q)

Message c(x) polynominal = sum_i^n c_i x^i

information u_i = u_0 ... u_{n-1}
v_i = c(u_i)
sent message: v_0 ... v_{n-1}

deg c(x) < m

n support u_0 ... u_{n-1}
c -> (c(u_0) ... c(u_{n-1})) code word

RS(m,n) = { (v_0 ... v_{n-1} | exists c(x) with deg c < m: v_i = c(u_i) }

c!=0 => c(x)==0 at most at m-1 values of x

minimum distance: d = n-m+1

If m-n is d = 2e+1, then (n-m)/2 errors are correctable

Given now the received word: y_0 ... y_{n-1}

There exitsts c(x) with deg c < m 
such that c(u_i)!=y_i at at most (n-m)/2 instances of i.

Task: find c!

Possible solution:

Find polynomials f(x) and g(x) such that 
(*) 	g(u_i) y_i = f(u_i)
and 
deg f - deg g = m-1
deg f + deg g + 2 > n

Assume free coefficients for f and g. 
There are deg f + 1 + deg g + 1 > n of them.
Consequently, (*) n homogenous equations, have a non-trivial solution.

c(x) = f(x) / g(x)

Proof: polynomials which are equal at "many" 
positions (support points), are equal.

y(x) = v(x) + e(x)
and e(x) = sum_{i:E_n} lambda_i x^i
errors at position i

Example: e(x) = x^3 + 5*x^4

g(x)*c(c) + e(x), 
e(x) and g(x) are known.
f(x) = g(x)*c(x)
deg(f-g) = m-1
deg(f+g) = n+1

Code words: value tables of polynomial c at n support points 
of a polynomial, deg c < m
assume: n-m even
m numbers --> n numbers ==> minimum distance n-m+1

----------------------------------------------------

Received word: y_0 .... y_{n-1}
Determine f(x) and g(x)
What are the degrees of f and g?

1+deg(f)+1+deg(g) = n+1
  deg(f)  -deg(g) = m-1
-----------------------
  deg(f)  +deg(g) = n-1
  deg(f)  -deg(g) = m-1
-----------------------
deg(f) = (n-m)/2 + m-1
deg(g) = (n-m)/2

(I) g(u_i) * y_i = f(u_i) for all i=0...n-1
    c(x) = f(x)/g(x)
(II) if y_i = c_0(u_i) for at least n-(n-m)/2 support points of i,
then c(x) = c_0(x)

Proof:
(I+II) g(u_i)*c_0(u_i) = f(u_i) for at least n-(n-m)/2 of i

That means: g(x)*c_0(x) and f(x) are equal at n-(n-m)/2 positions.
And we know that n-(n-m)/2 > deg(f)
Consequently: g(x)*c_0(x) = f(x)

Example:
--------

field is real numbers
m=2, n=4
c(x) = 1+x
c = (1,1)

u_0 = 0, u_1 = 1, u_2 = -1, u_3 = 2

v_0 = 1, v_1 = 2, v_2 = 0, v_3 = 3 
send code word: 1,2,0,3

received code word: 1,2,0,0 (error in last number!)
y_0 = 1, y_1 = 2, y_2 = 0, y_3 = 0

Find f of deg(f)= (n-m)/2+m-1 = 2
Find g of deg(g)= (n-m)/2 = 1, such that
g(u_i)*y_i = f(u_i), i.e.:


g(0)*1=f(0)
g(1)*2=f(1)
g(-1)*0=f(-1)
g(2)*0=f(2)

g(x) = g_0 + g_1*x
f(x) = f_0 + f_1*x + f_2*x^2

g_0 = f_0
2*(g_0+g_1) = f_0 + f_1 + f_2
f_0 - f_1 + f_2 = 0
f_0 + 2*f_1 + 4*f_2 = 0

f_0 = 1, f_1 = 0.5, f_2 = -0.5
g_0 = 1, g_1 = -0.5

Consequently:
f(x) = 1 + 0.5*x - 0.5*x^2
g(x) = 1 - 0.5*x

f/g = x+1

original message. :)

--------------------------------------------------------------

Why is this working?

g(x)*c(x) and f(x) are polynomials of degree of at most (n-m)/2+m-1
and they agree at many, i.e. n-(n-m)/2, positions, at u_i

g(u_i)*c(u_i) = g(u_i)*v_i
f(u_i) = g(u_i)*y_i

It holds that 
n - (n-m)/2 > (n-m)/2 + m - 1
Consequenty, the polynomials are equal.
g(x)*c(x) = f(x) or c(x) = f(x)/g(x)

Document Actions


Funktionsleiste