2626.sagews

Our goal is to check if our RS(255,223) is working as it should (at the time of writing, it isn't \right).  In order to do so, it is ideal to write the software in a fashion that allows us to implement more than just the galois field of 256 elements.  Thus, we generalize must generalize $GF(2^n)$ and work with a smaller size of elements to solve problems by hand first.  We use the Galois Field $$\frac{GF(2^3)}{x^3+x+1}$$ to give a basis of all binary triples (e.g. 000, 001, 010,...)

G.<alpha> = GF(2^3)
for i,x in enumerate(G): print i,x

0 0 1 alpha 2 alpha^2 3 alpha + 1 4 alpha^2 + alpha 5 alpha^2 + alpha + 1 6 alpha^2 + 1 7 1

Suppose we wish to transmit a message of length 5 symbols using RS(7,5).  This means that we will have 2 parity symbols (or the ability to correct 1 error). To implement the encoder of reed solomon we use what is called a polynomial ring using our galois field, $\frac{GF(2^3)}{x^3+x+1}$.  Think of this as the set of all polynomials with the coefficients described from above.

P.<x> = PolynomialRing(G,'x')
P

Univariate Polynomial Ring in x over Finite Field in alpha of size 2^3

1. Now suppose the five symbol message we wish to encode is ($$\alpha , \alpha^7 , \alpha^2 , \alpha^3 , \alpha^5$$) ($\alpha$, $\alpha^7 , \alpha^2, \alpha^3 , \alpha^5$ ).  We place this into a polynomial:

f(x) = alpha * x^4 + alpha^7 * x^3 + alpha^2 * x^2 + alpha^3 * x + alpha^5
f(x)

alpha*x^4 + x^3 + alpha^2*x^2 + (alpha + 1)*x + alpha^2 + alpha + 1

Notice how the high degree alphas simplify to their corresponding coefficients in the table above.  The next step is to multiply $x^2*f(x)$.  $x^2$ comes from the fact that we have two parity symbols to consider for transmission (this will come later on).   In general would would multiply $f(x)$ by $x^{\textrm{quantity of parity symbols}}$.  In effect this is left shift the polynomial so we can make room for our parity bits for transmission later on. The code below is $L(x) = x^2 \cdot f(x)$, only written out term by term.

L(x) = alpha * x^6 + alpha^7 * x^5 + alpha^2 * x^4 + alpha^3 * x^3 + alpha^5 * x^2
L(x)

alpha*x^6 + x^5 + alpha^2*x^4 + (alpha + 1)*x^3 + (alpha^2 + alpha + 1)*x^2

 

The next step is to create a generator function.  The purpose of the generator function is to create the parity bits.  While it can be arbitrarily polynomial from which we constructed earlier, tradition is to have the roots of the generator polynomial to be increasing powers of $\alpha$ (e.g. $\alpha,\alpha^2,\alpha^3$,...).  Since we have only two parity bits we will construct a 2 degree polynomial (having 2 roots):

    

    We first show the expansion of our polynomial,g(x), as $(x + \alpha)\cdot \left(x+\alpha^2 \right)$

    Then we write $g(x) = x^2 + \alpha^4 x + \alpha^3$

 

The next step is to create a generator function.  The purpose of the generator function is to create the parity bits.  While it can be arbitrarily polynomial from which we constructed earlier, tradition is to have the roots of the generator polynomial to be increasing powers of $\alpha$ (e.g. $\alpha,\alpha^2,\alpha^3$,...).  Since we have only two parity bits we will construct a 2 degree polynomial (having 2 roots):

 

    We first show the expansion of our polynomial,g(x), as $(x + \alpha)\cdot \left(x+\alpha^2 \right)$

    Then we write $g(x) = x^2 + \alpha^4 x + \alpha^3$

 

 

expand((x + alpha) * (x+alpha^2))

x^2 + (alpha^2 + alpha)*x + alpha + 1

g(x) = x^2 + (alpha^2 + alpha)*x + alpha + 1

Now our next step is to find the L(x) mod g(x)

(alpha * x^6 + alpha^7 * x^5 + alpha^2 * x^4 + alpha^3 * x^3 + alpha^5 * x^2)%(x^2 + (alpha^2 + alpha)*x + alpha + 1)

Traceback (most recent call last): File "<stdin>", line 1, in <module> File "_sage_input_9.py", line 10, in <module> exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("KGFscGhhICogeF42ICsgYWxwaGFeNyAqIHheNSArIGFscGhhXjIgKiB4XjQgKyBhbHBoYV4zICogeF4zICsgYWxwaGFeNSAqIHheMiklKHheMiArIChhbHBoYV4yICsgYWxwaGEpKnggKyBhbHBoYSArIDEp"),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single') File "", line 1, in <module> File "/tmp/tmpBMUmTI/___code___.py", line 3, in <module> exec compile(u'(alpha * x**_sage_const_6 + alpha**_sage_const_7 * x**_sage_const_5 + alpha**_sage_const_2 * x**_sage_const_4 + alpha**_sage_const_3 * x**_sage_const_3 + alpha**_sage_const_5 * x**_sage_const_2 )%(x**_sage_const_2 + (alpha**_sage_const_2 + alpha)*x + alpha + _sage_const_1 )' + '\n', '', 'single') File "", line 1, in <module> TypeError: unsupported operand type(s) for %: 'sage.symbolic.expression.Expression' and 'sage.symbolic.expression.Expression'

Effectively, we have found the remainder of $\frac{L(x)}{g(x)}$.  Now we can add our remainder, $\alpha^4x$, to L(x).  This result is our encoded polynomial, ready for transmission.

T(x) = alpha * x^6 + alpha^7 * x^5 + alpha^2 * x^4 + alpha^3 * x^3 + alpha^5 * x^2 + (alpha^2 + alpha)*x

 

A good way to check if our encoded message is what we want, we can evaluate our T(x) at the roots of the generator polynomial, $\alpha$ and $\alpha^2$.  If they are both equal to zero, we know that our T(x) is good!  This is because $L(X) = q(x)\cdot g(x) + r(x)$ where r(x) is our remainder and q(x) is the quotient.  Thus adding r(x) to both sides yields this:

    $\begin{array}{rcl}L(x) & = & q(x) \cdot g(x) + 2 r(x)\\L(x) + r(x)&=& q(x) \cdot g(x)\\L(x) + r(x)&=&T(x)\end{array}$

    The reason why $2 r(x)=0$ is that when we add, we are really performing the XOR operation.  XOR'ing anything twice is zero. Consider the right hand side of the second equation.  When we evaluate g(x) at our roots, we'll get zero.  This implies that the left hand side, $L(x) + r(x) = 0$, is also zero at our roots, namely $\alpha$ and $\alpha^2$:

A good way to check if our encoded message is what we want, we can evaluate our T(x) at the roots of the generator polynomial, $\alpha$ and $\alpha^2$.  If they are both equal to zero, we know that our T(x) is good!  This is because $$L(X) = q(x)\cdot g(x) + r(x)$$ where r(x) is our remainder and q(x) is the quotient.  Thus adding r(x) to both sides yields this:

    $$\begin{array}{rcl}L(x) & = & q(x) \cdot g(x) + 2 r(x)\\L(x) + r(x)&=& q(x) \cdot g(x)\\L(x) + r(x)&=&T(x)\end{array}$$

    The reason why $2 r(x)=0$ is that when we add, we are really performing the XOR operation.  XOR'ing anything twice is zero. Consider the right hand side of the second equation.  When we evaluate g(x) at our roots, we'll get zero.  This implies that the left hand side, $L(x) + r(x) = 0$, is also zero at our roots, namely $\alpha$ and $\alpha^2$:

 

T(alpha)

0

T(alpha^2)

0

Since the roots evaluate to zero, we know that our encoding is good to go!.  The 7 symbol message we will send is: $\left(\alpha , \alpha^7 , \alpha^2, \alpha^3 , \alpha^5, \alpha^4, 0 \right)$.