4114.sagews

Constructing Linear Codes

To construct linear codes, one must first construct the proper Matrix Space. The example that follows gives a name , $MS$, for the set of matrices with entries in $\mathbb{F}_3$ that have 4 rows and 9 columns.

MS=MatrixSpace(GF(3),4,9)

Now we can define the generator matrix. First, we are naming this matrix $M$ and saying that it belongs to $MS$, the matrix space defined above. We then list the rows of the matrix as vectors. These are our generating codewords.

M=MS([[1,0,2,1,0,0,0,2,1],[0,1,1,1,1,0,0,0,0],[0,0,1,2,1,0,0,0,2],[1,2,1,0,0,0,0,1,2]])

M

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

Finally, We construct our linear code $C$ with generator matrix $M$.

C=LinearCode(M)
C

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

We can get the generator matrix of the code with the command gen_mat()

C.gen_mat()

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

We can also construct linear codes over $\mathbb{F}_{p^m}$.

F.<x>=GF(2)[]
K.<a>=GF(8,name='a',modulus=1+x^2+x^3)
MS2=MatrixSpace(K,4,5)

G=MS2([[1,0,a,a+1,a],[0,1,a,a+1,a^2],[0,0,a,a+a^2,a],[0,0,0,a^2,a^2]])

C2=LinearCode(G)

C2

Linear code of length 5, dimension 4 over Finite Field in a of size 2^3

C2.gen_mat()

[ 1 0 a a + 1 a] [ 0 1 a a + 1 a^2] [ 0 0 a a^2 + a a] [ 0 0 0 a^2 a^2]

Getting back to our first exmaple, to get a generator matrix is systematic form, we can use:

G2=C.gen_mat_systematic()

G2

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

Note that this matrix is not in standard form but is in systematic form, meaning that it can be put in standard form by permuting its columns. Doing so gives a generator matrix for an equivalent code. To get a matrix  into standard form, we permute the columns in order to obtain the identity matrix on the left. We do this by making a permutation matrix, that is, a matrix, $P$ such that when a matrix $A$ is multliplied by $P$ on the right, the colmns of $A$ are permuted. For each pair of columns we wish to swap, we construct an elementary matrix $E$ which when $A$ is multliplied by $E$ on the right, that pair of columns are swapped. If there is only one pair of columns which we need to swap, this elementary matrix is the permutation matrix we need. If not, we can contruct as many elementary matrices as we need, and their product will be our permutation matrix.

 

In the example above, we need to swap columns 4 and 5 in order to get a matrix in standard form. In Sage, however, the numbering starts with zero, so we need to call columns 4 and 5 columns 3 and 4 respectively. The following command constructs an elementary matrix.

E1=elementary_matrix(GF(3),9, col1=3, col2=4)
E1

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

This elementary matrix is simply the identity matrix with columns 4 and 5 interchanged. Since this is the only pair of columns we need to interchange, this is our permutation matrix.

P=E1
G3=G2*P
G3

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

To change the columns back, we simply need to multiply the new matrix by $P$ again.

G3*P

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

If we had also wanted to swap columns 1 and 9 we would have done the following:

E2=elementary_matrix(GF(3),9, col1=0, col2=8)
P=E1*E2
G2*P

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

$P$ swapped columns 4 and 5 and also swapped columns 1 and 9. The permutation matrix $P$ is the identity matrix with these columns interchanged.

P

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

We can use the following command to find the parity check matrix for the code.

H=C.check_mat()

H

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

And to get its transpose,

H.transpose()

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

If we want to multiply a vector by a matrix, we first have to declare the proper vector space, and then use the following syntax to create a vector:

VS=VectorSpace(GF(3),4)

v=VS([1,0,2,1])

If $v$ is a message that we wish to encode by multiplying it by G, we do so as follows:

v*G

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

Here we are creating a vector of length 9. We then see if this vector, $r$, is a codeword.

VS9=VectorSpace(GF(3),9)
r=VS9([2,1,1,1,1,1,1,1,1])

r*H.transpose()

(0, 1, 2, 1, 1)

Here are some more helpful functions.

C.minimum_distance()

C.is_self_dual()

False

C.is_self_orthogonal()

False

C.is_permutation_equivalent(D) is a command tells wether the code C is equivalent to the code D. This can be used to see if a code is equivalent to its dual.

MS=MatrixSpace(GF(2),2,4)
M=MS([[1,0,1,0],[0,1,0,1]])
C=LinearCode(M)
Cperp=C.dual_code()
C.is_permutation_equivalent(Cperp)

True

C.is_self_dual()

True

C.is_self_orthogonal()

True

C.list()

[(0, 0, 0, 0), (1, 0, 1, 0), (0, 1, 0, 1), (1, 1, 1, 1)]

Problem 1. Construct a linear code C over $\mathbb{F}_{5}$ of length 11 and dimension 5. Find its minimal distance.  Form a message vector of length 5 over the same field and encode it by multiplying it by the generator matrix of C. Change the encoded word by adding an error vector to it of weight less than or equal to $d-1$. Confirm that this word is not a codeword by multiplying it by the check matrix for the code. Repeat for a code of the same length and dimension over $\mathbb{F}_8$ The minimum distance command will not work for $\mathbb{F}_8$, however, so instead of finding it's mimimal distance make an error of weight 1.

 

 

Problem 2. Find the distance of the binary linear codes $C$ with each of the following parity check matrices.

(a) $H=\begin{matrix}0&1&1&1&0&0&0\\1&1&1&0&1&0&0\\1&1&0&0&0&1&0\\1&0&1&0&0&0&1 \end{matrix} \quad$ (b) $H=\begin{matrix}1&1&0&1&0&0&0\\1&0&1&0&1&0&0\\0&1&1&0&0&1&0\\1&1&0&0&0&0&1\end{matrix}$

Problem 3. Do exercise 4.18 from the text.

Problem 4. No problem 4, there was  a mistake here.

Problem 5. Construct a binary code $C$ of length 6 as follows: for every $(x_1,x_2,x_3)\in\mathbb{F}_2^3$ construct a 6-bit word $(x_1,x_2,x_3,x_4,x_5,x_6)\in C$, where

$x_4=x_1+x_2+x_3$,

$x_5=x_1+x_3$,

$x_6=x_3+x_3$

(i)Show that $C$ is a linear code.

(ii)Find a generator and parity check matrix for $C$.

Problem 6. Construct a linear code C over $\mathbb{F}_{32}$ such that the generator matix is $G= (I_n|A)$ where $I_n$ is an $n\times n$ identity matrix and $A$ is symmetric (equal to its transpose). Is $C$ self dual? If not, is $C$ equivalent to $C^\perp$? If $C$ is equivalent to $C^\perp$, construct a permutation matrix $P$ such that $GP$ is a generator matrix for $C^\perp$.

 

 

For those of you taking math 527, also do problems 4.9 and 4.10 from the text.