4301.sagews

Cyclic Codes

A right cyclic shift is where each entry of a vector is shifted one place to the right, and the last entry is shifted to the first position.

Right cyclic shift $\sigma:\mathbb{F}_q^n\rightarrow \mathbb{F}_q^n$

            $v=a_0a_1...a_{n-1}\mapsto \sigma(v)=a_{n-1}a_0...a_{n-2}$

  An linear code is CYCLIC if $\sigma(C)\subseteq C$, that is, for all $v\in C$, the right cyclic shift of $v$ is also in $C$.

Polynomials modulo ($1-x^n$)

We can represent codewords of length $n$ by polynomials of degree $n-1$.

Polynomial Representation  $\pi:\mathbb{F}_q^n\rightarrow \mathbb{F}_q[x]/(1-x^n)$

$v=a_0a_1...a_{n-1} \mapsto \pi(v)=a_0+a_1x+a_2x^2+...+a_{n-1}x^{n-1}$.

Algebra  Addition is as usual. We can now also multiply words (modulo $1-x^n$).

Example:

$\mathbb{F}_2[x]/(1-x^3)=\{0,1,x,x^2,1+x,1+x^2,x+x^2,1+x+x^2\}$

Ex 1 Let $v=101$ and $w=010$, then $\pi(v)\pi(w)=(1+x^2)(x)=x+x^3\equiv 1+x \pmod{1-x^3}$

Ex 2 Let $v=101$ and $w=111$, then $\pi(v)\pi(w)=(1+x^2)(1+x+x^2)\equiv 0 \pmod{1-x^3}$

We have now defined a multiplication operation on codewords. This is not an inner product.

In Ex 2 vw=0, and we can see that we now have zero divisors.

A cyclic shift corresponds to multiplication by x.

$\pi(\sigma(v))=x\pi(v)$

Classifying Cyclic Codes

Theorem A linear code $C$ is cyclic if and only if for every codeword $v\in C$ and every word $w\in \mathbb{F}_q^n$, we have $wv \in C$.

Theorem A linear code $C$ is cyclic if and only if  $f\pi(v)\in\pi(C)$ for every $v\in C$ and every $f\in\mathbb{F}_q[x]$.

                       $C$ cyclic code over $\mathbb{F}_q \longleftrightarrow \pi(C)$ is an ideal of $\mathbb{F}_q[x]/(1-x^n)$.

Creating Cyclic codes

To create a cyclic code as words we can do the following:

Let $v\in \mathbb{F}_q^n$ and let $S=\{v,\sigma(v),\sigma^2(v),...,\sigma^{n-1}v\}$.

In general the elements of $S$ are not all distinct. Then $C=\langle S\rangle$ is the cyclic code genreated by $v$.

To create a cyclic code as polynomials:

$S=\{\pi(v),x\pi(v),x^2\pi(v),...,x^{n-1}\pi(v)\}$.

The codewords are exactly the polynomial multiples of $\pi(v)$.

$C=\langle S \rangle$ is the cyclic code generated by $\pi(v)$.

The word $v$ or its polynomial version $\pi(v)$ is called a generator for $C$.

There can be several generators for a code, but we are concerned with finding the generator of $C$.

Theorem

Let $C$ be a cyclic code over $\mathbb{F}_q$. There exists a unique monic polynomial in $C$ with minimal degree.

This polynomial $g$ is called the generator of $C$.

Theorem

$C=\langle g \rangle$.

Proof: ($\supseteq$) is obvious. Now let $f\in C$. By the Division Algorithm, $f=gq+r$ with deg$(r)<$deg$(g)$, but $r=f-gq \in C, \rightarrow\leftarrow$

So $r=0$ and $f$ is a multiple of $g$ so $f\in\langle g \rangle$.

Theorem

If $f$ is a generator for a cyclic code of length $n$, then $g:=\gcd(f,1-x^n)$ is the generator for the code.

Proof: Since $g\equiv f \pmod{1-x^n}$ then $\langle g \rangle \subseteq \langle f \rangle=C$.

         Since $g$ divides $f$, $\langle f \rangle \subseteq \langle g \rangle$. Now assume $h$ is the generator polynomial of $C$.

         Then $g$ divides $H$, and deg$(g)<$deg$(h)$. Hence by minimality, $g=h$.
Theorem

There is a one-to-one correspondence between cyclic codes of length $n$ and the monic divisors of $(1-x^n)$ in $\mathbb{F}_q$.

If $1-x^n=\prod_{i=1}^r p_i^{e_i}$ in $\mathbb{F}_q$ is the factorization into irreducible monic polynomials, then there are $\prod_{i=1}^r (e_i+1)$ different cyclic codes over $\mathbb{F}_q$.

Properites of Cyclic Codes

1. If the generator polynomial for a cyclic code $C$ is of degree $r$, then the dimension of $C$ is $n-r$.

2. If $g$ is the generator polynomial for a code $C$ of degree $r$, the set $S=\{g,xg,x^2g,...,x^{k-1}g\}$ is linearly indedependent where $k=n-r$. In fact, it is a basis for $C$.

3. A cyclic code $C$ of length $n$ and dimension $k$ exists if and only if there is a polynomial $g$ of degree $n-k$ which divides $(1-x^n)$.

4. A generator matrix for $C$ is $\left| \begin{matrix} g\\xg\\x^2g\\ \vdots \\ x^{k-1}g \end{matrix}\right|$

Constructing Cyclic Codes From Polynomials in Sage

It is easy to construct cyclic codes in Sage. First you construct the polynomial ring over the field you are working in. Then you name your generator polynomial, and finally, you construct your code.

P.<x>=PolynomialRing(GF(3),"x")
g=x-1
C=CyclicCodeFromGeneratingPolynomial(4,g);C

Linear code of length 4, dimension 3 over Finite Field of size 3

P.<x>=PolynomialRing(GF(4,"a"),"x")
g=x^3+1
C=CyclicCodeFromGeneratingPolynomial(9,g);C

Linear code of length 9, dimension 6 over Finite Field in a of size 2^2

You can still get a generator matrix for your code, but Sage will give it to you in terms of words and not polynomials. You can easily convert back and forth however.

C.gen_mat()

[1 0 0 1 0 0 0 0 0] [0 1 0 0 1 0 0 0 0] [0 0 1 0 0 1 0 0 0] [0 0 0 1 0 0 1 0 0] [0 0 0 0 1 0 0 1 0] [0 0 0 0 0 1 0 0 1]

If your generator does not divide $1-x^n$ where $n$ is the length of your code, Sage will find the gcd of your generator and $1-x^n$, which is one. Consequently, Sage will use 1 as the generator polynomial. To avoid this,  add the parameter  ignore=false. Then if your generator does not divide $1-x^n$ you will get the following error message:

P.<x>=PolynomialRing(GF(4,"a"),"x")
g=x
C=CyclicCodeFromGeneratingPolynomial(5,g,ignore=false);C

Traceback (most recent call last): File "<stdin>", line 1, in <module> File "_sage_input_3.py", line 10, in <module> exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("UC48eD49UG9seW5vbWlhbFJpbmcoR0YoNCwiYSIpLCJ4IikKZz14CkM9Q3ljbGljQ29kZUZyb21HZW5lcmF0aW5nUG9seW5vbWlhbCg1LGcsaWdub3JlPWZhbHNlKTtD"),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single') File "", line 1, in <module> File "/tmp/tmp3dKpSX/___code___.py", line 5, in <module> exec compile(u'C=CyclicCodeFromGeneratingPolynomial(_sage_const_5 ,g,ignore=false);C' + '\n', '', 'single') File "", line 1, in <module> File "/sagenb/sage_install/sage-4.8-sage.math.washington.edu-x86_64-Linux/local/lib/python2.6/site-packages/sage/coding/code_constructions.py", line 676, in CyclicCodeFromGeneratingPolynomial raise ValueError, '%s must divide x^%s - 1'%(g,n) ValueError: x must divide x^5 - 1

P.<x>=PolynomialRing(GF(4,"a"),"x")
g=x^3+1
C=CyclicCodeFromGeneratingPolynomial(9,g,ignore=false);C

Linear code of length 9, dimension 6 over Finite Field in a of size 2^2

You can also determine if a poynomial divides $1-x^n$ by dividing. If you get a quotient then it is divisible. If Sage presents the answer as a fraction, then it isn't. You must have already defined your polynomial ring. Sage will also factor for you.

(1-x^9)/(1+x^3)

x^6 + x^3 + 1

(1-x^5)/x

(x^5 + 1)/x

P.<x>=PolynomialRing(GF(3),"x")
(x^8-1).factor()

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

To find all of the generators of cyclic codes over $\mathbb{F}_q$ of length $n$, you need to the factorization of $1-x^n$ over $\mathbb{F}_q$. This can be done in the way that we did it when studying minimal polynomials. On pages 140 and 141 of the text, there are tables of the factorization of $x^n-1$ for $1\leq n \leq 10$ over $\mathbb{F}_2$ and $\mathbb{F}_3$.

Encoding

Non-systematic encoding is an easier method of encoding than systematic encoding, but systematic encoding makes decoding easier.

Non-systematic Encoding

Generator Polynomial $g$ of degree $r$, for an $[n,k=n-r]$-code $C$.

$G=\left|\begin{matrix} g\\xg\\x^2g\\ \vdots \\ x^{k-1}g \end{matrix} \right|$.

Let $m$ be the original message  of length $k$, which is a polynomial of degree $\leq k-1$.

Encoding $v=mG$:   $v=m\cdot g \pmod{1-x^n}$.

This is easy encoding, but can you see $m$ or $H$?

Systematic Encoding

We build a generator matrix in the form $g=[R|I_k]$.

Let $r_i\equiv x^{n-k+i} \pmod{g}$ for $i=0...k-1$.

Then $-r_i+x^{n-k+i}\in C$. In fact, they are linearly independent.

$G'=\left|\begin{matrix} -r_0 &+& x^{n-k}\\-r_1& +& x^{n-k+1}\\ \cdots &&\cdots\\-r_{k-1}&+&x^{n-1} \end{matrix}\right|$.

$G'=[R|I_k]$ where $-r_i$ are the rows of $R$.

The original message $m$ is of length $k$, and is a polynomial of degree $\leq k-1$.

Encoding $v=mG'$:  $v=qg=-r+m\cdot x^{n-k}$. $r$ is the remainder when dividing $mx^{n-k}$ by $g$.

Advantage: Original message $m$ appears on the last $k$ positions of $v$.

Example:

Let $C=\langle 2+x+2x^3+x^4\rangle \subseteq \mathbb{F}_3^8$.

$g=2+x+2x^3+x^4$

  $r=4$, so to make the generator matrix for the code in symmetric form, we need to compute the remainders when $x^4$, $x^5$, $x^6$ and $x^7$ are divided by $g$.

For that purpose, we can set up a polynomial ring modulo $g$.

R.<u> = QuotientRing(GF(3)[x], GF(3)[x].ideal(x^4+2*x^3+x+2)); R

Univariate Quotient Polynomial Ring in u over Finite Field of size 3 with modulus x^4 + 2*x^3 + x + 2

u^4,u^5,u^6,u^7

(u^3 + 2*u + 1, u^3 + 2*u^2 + 1, 1, u)

To make the generator matrix for the code in symmetric form,

the rows , of the matrix are $-r_i +x^{n-k+i}$ for $i \in \{0,...,k-1\}$.  as shown above.

Thus they are

$2+x+2x^3+x^4= 2  1 0 2 1 0 0 0$

$2+x^2+2x^3+x^5=2 0 1 1 0 1 0 0$

$2+x^6=1 0 0 0 0 0 1 0$

$2x+x^7=0 2 0 0 0 0 0 1$

M=MatrixSpace(GF(3),4,8)
G=M([[2,1,0,2,1,0,0,0],[2,0,1,1,0,1,0,0],[1,0,0,0,0,0,1,0],[0,2,0,0,0,0,0,1]]);G

[2 1 0 2 1 0 0 0] [2 0 1 1 0 1 0 0] [1 0 0 0 0 0 1 0] [0 2 0 0 0 0 0 1]

So to encode the message 2010, we mulitply the message by $G$ and get:

V=VectorSpace(GF(3),4)
m=V([2,0,1,0])
m*G

(2, 2, 0, 1, 2, 0, 1, 0)

Note that the message is on the last four digits.

Now to encode via polynomials:

R.<u> = QuotientRing(GF(3)[x], GF(3)[x].ideal(1-x^8)); R

(2+u^2)*(2+u+2*u^3+u^4)

u^6 + 2*u^5 + 2*u^4 + 2*u^3 + 2*u^2 + 2*u + 1

So the encoded message is 1 2 2 2 2 2 1 0.

Homework #6

1. Describe all of the ternary cyclic codes of length 4 by giving its generator polynomial and its parameters.

2. Assume $C_1$ and $C_2$ are cyclic codes of the same length with generator polynomials $g_1(x)$, $g_2(x)$ respectively. Show that $C_1\subseteq C_2$ if and only if $g_2(x)$ divides $g_1(x)$.

3. Problem 7.1

4. Problem 7.6

5. Problem 7.9

6. Problem 7.13

7. Problem 7.23

If you are taking Math 527 then do Problem 7.24.

If you are not taking Math 527 you can do Problem 7.24 for extra credit.