Coding Theory¶

Linear Codes¶

Linear Codes

class simula.coding.linear_code.LinearCode(field=GF(2), gen_matrix=None, check_matrix=None)¶

Representation of linear codes.

EXAMPLES:

simula : G = matrix([ [1,1,1,0,1,1], [0,1,0,0,1,1], [1,0,1,1,0,1], [0,1,1,1,0,1] ])
simula : G
Matrix([
[1, 1, 1, 0, 1, 1],
[0, 1, 0, 0, 1, 1],
[1, 0, 1, 1, 0, 1],
[0, 1, 1, 1, 0, 1]])
simula : C = LinearCode(GF(2), G); C
Linear code over GF(2) of generator matrix
Matrix([
[1, 1, 1, 0, 1, 1],
[0, 1, 0, 0, 1, 1],
[1, 0, 1, 1, 0, 1],
[0, 1, 1, 1, 0, 1]])
simula : C.dimension()
4
simula : C.minimum_distance()
2
simula : C.correction_capacity()
0
simula : C.parity_check_matrix()
Matrix([
[1, 1, 1, 0, 1, 0],
[1, 1, 1, 1, 0, 1]])
simula : C.all_codewords()
[(0, 0, 0, 0, 0, 0), (0, 1, 1, 1, 0, 1), (1, 0, 1, 1, 0, 1), (1, 1, 0, 0, 0, 0), (0, 1, 0, 0, 1, 1),
 (0, 0, 1, 1, 1, 0), (1, 1, 1, 1, 1, 0), (1, 0, 0, 0, 1, 1), (1, 1, 1, 0, 1, 1), (1, 0, 0, 1, 1, 0),
  (0, 1, 0, 1, 1, 0), (0, 0, 1, 0, 1, 1), (1, 0, 1, 0, 0, 0), (1, 1, 0, 1, 0, 1), (0, 0, 0, 1, 0, 1),
  (0, 1, 1, 0, 0, 0)]

control_matrix()¶

Returns a parity check matrix of self.

Return type: simula.linalg.matrices.Matrix

correction_capacity()¶: Returns the error correction capacity of self.

dimension()¶: Returns the dimension of self.

dual_code()¶: Returns the dual code of self.

encode(m)¶: Returns the encoding of the vector m.

generator_matrix()¶

Returns a generator matrix of the linear code self.

Return type: simula.linalg.matrices.Matrix

is_codeword(w)¶

Returns True if w is a codeword of self and False otherwise.

INPUT:

w – a word

property k¶: Returns the dimension of self.

length()¶: Returns the length of self.

minimum_distance()¶: Returns the minimum distance of self.

property n¶: Returns the length of self.

number_of_codewords()¶: Returns the number of codewords (cardinality) of self.

parity_check_matrix()¶

Returns a parity check matrix of self.

Return type: simula.linalg.matrices.Matrix

syndrome(w)¶

Returns the syndrome of the word w.

INPUT:

w – a word

Hamming Codes¶

Hamming codes

class simula.coding.hamming_code.HammingCode(field, r=3)¶

Bases: simula.coding.linear_code.LinearCode

Representation of a hamming code.

EXAMPLES:

simula : C = HammingCode(GF(2), r=3); C
Hamming Code defined over GF(2) of parity check matrix
Matrix([
[0, 0, 0, 1, 1, 1, 1],
[0, 1, 1, 0, 0, 1, 1],
[1, 0, 1, 0, 1, 0, 1]])
simula : C.generator_matrix()
Matrix([
[1, 0, 0, 0, 0, 1, 1],
[0, 1, 0, 0, 1, 0, 1],
[0, 0, 1, 0, 1, 1, 0],
[0, 0, 0, 1, 1, 1, 1]])
simula : C.dimension()
4
simula : C.correction_capacity()
1

dimension()¶: Returns the dimension of self.

length()¶: Returns the length of self.

minimum_distance()¶: Returns the minimum distance of self.

Cyclic Codes¶

Cyclic Codes

class simula.coding.cyclic_code.CyclicCode(length=None, gen_poly=None, check_poly=None, code=None)¶

Bases: simula.coding.linear_code.LinearCode

Representation of a cyclic code.

There are two different ways to create a new CyclicCode, either by providing:

the generator polynomial and the length (1) or

the check polynomial and the length (2).

Parameters

gen_poly – (default: None) the generator polynomial of self. That is, the highest-degree monic polynomial which divides every polynomial representation of a codeword in self.
check_poly – (default: None) the check polynomial of self.
length – (default: None) the length of self. It has to be bigger than the degree of gen_poly.

EXAMPLES:

simula: R.<x> = GF(2)[]
simula: g = x^3 + x + 1
simula: C = CyclicCode(gen_poly=g, length=7)
simula : C
Linear code over GF(2) of generator matrix
Matrix([
[1, 1, 0, 1, 0, 0, 0],
[0, 1, 1, 0, 1, 0, 0],
[0, 0, 1, 1, 0, 1, 0],
[0, 0, 0, 1, 1, 0, 1]])
simula: h = C.check_polynomial(); h
x^4 + x^2 + x + 1
simula: C2 = CyclicCode(check_poly=h, length=7)
simula : C2
Linear code over GF(2) of parity check matrix
Matrix([
[1, 0, 1, 1, 1, 0, 0],
[0, 1, 0, 1, 1, 1, 0],
[0, 0, 1, 0, 1, 1, 1]])
simula : C2.generator_polynomial()
x^3 + x + 1

check_polynomial()¶

Returns the check polynomial of self.

EXAMPLES:

simula: R.<x> = GF(2)[]
simula: g = x^3 + x + 1
simula: C = CyclicCode(gen_poly=g, length=7)
simula: C.check_polynomial()
x^4 + x^2 + x + 1

generator_polynomial()¶

Returns the generator polynomial of self.

EXAMPLES:

simula: R.<x> = GF(2)[]
simula: g = x^3 + x + 1
simula: C = CyclicCode(gen_poly=g, length=7)
simula: C.generator_polynomial()
x^3 + x + 1

is_codeword(w)¶

Returns True if w is a codeword of self and False otherwise.

Parameters: w – a word

length()¶: Returns the length of self.

parity_check_matrix()¶

Returns the parity check matrix of self.

EXAMPLES:

simula: R.<x> = GF(2)[]
simula: g = x^3 + x + 1
simula: C = CyclicCode(gen_poly=g, length=7)
simula: C.parity_check_matrix()
Matrix([
[1, 0, 1, 1, 1, 0, 0],
0, 1, 0, 1, 1, 1, 0],
[0, 0, 1, 0, 1, 1, 1]])

Return type: simula.linalg.matrices.Matrix

syndrome(w, poly=False)¶

Returns the syndrome of the word w in the form of a polynomial or a vector.

Parameters

w – a word
poly – (default: False) if True the syndrome is returned as a polynomial