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