Generic structures for linear codes of any metric

Class supporting methods available for linear codes over any metric (Hamming, rank).

class sage.coding.linear_code_no_metric.AbstractLinearCodeNoMetric(base_field, length, default_encoder_name, default_decoder_name, metric='Hamming')

Bases: AbstractCode, Module

Abstract class for linear codes of any metric.

This class contains all the methods that can be used on any linear code of any metric. Every abstract class of linear codes over some metric (e.g. abstract class for linear codes over the Hamming metric, sage.coding.linear_code.AbstractLinearCode) should inherit from this class.

To create a new class of linear codes over some metrics, you need to:

• inherit from AbstractLinearCodeNoMetric

• call AbstractCode __init__ method in the subclass constructor. Example: super().__init__(length, "EncoderName", "DecoderName", "metric").

• add the following two lines on the class level:

  _registered_encoders = {}
  _registered_decoders = {}
  

• fill the dictionary of its encoders in sage.coding.__init__.py file. Example: I want to link the encoder MyEncoderClass to MyNewCodeClass under the name MyEncoderName. All I need to do is to write this line in the __init__.py file: MyNewCodeClass._registered_encoders["NameOfMyEncoder"] = MyEncoderClass and all instances of MyNewCodeClass will be able to use instances of MyEncoderClass.

• fill the dictionary of its decoders in sage.coding.__init__ file. Example: I want to link the encoder MyDecoderClass to MyNewCodeClass under the name MyDecoderName. All I need to do is to write this line in the __init__.py file: MyNewCodeClass._registered_decoders["NameOfMyDecoder"] = MyDecoderClass and all instances of MyNewCodeClass will be able to use instances of MyDecoderClass.

• create a generic constructor representative of you abstract class. This generic constructor is a class for unstructured linear codes given by some generator and considered over the given metric. A good example of this is sage.coding.linear_code.LinearCode, which is a generic constructor for sage.coding.linear_code.AbstractLinearCode, an abstract class for linear codes over the Hamming metric.

• set a private field in the __init__ method specifying the generic constructor, (e.g. MyAbstractCode._generic_constructor = MyCode)

It is assumed that the subclass codes are linear over base_field. To test this, it is recommended to add a test suite test to the generic constructor. To do this, create a representative of your code \(C\) and run TestSuite(C).run(). A good example of this is in sage.coding.linear_code.LinearCode.

As the class AbstractLinearCodeNoMetric is not designed to be instantiated, it does not have any representation methods. You should implement _repr_ and _latex_ methods in the subclass.

Warning

A lot of methods of the abstract class rely on the knowledge of a generator matrix. It is thus strongly recommended to set an encoder with a generator matrix implemented as a default encoder.

ambient_space()

Return the ambient vector space of self.

EXAMPLES:

sage: C = codes.HammingCode(GF(2), 3)
sage: C.ambient_space()
Vector space of dimension 7 over Finite Field of size 2

base_field()

Return the base field of self.

EXAMPLES:

sage: G  = Matrix(GF(2), [[1,1,1,0,0,0,0], [1,0,0,1,1,0,0],
....:                     [0,1,0,1,0,1,0], [1,1,0,1,0,0,1]])
sage: C  = LinearCode(G)
sage: C.base_field()
Finite Field of size 2

basis()

Return a basis of self.

OUTPUT:

• Sequence - an immutable sequence whose universe is ambient space of self.

EXAMPLES:

sage: C = codes.HammingCode(GF(2), 3)
sage: C.basis()
[
(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)
]
sage: C.basis().universe()
Vector space of dimension 7 over Finite Field of size 2

cardinality()

Return the size of this code.

EXAMPLES:

sage: C = codes.HammingCode(GF(2), 3)
sage: C.cardinality()
16
sage: len(C)
16

dimension()

Return the dimension of this code.

EXAMPLES:

sage: G = matrix(GF(2), [[1,0,0], [1,1,0]])
sage: C = LinearCode(G)
sage: C.dimension()
2

dual_code()

Return the dual code \(C^{\perp}\) of the code \(C\),

\[C^{\perp} = \{ v \in V\ |\ v\cdot c = 0,\ \forall c \in C \}.\]

EXAMPLES:

sage: C = codes.HammingCode(GF(2), 3)
sage: C.dual_code()
[7, 3] linear code over GF(2)
sage: C = codes.HammingCode(GF(4, 'a'), 3)
sage: C.dual_code()
[21, 3] linear code over GF(4)

generator_matrix(encoder_name=None, **kwargs)

Return a generator matrix of self.

INPUT:

• encoder_name – (default: None) name of the encoder which will be used to compute the generator matrix. The default encoder of self will be used if default value is kept.

• kwargs – all additional arguments are forwarded to the construction of the encoder that is used.

EXAMPLES:

sage: G = matrix(GF(3), 2, [1,-1,1,-1,1,1])
sage: code = LinearCode(G)
sage: code.generator_matrix()
[1 2 1]
[2 1 1]

gens()

Return the generators of this code as a list of vectors.

EXAMPLES:

sage: C = codes.HammingCode(GF(2), 3)
sage: C.gens()
 [(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)]

information_set()

Return an information set of the code.

Return value of this method is cached.

A set of column positions of a generator matrix of a code is called an information set if the corresponding columns form a square matrix of full rank.

OUTPUT:

• Information set of a systematic generator matrix of the code.

EXAMPLES:

sage: G = matrix(GF(3),2,[1,2,0,
....:                     2,1,1])
sage: code = LinearCode(G)
sage: code.systematic_generator_matrix()
[1 2 0]
[0 0 1]
sage: code.information_set()
(0, 2)

is_information_set(positions)

Return whether the given positions form an information set.

INPUT:

• A list of positions, i.e. integers in the range 0 to \(n-1\) where \(n\) is the length of self.

OUTPUT:

• A boolean indicating whether the positions form an information set.

EXAMPLES:

sage: G = matrix(GF(3),2,[1,2,0,
....:                     2,1,1])
sage: code = LinearCode(G)
sage: code.is_information_set([0,1])
False
sage: code.is_information_set([0,2])
True

is_permutation_automorphism(g)

Return \(1\) if \(g\) is an element of \(S_n\) (\(n\) = length of self) and if \(g\) is an automorphism of self.

EXAMPLES:

sage: C = codes.HammingCode(GF(3), 3)
sage: g = SymmetricGroup(13).random_element()
sage: C.is_permutation_automorphism(g)
0
sage: MS = MatrixSpace(GF(2),4,8)
sage: G  = MS([[1,0,0,0,1,1,1,0], [0,1,1,1,0,0,0,0],
....:          [0,0,0,0,0,0,0,1], [0,0,0,0,0,1,0,0]])
sage: C  = LinearCode(G)
sage: S8 = SymmetricGroup(8)
sage: g = S8("(2,3)")
sage: C.is_permutation_automorphism(g)
1
sage: g = S8("(1,2,3,4)")
sage: C.is_permutation_automorphism(g)
0

is_self_dual()

Return True if the code is self-dual (in the usual Hamming inner product) and False otherwise.

EXAMPLES:

sage: C = codes.GolayCode(GF(2))
sage: C.is_self_dual()
True
sage: C = codes.HammingCode(GF(2), 3)
sage: C.is_self_dual()
False

is_self_orthogonal()

Return True if this code is self-orthogonal and False otherwise.

A code is self-orthogonal if it is a subcode of its dual.

EXAMPLES:

sage: C = codes.GolayCode(GF(2))
sage: C.is_self_orthogonal()
True
sage: C = codes.HammingCode(GF(2), 3)
sage: C.is_self_orthogonal()
False
sage: C = codes.QuasiQuadraticResidueCode(11)  # optional - gap_package_guava
sage: C.is_self_orthogonal()                   # optional - gap_package_guava
True

is_subcode(other)

Return True if self is a subcode of other.

EXAMPLES:

sage: C1 = codes.HammingCode(GF(2), 3)
sage: G1 = C1.generator_matrix()
sage: G2 = G1.matrix_from_rows([0,1,2])
sage: C2 = LinearCode(G2)
sage: C2.is_subcode(C1)
True
sage: C1.is_subcode(C2)
False
sage: C3 = C1.extended_code()
sage: C1.is_subcode(C3)
False
sage: C4 = C1.punctured([1])
sage: C4.is_subcode(C1)
False
sage: C5 = C1.shortened([1])
sage: C5.is_subcode(C1)
False
sage: C1 = codes.HammingCode(GF(9,"z"), 3)
sage: G1 = C1.generator_matrix()
sage: G2 = G1.matrix_from_rows([0,1,2])
sage: C2 = LinearCode(G2)
sage: C2.is_subcode(C1)
True

parity_check_matrix()

Return the parity check matrix of self.

The parity check matrix of a linear code \(C\) corresponds to the generator matrix of the dual code of \(C\).

EXAMPLES:

sage: C = codes.HammingCode(GF(2), 3)
sage: Cperp = C.dual_code()
sage: C; Cperp
[7, 4] Hamming Code over GF(2)
[7, 3] linear code over GF(2)
sage: C.generator_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]
sage: C.parity_check_matrix()
 [1 0 1 0 1 0 1]
 [0 1 1 0 0 1 1]
 [0 0 0 1 1 1 1]
sage: Cperp.parity_check_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]
sage: Cperp.generator_matrix()
 [1 0 1 0 1 0 1]
 [0 1 1 0 0 1 1]
 [0 0 0 1 1 1 1]

permuted_code(p)

Return the permuted code, which is equivalent to self via the column permutation p.

EXAMPLES:

sage: C = codes.HammingCode(GF(2), 3)
sage: G = C.permutation_automorphism_group(); G
Permutation Group with generators
 [(4,5)(6,7), (4,6)(5,7), (2,3)(6,7), (2,4)(3,5), (1,2)(5,6)]
sage: g = G("(2,3)(6,7)")
sage: Cg = C.permuted_code(g)
sage: Cg
[7, 4] linear code over GF(2)
sage: C.generator_matrix() == Cg.systematic_generator_matrix()
True

rate()

Return the ratio of the number of information symbols to the code length.

EXAMPLES:

sage: C = codes.HammingCode(GF(2), 3)
sage: C.rate()
4/7

redundancy_matrix()

Return the non-identity columns of a systematic generator matrix for self.

A systematic generator matrix is a generator matrix such that a subset of its columns forms the identity matrix. This method returns the remaining part of the matrix.

For any given code, there can be many systematic generator matrices (depending on which positions should form the identity). This method will use the matrix returned by AbstractLinearCode.systematic_generator_matrix().

OUTPUT:

• An \(k \times (n-k)\) matrix.

EXAMPLES:

sage: C = codes.HammingCode(GF(2), 3)
sage: C.generator_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]
sage: C.redundancy_matrix()
 [0 1 1]
 [1 0 1]
 [1 1 0]
 [1 1 1]
sage: C = LinearCode(matrix(GF(3),2,[1,2,0,\
                                     2,1,1]))
sage: C.systematic_generator_matrix()
[1 2 0]
[0 0 1]
sage: C.redundancy_matrix()
[2]
[0]

standard_form(return_permutation=True)

Return a linear code which is permutation-equivalent to self and admits a generator matrix in standard form.

A generator matrix is in standard form if it is of the form \([I \vert A]\), where \(I\) is the \(k \times k\) identity matrix. Any code admits a generator matrix in systematic form, i.e. where a subset of the columns form the identity matrix, but one might need to permute columns to allow the identity matrix to be leading.

INPUT:

• return_permutation – (default: True) if True, the column permutation which brings self into the returned code is also returned.

OUTPUT:

• A LinearCode whose systematic_generator_matrix() is guaranteed to be of the form \([I \vert A]\).

EXAMPLES:

sage: C = codes.HammingCode(GF(2), 3)
sage: C.generator_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]
sage: Cs,p = C.standard_form()
sage: p
[]
sage: Cs is C
True
sage: C = LinearCode(matrix(GF(2), [[1,0,0,0,1,1,0],\
                                    [0,1,0,1,0,1,0],\
                                    [0,0,0,0,0,0,1]]))
sage: Cs, p = C.standard_form()
sage: p
[1, 2, 7, 3, 4, 5, 6]
sage: Cs.generator_matrix()
[1 0 0 0 0 1 1]
[0 1 0 0 1 0 1]
[0 0 1 0 0 0 0]

syndrome(r)

Return the syndrome of r.

The syndrome of r is the result of \(H \times r\) where \(H\) is the parity check matrix of self. If r belongs to self, its syndrome equals to the zero vector.

INPUT:

• r – a vector of the same length as self

OUTPUT:

• a column vector

EXAMPLES:

sage: MS = MatrixSpace(GF(2),4,7)
sage: G  = MS([[1,1,1,0,0,0,0], [1,0,0,1,1,0,0], [0,1,0,1,0,1,0], [1,1,0,1,0,0,1]])
sage: C  = LinearCode(G)
sage: r = vector(GF(2), (1,0,1,0,1,0,1))
sage: r in C
True
sage: C.syndrome(r)
(0, 0, 0)

If r is not a codeword, its syndrome is not equal to zero:

sage: r = vector(GF(2), (1,0,1,0,1,1,1))
sage: r in C
False
sage: C.syndrome(r)
(0, 1, 1)

Syndrome computation works fine on bigger fields:

sage: C = codes.random_linear_code(GF(59), 12, 4)
sage: c = C.random_element()
sage: C.syndrome(c)
(0, 0, 0, 0, 0, 0, 0, 0)

systematic_generator_matrix(systematic_positions=None)

Return a systematic generator matrix of the code.

A generator matrix of a code is called systematic if it contains a set of columns forming an identity matrix.

INPUT:

• systematic_positions – (default: None) if supplied, the set of systematic positions in the systematic generator matrix. See the documentation for LinearCodeSystematicEncoder details.

EXAMPLES:

sage: G = matrix(GF(3), [[ 1, 2, 1, 0],                                     [ 2, 1, 1, 1]])
sage: C = LinearCode(G)
sage: C.generator_matrix()
[1 2 1 0]
[2 1 1 1]
sage: C.systematic_generator_matrix()
[1 2 0 1]
[0 0 1 2]

Specific systematic positions can also be requested:

sage: C.systematic_generator_matrix(systematic_positions=[3,2])
[1 2 0 1]
[1 2 1 0]

zero()

Return the zero vector of self.

EXAMPLES:

sage: C = codes.HammingCode(GF(2), 3)
sage: C.zero()
(0, 0, 0, 0, 0, 0, 0)
sage: C.sum(()) # indirect doctest
(0, 0, 0, 0, 0, 0, 0)
sage: C.sum((C.gens())) # indirect doctest
(1, 1, 1, 1, 1, 1, 1)

class sage.coding.linear_code_no_metric.LinearCodeSystematicEncoder(code, systematic_positions=None)

Bases: Encoder

Encoder based on a generator matrix in systematic form for Linear codes.

To encode an element of its message space, this encoder first builds a generator matrix in systematic form. What is called systematic form here is the reduced row echelon form of a matrix, which is not necessarily \([I \vert H]\), where \(I\) is the identity block and \(H\) the parity block. One can refer to LinearCodeSystematicEncoder.generator_matrix() for a concrete example. Once such a matrix has been computed, it is used to encode any message into a codeword.

This encoder can also serve as the default encoder of a code defined by a parity check matrix: if the LinearCodeSystematicEncoder detects that it is the default encoder, it computes a generator matrix as the reduced row echelon form of the right kernel of the parity check matrix.

INPUT:

• code – The associated code of this encoder.

• systematic_positions – (default: None) the positions in codewords that should correspond to the message symbols. A list of \(k\) distinct integers in the range 0 to \(n-1\) where \(n\) is the length of the code and \(k\) its dimension. The 0th symbol of a message will then be at position systematic_positions[0], the 1st index at position systematic_positions[1], etc. A ValueError is raised at construction time if the supplied indices do not form an information set.

EXAMPLES:

The following demonstrates the basic usage of LinearCodeSystematicEncoder:

sage: LCSE = codes.encoders.LinearCodeSystematicEncoder
sage: G = Matrix(GF(2), [[1,1,1,0,0,0,0,0],\
                         [1,0,0,1,1,0,0,0],\
                         [0,1,0,1,0,1,0,0],\
                         [1,1,0,1,0,0,1,1]])
sage: C = LinearCode(G)
sage: E = LCSE(C)
sage: E.generator_matrix()
[1 0 0 0 0 1 1 1]
[0 1 0 0 1 0 1 1]
[0 0 1 0 1 1 0 0]
[0 0 0 1 1 1 1 1]
sage: E2 = LCSE(C, systematic_positions=[5,4,3,2])
sage: E2.generator_matrix()
[1 0 0 0 0 1 1 1]
[0 1 0 0 1 0 1 1]
[1 1 0 1 0 0 1 1]
[1 1 1 0 0 0 0 0]

An error is raised if one specifies systematic positions which do not form an information set:

sage: E3 = LCSE(C, systematic_positions=[0,1,6,7])
Traceback (most recent call last):
...
ValueError: systematic_positions are not an information set

We exemplify how to use LinearCodeSystematicEncoder as the default encoder. The following class is the dual of the repetition code:

sage: class DualRepetitionCode(sage.coding.linear_code.AbstractLinearCode):
....:   def __init__(self, field, length):
....:       super().__init__(field, length, "Systematic", "Syndrome")
....:
....:   def parity_check_matrix(self):
....:       return Matrix(self.base_field(), [1]*self.length())
....:
....:   def _repr_(self):
....:       return "Dual of the [%d, 1] Repetition Code over GF(%s)" % (self.length(), self.base_field().cardinality())
....:
sage: DualRepetitionCode(GF(3), 5).generator_matrix()
[1 0 0 0 2]
[0 1 0 0 2]
[0 0 1 0 2]
[0 0 0 1 2]

An exception is thrown if LinearCodeSystematicEncoder is the default encoder but no parity check matrix has been specified for the code:

sage: class BadCodeFamily(sage.coding.linear_code.AbstractLinearCode):
....:   def __init__(self, field, length):
....:       super().__init__(field, length, "Systematic", "Syndrome")
....:
....:   def _repr_(self):
....:       return "I am a badly defined code"
....:
sage: BadCodeFamily(GF(3), 5).generator_matrix()
Traceback (most recent call last):
...
ValueError: a parity check matrix must be specified
if LinearCodeSystematicEncoder is the default encoder

generator_matrix()

Return a generator matrix in systematic form of the associated code of self.

Systematic form here means that a subsets of the columns of the matrix forms the identity matrix.

Note

The matrix returned by this method will not necessarily be \([I \vert H]\), where \(I\) is the identity block and \(H\) the parity block. If one wants to know which columns create the identity block, one can call systematic_positions()

EXAMPLES:

sage: LCSE = codes.encoders.LinearCodeSystematicEncoder
sage: G = Matrix(GF(2), [[1,1,1,0,0,0,0],\
                         [1,0,0,1,1,0,0],\
                         [0,1,0,1,0,1,0],\
                         [1,1,0,1,0,0,1]])
sage: C = LinearCode(G)
sage: E = LCSE(C)
sage: E.generator_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]

We can ask for different systematic positions:

sage: E2 = LCSE(C, systematic_positions=[5,4,3,2])
sage: E2.generator_matrix()
[1 0 0 0 0 1 1]
[0 1 0 0 1 0 1]
[1 1 0 1 0 0 1]
[1 1 1 0 0 0 0]

Another example where there is no generator matrix of the form \([I \vert H]\):

sage: G = Matrix(GF(2), [[1,1,0,0,1,0,1],\
                         [1,1,0,0,1,0,0],\
                         [0,0,1,0,0,1,0],\
                         [0,0,1,0,1,0,1]])
sage: C = LinearCode(G)
sage: E = LCSE(C)
sage: E.generator_matrix()
[1 1 0 0 0 1 0]
[0 0 1 0 0 1 0]
[0 0 0 0 1 1 0]
[0 0 0 0 0 0 1]

systematic_permutation()

Return a permutation which would take the systematic positions into [0,..,k-1]

EXAMPLES:

sage: C = LinearCode(matrix(GF(2), [[1,0,0,0,1,1,0],\
                                    [0,1,0,1,0,1,0],\
                                    [0,0,0,0,0,0,1]]))
sage: E = codes.encoders.LinearCodeSystematicEncoder(C)
sage: E.systematic_positions()
(0, 1, 6)
sage: E.systematic_permutation()
[1, 2, 7, 3, 4, 5, 6]

systematic_positions()

Return a tuple containing the indices of the columns which form an identity matrix when the generator matrix is in systematic form.

EXAMPLES:

sage: LCSE = codes.encoders.LinearCodeSystematicEncoder
sage: G = Matrix(GF(2), [[1,1,1,0,0,0,0],\
                         [1,0,0,1,1,0,0],\
                         [0,1,0,1,0,1,0],\
                         [1,1,0,1,0,0,1]])
sage: C = LinearCode(G)
sage: E = LCSE(C)
sage: E.systematic_positions()
(0, 1, 2, 3)

We take another matrix with a less nice shape:

sage: G = Matrix(GF(2), [[1,1,0,0,1,0,1],\
                         [1,1,0,0,1,0,0],\
                         [0,0,1,0,0,1,0],\
                         [0,0,1,0,1,0,1]])
sage: C = LinearCode(G)
sage: E = LCSE(C)
sage: E.systematic_positions()
(0, 2, 4, 6)

The systematic positions correspond to the positions which carry information in a codeword:

sage: MS = E.message_space()
sage: m = MS.random_element()
sage: c = m * E.generator_matrix()
sage: pos = E.systematic_positions()
sage: info = MS([c[i] for i in pos])
sage: m == info
True

When constructing a systematic encoder with specific systematic positions, then it is guaranteed that this method returns exactly those positions (even if another choice might also be systematic):

sage: G = Matrix(GF(2), [[1,0,0,0],\
                         [0,1,0,0],\
                         [0,0,1,1]])
sage: C = LinearCode(G)
sage: E = LCSE(C, systematic_positions=[0,1,3])
sage: E.systematic_positions()
(0, 1, 3)