4236.sagews

Code Construction

On the last worksheet we learned how to contruct linear codes by entering in a generator matrix. Sage will make a random linear code with the length and dimension you specify over the finite field you specify.

C=RandomLinearCode(30,15,GF(2))
C

Linear code of length 30, dimension 15 over Finite Field of size 2

C.gen_mat()

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

C=RandomLinearCode(10,5,GF(4,'a'))
C

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

C.gen_mat()

[ 1 0 0 0 0 a 1 1 a a + 1] [ 0 1 0 0 0 a + 1 a 1 0 a] [ 0 0 1 0 0 a a + 1 1 1 a + 1] [ 0 0 0 1 0 1 1 a + 1 a 1] [ 0 0 0 0 1 a + 1 1 a + 1 a 1]

C.minimum_distance()

3

H=C.check_mat();H

[ 1 0 0 0 0 0 a + 1 0 0 a + 1] [ 0 1 0 0 0 0 a + 1 0 a 0] [ 0 0 1 0 0 0 a + 1 a 0 a] [ 0 0 0 1 0 a + 1 a + 1 0 a a] [ 0 0 0 0 1 a + 1 a 1 1 0]

Hamming Codes

As we learned in class, Hamming Codes are defined by their parity check matrices. Sage will create Hamming Codes for us, and if we ask for them, will give us the parity check matrix. We can check that the code having this parity check matrix is the same as the code defined. To construct the binary Hamming Code with check matrix $H_r$ the syntax is C=HammingCode(r,GF(2)), and for $q$-ary codes it is C=HammingCode(r,GF(q)).

C=HammingCode(3,GF(2))
H=C.check_mat();H

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

LinearCodeFromCheckMatrix(H)==C

True

C=HammingCode(2,GF(2))
H=C.check_mat();H

[1 0 1] [0 1 1]

LinearCodeFromCheckMatrix(H)==C

True

C=HammingCode(2,GF(8,'a'))
H=C.check_mat();H

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

LinearCodeFromCheckMatrix(H)==C

True

Golay Codes

Sage also has constructions for the Binary Golay Code, the Extended Binary Golay Code, the Ternary Golay Code, and the Extended Ternary Golay Code.

C=BinaryGolayCode()
C

Linear code of length 23, dimension 12 over Finite Field of size 2

C.gen_mat()

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

C.minimum_distance()

7

C.is_self_dual()

False

C.is_self_orthogonal()

False

C=ExtendedBinaryGolayCode()
C

Linear code of length 24, dimension 12 over Finite Field of size 2

C.is_self_dual()

True

C.gen_mat()

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

C.minimum_distance()

8

C=TernaryGolayCode()

C

Linear code of length 11, dimension 6 over Finite Field of size 3

C.gen_mat()

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

C.minimum_distance()

5

C=ExtendedTernaryGolayCode()

C

Linear code of length 12, dimension 6 over Finite Field of size 3

C.gen_mat()

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

C.minimum_distance()

6

Homework

1. Construct an SDA for the Extended Hamming code $\hat{\mathcal{H}_3}$, and use it to decode 110101101010101010111111.

 

2. Construct an example code to show the shortening process can change the rank, and another in which the rank remains unchanged.

 

3.The dual of the extended Hamming code $\hat{\mathcal{H}_r}$ is called the first order Reed-Muller code, and is denoted $\mathcal{R}(1,r)$.

    a) Find a generator matrix and a praity check matrix for $\mathcal{R}(1,4)$.

    b) Determine the parameters for this code.

    c) Let $R(k)$ denote the repetition code of length $k$. Construct a generator matrix for the code $C$ which is obtained by using the $(u,u+v)$ construction on the codes $\mathcal{R}(1,3)$ and $R(8)$.

    d) What is the relation between the codes $C$ and $\mathcal{R}(1,4)$?

4. Consider the codes $C_1=C_2=\mathcal{H}_3$ with generator matrices $G$. We will construct a code of dimension 16. Here we describe the endoing process. Take a bianry message $m$ of length 16, and break it into 4 words of length 4 each. Arrange the four words as four rows in a $4\times 4$ matrix (watch the order). Now, encode each row using code $C_1$ to obtains rows of length $7$. You now have a matrix of size $4\times 7$. Now use code $C_2$ to encode each column of this matrix. You should obtain a $7\times 7$ matrix. Now write the rows of this matrix into on large row of length 49. This is the enceded word. We have constructed an example of a Product Code, in this case of length 49 and dismension 16.

 

Produce a generator matrix for this code.

5. Choose two of the following three problems

     a)Prove the result about minimal distances of extended codes (see lecture notes from 2/7/12).

     b) Exercise 5.23 from the text

     c) Exercise 5.31 from the text

If you are taking math 527 do the following additional problems:

6. Prove the result about minimal distances for the $(u,u+v)$ construction in the special case that $d_2=2d_1$.

7. Let $C$ be a binary linear code with minimal distance $d=2s$. Show that there is a coset of $C$ that contains at least two words of weight $s$.