Punctured code

Let \(C\) be a linear code. Let \(C_i\) be the set of all words of \(C\) with the \(i\)-th coordinate being removed. \(C_i\) is the punctured code of \(C\) on the \(i\)-th position.

class sage.coding.punctured_code.PuncturedCode(C, positions)

Bases: sage.coding.linear_code.AbstractLinearCode

Representation of a punctured code.

• C – A linear code

• positions – the positions where C will be punctured. It can be either an integer if one need to puncture only one position, a list or a set of positions to puncture. If the same position is passed several times, it will be considered only once.

EXAMPLES:

sage: C = codes.random_linear_code(GF(7), 11, 5)
sage: Cp = codes.PuncturedCode(C, 3)
sage: Cp
Puncturing of [11, 5] linear code over GF(7) on position(s) [3]

sage: Cp = codes.PuncturedCode(C, {3, 5})
sage: Cp
Puncturing of [11, 5] linear code over GF(7) on position(s) [3, 5]

dimension()

Returns the dimension of self.

EXAMPLES:

sage: set_random_seed(42)
sage: C = codes.random_linear_code(GF(7), 11, 5)
sage: Cp = codes.PuncturedCode(C, 3)
sage: Cp.dimension()
5

encode(m, original_encode=False, encoder_name=None, **kwargs)

Transforms an element of the message space into an element of the code.

INPUT:

• m – a vector of the message space of the code.

• original_encode – (default: False) if this is set to True, m will be encoded using an Encoder of self’s original_code(). This allow to avoid the computation of a generator matrix for self.

• encoder_name – (default: None) Name of the encoder which will be used to encode word. The default encoder of self will be used if default value is kept

OUTPUT:

• an element of self

EXAMPLES:

sage: M = matrix(GF(7), [[1, 0, 0, 0, 3, 4, 6], [0, 1, 0, 6, 1, 6, 4], [0, 0, 1, 5, 2, 2, 4]])
sage: C_original = LinearCode(M)
sage: Cp = codes.PuncturedCode(C_original, 2)
sage: m = vector(GF(7), [1, 3, 5])
sage: Cp.encode(m)
 (1, 3, 5, 5, 0, 2)

original_code()

Returns the linear code which was punctured to get self.

EXAMPLES:

sage: C = codes.random_linear_code(GF(7), 11, 5)
sage: Cp = codes.PuncturedCode(C, 3)
sage: Cp.original_code()
[11, 5] linear code over GF(7)

punctured_positions()

Returns the list of positions which were punctured on the original code.

EXAMPLES:

sage: C = codes.random_linear_code(GF(7), 11, 5)
sage: Cp = codes.PuncturedCode(C, 3)
sage: Cp.punctured_positions()
{3}

random_element(*args, **kwds)

Returns a random codeword of self.

This method does not trigger the computation of self’s sage.coding.linear_code_no_metric.generator_matrix().

INPUT:

• agrs, kwds - extra positional arguments passed to sage.modules.free_module.random_element().

EXAMPLES:

sage: C = codes.random_linear_code(GF(7), 11, 5)
sage: Cp = codes.PuncturedCode(C, 3)
sage: Cp.random_element() in Cp
True

structured_representation()

Returns self as a structured code object.

If self has a specific structured representation (e.g. a punctured GRS code is a GRS code too), it will return this representation, else it returns a sage.coding.linear_code.LinearCode.

EXAMPLES:

We consider a GRS code:

sage: C_grs = codes.GeneralizedReedSolomonCode(GF(59).list()[:40], 12)

A punctured GRS code is still a GRS code:

sage: Cp_grs = codes.PuncturedCode(C_grs, 3)
sage: Cp_grs.structured_representation()
[39, 12, 28] Reed-Solomon Code over GF(59)

Another example with structureless linear codes:

sage: set_random_seed(42)
sage: C_lin  = codes.random_linear_code(GF(2), 10, 5)
sage: Cp_lin = codes.PuncturedCode(C_lin, 2)
sage: Cp_lin.structured_representation()
[9, 5] linear code over GF(2)

class sage.coding.punctured_code.PuncturedCodeOriginalCodeDecoder(code, strategy=None, original_decoder=None, **kwargs)

Bases: sage.coding.decoder.Decoder

Decoder decoding through a decoder over the original code of its punctured code.

INPUT:

• code – The associated code of this encoder

• strategy – (default: None) the strategy used to decode. The available strategies are:

  • 'error-erasure' – uses an error-erasure decoder over the original code if available,

    fails otherwise.

  • 'random-values' – fills the punctured positions with random elements

    in code’s base field and tries to decode using the default decoder of the original code

  • 'try-all' – fills the punctured positions with every possible combination of

    symbols until decoding succeeds, or until every combination have been tried

  • None – uses error-erasure if an error-erasure decoder is available,

    switch to random-values behaviour otherwise

• original_decoder – (default: None) the decoder that will be used over the original code. It has to be a decoder object over the original code. This argument takes precedence over strategy: if both original_decoder and strategy are filled, self will use the original_decoder to decode over the original code. If original_decoder is set to None, it will use the decoder picked by strategy.

• **kwargs – all extra arguments are forwarded to original code’s decoder

  EXAMPLES:

  sage: C = codes.GeneralizedReedSolomonCode(GF(16, 'a').list()[:15], 7)
  sage: Cp = codes.PuncturedCode(C, 3)
  sage: codes.decoders.PuncturedCodeOriginalCodeDecoder(Cp)
  Decoder of Puncturing of [15, 7, 9] Reed-Solomon Code over GF(16) on position(s) [3] through Error-Erasure decoder for [15, 7, 9] Reed-Solomon Code over GF(16)
  

  As seen above, if all optional are left blank, and if an error-erasure decoder is available, it will be chosen as the original decoder. Now, if one forces strategy `` to ``'try-all' or 'random-values', the default decoder of the original code will be chosen, even if an error-erasure is available:

  sage: C = codes.GeneralizedReedSolomonCode(GF(16, 'a').list()[:15], 7)
  sage: Cp = codes.PuncturedCode(C, 3)
  sage: D = codes.decoders.PuncturedCodeOriginalCodeDecoder(Cp, strategy="try-all")
  sage: "error-erasure" in D.decoder_type()
  False
  

  And if one fills original_decoder and strategy fields with contradictory elements, the original_decoder takes precedence:

  sage: C = codes.GeneralizedReedSolomonCode(GF(16, 'a').list()[:15], 7)
  sage: Cp = codes.PuncturedCode(C, 3)
  sage: Dor = C.decoder("Gao")
  sage: D = codes.decoders.PuncturedCodeOriginalCodeDecoder(Cp, original_decoder = Dor, strategy="error-erasure")
  sage: D.original_decoder() == Dor
  True
  

decode_to_code(y)

Decodes y to an element in sage.coding.decoder.Decoder.code().

EXAMPLES:

sage: C = codes.GeneralizedReedSolomonCode(GF(16, 'a').list()[:15], 7)
sage: Cp = codes.PuncturedCode(C, 3)
sage: D = codes.decoders.PuncturedCodeOriginalCodeDecoder(Cp)
sage: c = Cp.random_element()
sage: Chan = channels.StaticErrorRateChannel(Cp.ambient_space(), 3)
sage: y = Chan(c)
sage: y in Cp
False
sage: D.decode_to_code(y) == c
True

decoding_radius(number_erasures=None)

Returns maximal number of errors that self can decode.

EXAMPLES:

sage: C = codes.GeneralizedReedSolomonCode(GF(16, 'a').list()[:15], 7)
sage: Cp = codes.PuncturedCode(C, 3)
sage: D = codes.decoders.PuncturedCodeOriginalCodeDecoder(Cp)
sage: D.decoding_radius(2)
2

original_decoder()

Returns the decoder over the original code that will be used to decode words of sage.coding.decoder.Decoder.code().

EXAMPLES:

sage: C = codes.GeneralizedReedSolomonCode(GF(16, 'a').list()[:15], 7)
sage: Cp = codes.PuncturedCode(C, 3)
sage: D = codes.decoders.PuncturedCodeOriginalCodeDecoder(Cp)
sage: D.original_decoder()
Error-Erasure decoder for [15, 7, 9] Reed-Solomon Code over GF(16)

class sage.coding.punctured_code.PuncturedCodePuncturedMatrixEncoder(code)

Bases: sage.coding.encoder.Encoder

Encoder using original code generator matrix to compute the punctured code’s one.

INPUT:

• code – The associated code of this encoder.

EXAMPLES:

sage: C = codes.random_linear_code(GF(7), 11, 5)
sage: Cp = codes.PuncturedCode(C, 3)
sage: E = codes.encoders.PuncturedCodePuncturedMatrixEncoder(Cp)
sage: E
Punctured matrix-based encoder for the Puncturing of [11, 5] linear code over GF(7) on position(s) [3]

generator_matrix()

Returns a generator matrix of the associated code of self.

EXAMPLES:

sage: set_random_seed(10)
sage: C = codes.random_linear_code(GF(7), 11, 5)
sage: Cp = codes.PuncturedCode(C, 3)
sage: E = codes.encoders.PuncturedCodePuncturedMatrixEncoder(Cp)
sage: E.generator_matrix()
[1 0 0 0 0 5 2 6 0 6]
[0 1 0 0 0 5 2 2 1 1]
[0 0 1 0 0 6 2 4 0 4]
[0 0 0 1 0 0 6 3 3 3]
[0 0 0 0 1 0 1 3 4 3]