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)[source]#

Bases: 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]

>>> from sage.all import *
>>> C = codes.random_linear_code(GF(Integer(7)), Integer(11), Integer(5))
>>> Cp = codes.PuncturedCode(C, Integer(3))
>>> Cp
Puncturing of [11, 5] linear code over GF(7) on position(s) [3]

>>> Cp = codes.PuncturedCode(C, {Integer(3), Integer(5)})
>>> Cp
Puncturing of [11, 5] linear code over GF(7) on position(s) [3, 5]
dimension()[source]#

Return 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

>>> from sage.all import *
>>> set_random_seed(Integer(42))
>>> C = codes.random_linear_code(GF(Integer(7)), Integer(11), Integer(5))
>>> Cp = codes.PuncturedCode(C, Integer(3))
>>> Cp.dimension()
5
encode(m, original_encode=False, encoder_name=None, **kwargs)[source]#

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)

>>> from sage.all import *
>>> M = matrix(GF(Integer(7)), [[Integer(1), Integer(0), Integer(0), Integer(0), Integer(3), Integer(4), Integer(6)],
...                    [Integer(0), Integer(1), Integer(0), Integer(6), Integer(1), Integer(6), Integer(4)],
...                    [Integer(0), Integer(0), Integer(1), Integer(5), Integer(2), Integer(2), Integer(4)]])
>>> C_original = LinearCode(M)
>>> Cp = codes.PuncturedCode(C_original, Integer(2))
>>> m = vector(GF(Integer(7)), [Integer(1), Integer(3), Integer(5)])
>>> Cp.encode(m)
 (1, 3, 5, 5, 0, 2)
original_code()[source]#

Return 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)

>>> from sage.all import *
>>> C = codes.random_linear_code(GF(Integer(7)), Integer(11), Integer(5))
>>> Cp = codes.PuncturedCode(C, Integer(3))
>>> Cp.original_code()
[11, 5] linear code over GF(7)
punctured_positions()[source]#

Return 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}

>>> from sage.all import *
>>> C = codes.random_linear_code(GF(Integer(7)), Integer(11), Integer(5))
>>> Cp = codes.PuncturedCode(C, Integer(3))
>>> Cp.punctured_positions()
{3}
random_element(*args, **kwds)[source]#

Return 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

>>> from sage.all import *
>>> C = codes.random_linear_code(GF(Integer(7)), Integer(11), Integer(5))
>>> Cp = codes.PuncturedCode(C, Integer(3))
>>> Cp.random_element() in Cp
True
structured_representation()[source]#

Return 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)

>>> from sage.all import *
>>> C_grs = codes.GeneralizedReedSolomonCode(GF(Integer(59)).list()[:Integer(40)], Integer(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)

>>> from sage.all import *
>>> Cp_grs = codes.PuncturedCode(C_grs, Integer(3))
>>> 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)

>>> from sage.all import *
>>> set_random_seed(Integer(42))
>>> C_lin  = codes.random_linear_code(GF(Integer(2)), Integer(10), Integer(5))
>>> Cp_lin = codes.PuncturedCode(C_lin, Integer(2))
>>> Cp_lin.structured_representation()
[9, 5] linear code over GF(2)
class sage.coding.punctured_code.PuncturedCodeOriginalCodeDecoder(code, strategy=None, original_decoder=None, **kwargs)[source]#

Bases: 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)

>>> from sage.all import *
>>> C = codes.GeneralizedReedSolomonCode(GF(Integer(16), 'a').list()[:Integer(15)], Integer(7))
>>> Cp = codes.PuncturedCode(C, Integer(3))
>>> 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

>>> from sage.all import *
>>> C = codes.GeneralizedReedSolomonCode(GF(Integer(16), 'a').list()[:Integer(15)], Integer(7))
>>> Cp = codes.PuncturedCode(C, Integer(3))
>>> D = codes.decoders.PuncturedCodeOriginalCodeDecoder(Cp, strategy="try-all")
>>> "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

>>> from sage.all import *
>>> C = codes.GeneralizedReedSolomonCode(GF(Integer(16), 'a').list()[:Integer(15)], Integer(7))
>>> Cp = codes.PuncturedCode(C, Integer(3))
>>> Dor = C.decoder("Gao")
>>> D = codes.decoders.PuncturedCodeOriginalCodeDecoder(Cp, original_decoder=Dor,
...                                                     strategy="error-erasure")
>>> D.original_decoder() == Dor
True
decode_to_code(y)[source]#

Decode 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

>>> from sage.all import *
>>> C = codes.GeneralizedReedSolomonCode(GF(Integer(16), 'a').list()[:Integer(15)], Integer(7))
>>> Cp = codes.PuncturedCode(C, Integer(3))
>>> D = codes.decoders.PuncturedCodeOriginalCodeDecoder(Cp)
>>> c = Cp.random_element()
>>> Chan = channels.StaticErrorRateChannel(Cp.ambient_space(), Integer(3))
>>> y = Chan(c)
>>> y in Cp
False
>>> D.decode_to_code(y) == c
True
decoding_radius(number_erasures=None)[source]#

Return the 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

>>> from sage.all import *
>>> C = codes.GeneralizedReedSolomonCode(GF(Integer(16), 'a').list()[:Integer(15)], Integer(7))
>>> Cp = codes.PuncturedCode(C, Integer(3))
>>> D = codes.decoders.PuncturedCodeOriginalCodeDecoder(Cp)
>>> D.decoding_radius(Integer(2))
2
original_decoder()[source]#

Return 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)

>>> from sage.all import *
>>> C = codes.GeneralizedReedSolomonCode(GF(Integer(16), 'a').list()[:Integer(15)], Integer(7))
>>> Cp = codes.PuncturedCode(C, Integer(3))
>>> D = codes.decoders.PuncturedCodeOriginalCodeDecoder(Cp)
>>> D.original_decoder()
Error-Erasure decoder for [15, 7, 9] Reed-Solomon Code over GF(16)
class sage.coding.punctured_code.PuncturedCodePuncturedMatrixEncoder(code)[source]#

Bases: 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]

>>> from sage.all import *
>>> C = codes.random_linear_code(GF(Integer(7)), Integer(11), Integer(5))
>>> Cp = codes.PuncturedCode(C, Integer(3))
>>> E = codes.encoders.PuncturedCodePuncturedMatrixEncoder(Cp)
>>> E
Punctured matrix-based encoder for the
 Puncturing of [11, 5] linear code over GF(7) on position(s) [3]
generator_matrix()[source]#

Return 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]

>>> from sage.all import *
>>> set_random_seed(Integer(10))
>>> C = codes.random_linear_code(GF(Integer(7)), Integer(11), Integer(5))
>>> Cp = codes.PuncturedCode(C, Integer(3))
>>> E = codes.encoders.PuncturedCodePuncturedMatrixEncoder(Cp)
>>> 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]