Extended code#

Let \(C\) be a linear code of length \(n\) over \(\GF{q}\). The extended code of \(C\) is the code

\[\hat{C} = \{x_{1}x_{2}\dots x_{n+1} \in \GF{q}^{n+1} \,\vert\, x_{1}x_{2}\dots x_{n} \in C \text{ with } x_{1} + x_{2} + \dots + x_{n+1} = 0 \}.\]

See [HP2003] (pp 15-16) for details.

class sage.coding.extended_code.ExtendedCode(C)[source]#

Bases: AbstractLinearCode

Representation of an extended code.

INPUT:

  • C – A linear code

EXAMPLES:

sage: C = codes.random_linear_code(GF(7), 11, 5)
sage: Ce = codes.ExtendedCode(C)
sage: Ce
Extension of [11, 5] linear code over GF(7)

>>> from sage.all import *
>>> C = codes.random_linear_code(GF(Integer(7)), Integer(11), Integer(5))
>>> Ce = codes.ExtendedCode(C)
>>> Ce
Extension of [11, 5] linear code over GF(7)
original_code()[source]#

Return the code which was extended to get self.

EXAMPLES:

sage: C = codes.random_linear_code(GF(7), 11, 5)
sage: Ce = codes.ExtendedCode(C)
sage: Ce.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))
>>> Ce = codes.ExtendedCode(C)
>>> Ce.original_code()
[11, 5] linear code over GF(7)
parity_check_matrix()[source]#

Return a parity check matrix of self.

This matrix is computed directly from original_code().

EXAMPLES:

sage: C = LinearCode(matrix(GF(2),[[1,0,0,1,1],\
                                   [0,1,0,1,0],\
                                   [0,0,1,1,1]]))
sage: C.parity_check_matrix()
[1 0 1 0 1]
[0 1 0 1 1]
sage: Ce = codes.ExtendedCode(C)
sage: Ce.parity_check_matrix()
[1 1 1 1 1 1]
[1 0 1 0 1 0]
[0 1 0 1 1 0]

>>> from sage.all import *
>>> C = LinearCode(matrix(GF(Integer(2)),[[Integer(1),Integer(0),Integer(0),Integer(1),Integer(1)],\
                                   [0,1,0,1,0],\
                                   [0,0,1,1,1]]))
>>> C.parity_check_matrix()
[1 0 1 0 1]
[0 1 0 1 1]
>>> Ce = codes.ExtendedCode(C)
>>> Ce.parity_check_matrix()
[1 1 1 1 1 1]
[1 0 1 0 1 0]
[0 1 0 1 1 0]
random_element()[source]#

Return a random element of self.

This random element is computed directly from the original code, and does not compute a generator matrix of self in the process.

EXAMPLES:

sage: C = codes.random_linear_code(GF(7), 9, 5)
sage: Ce = codes.ExtendedCode(C)
sage: c = Ce.random_element() #random
sage: c in Ce
True

>>> from sage.all import *
>>> C = codes.random_linear_code(GF(Integer(7)), Integer(9), Integer(5))
>>> Ce = codes.ExtendedCode(C)
>>> c = Ce.random_element() #random
>>> c in Ce
True
class sage.coding.extended_code.ExtendedCodeExtendedMatrixEncoder(code)[source]#

Bases: Encoder

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

INPUT:

  • code – The associated code of self.

generator_matrix()[source]#

Return a generator matrix of the associated code of self.

EXAMPLES:

sage: C = LinearCode(matrix(GF(2),[[1,0,0,1,1],\
                                   [0,1,0,1,0],\
                                   [0,0,1,1,1]]))
sage: Ce = codes.ExtendedCode(C)
sage: E = codes.encoders.ExtendedCodeExtendedMatrixEncoder(Ce)
sage: E.generator_matrix()
[1 0 0 1 1 1]
[0 1 0 1 0 0]
[0 0 1 1 1 1]

>>> from sage.all import *
>>> C = LinearCode(matrix(GF(Integer(2)),[[Integer(1),Integer(0),Integer(0),Integer(1),Integer(1)],\
                                   [0,1,0,1,0],\
                                   [0,0,1,1,1]]))
>>> Ce = codes.ExtendedCode(C)
>>> E = codes.encoders.ExtendedCodeExtendedMatrixEncoder(Ce)
>>> E.generator_matrix()
[1 0 0 1 1 1]
[0 1 0 1 0 0]
[0 0 1 1 1 1]
class sage.coding.extended_code.ExtendedCodeOriginalCodeDecoder(code, original_decoder=None, **kwargs)[source]#

Bases: Decoder

Decoder which decodes through a decoder over the original code.

INPUT:

  • code – The associated code of this decoder

  • 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. If original_decoder is set to None, it will use the default decoder of the original code.

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

EXAMPLES:

sage: C = codes.GeneralizedReedSolomonCode(GF(16, 'a').list()[:15], 7)
sage: Ce = codes.ExtendedCode(C)
sage: D = codes.decoders.ExtendedCodeOriginalCodeDecoder(Ce)
sage: D
Decoder of Extension of [15, 7, 9] Reed-Solomon Code over GF(16)
 through Gao 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))
>>> Ce = codes.ExtendedCode(C)
>>> D = codes.decoders.ExtendedCodeOriginalCodeDecoder(Ce)
>>> D
Decoder of Extension of [15, 7, 9] Reed-Solomon Code over GF(16)
 through Gao decoder for [15, 7, 9] Reed-Solomon Code over GF(16)
decode_to_code(y, **kwargs)[source]#

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

EXAMPLES:

sage: C = codes.GeneralizedReedSolomonCode(GF(16, 'a').list()[:15], 7)
sage: Ce = codes.ExtendedCode(C)
sage: D = codes.decoders.ExtendedCodeOriginalCodeDecoder(Ce)
sage: c = Ce.random_element()
sage: Chan = channels.StaticErrorRateChannel(Ce.ambient_space(),
....:                                        D.decoding_radius())
sage: y = Chan(c)
sage: y in Ce
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))
>>> Ce = codes.ExtendedCode(C)
>>> D = codes.decoders.ExtendedCodeOriginalCodeDecoder(Ce)
>>> c = Ce.random_element()
>>> Chan = channels.StaticErrorRateChannel(Ce.ambient_space(),
...                                        D.decoding_radius())
>>> y = Chan(c)
>>> y in Ce
False
>>> D.decode_to_code(y) == c
True

Another example, with a list decoder:

sage: # needs sage.symbolic
sage: C = codes.GeneralizedReedSolomonCode(GF(16, 'a').list()[:15], 7)
sage: Ce = codes.ExtendedCode(C)
sage: Dgrs = C.decoder('GuruswamiSudan', tau=4)
sage: D = codes.decoders.ExtendedCodeOriginalCodeDecoder(Ce,
....:                                                    original_decoder=Dgrs)
sage: c = Ce.random_element()
sage: Chan = channels.StaticErrorRateChannel(Ce.ambient_space(),
....:                                        D.decoding_radius())
sage: y = Chan(c)
sage: y in Ce
False
sage: c in D.decode_to_code(y)
True

>>> from sage.all import *
>>> # needs sage.symbolic
>>> C = codes.GeneralizedReedSolomonCode(GF(Integer(16), 'a').list()[:Integer(15)], Integer(7))
>>> Ce = codes.ExtendedCode(C)
>>> Dgrs = C.decoder('GuruswamiSudan', tau=Integer(4))
>>> D = codes.decoders.ExtendedCodeOriginalCodeDecoder(Ce,
...                                                    original_decoder=Dgrs)
>>> c = Ce.random_element()
>>> Chan = channels.StaticErrorRateChannel(Ce.ambient_space(),
...                                        D.decoding_radius())
>>> y = Chan(c)
>>> y in Ce
False
>>> c in D.decode_to_code(y)
True
decoding_radius(*args, **kwargs)[source]#

Return maximal number of errors that self can decode.

INPUT:

  • *args, **kwargs – arguments and optional arguments are forwarded to original decoder’s decoding_radius method.

EXAMPLES:

sage: C = codes.GeneralizedReedSolomonCode(GF(16, 'a').list()[:15], 7)
sage: Ce = codes.ExtendedCode(C)
sage: D = codes.decoders.ExtendedCodeOriginalCodeDecoder(Ce)
sage: D.decoding_radius()
4

>>> from sage.all import *
>>> C = codes.GeneralizedReedSolomonCode(GF(Integer(16), 'a').list()[:Integer(15)], Integer(7))
>>> Ce = codes.ExtendedCode(C)
>>> D = codes.decoders.ExtendedCodeOriginalCodeDecoder(Ce)
>>> D.decoding_radius()
4
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: Ce = codes.ExtendedCode(C)
sage: D = codes.decoders.ExtendedCodeOriginalCodeDecoder(Ce)
sage: D.original_decoder()
Gao 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))
>>> Ce = codes.ExtendedCode(C)
>>> D = codes.decoders.ExtendedCodeOriginalCodeDecoder(Ce)
>>> D.original_decoder()
Gao decoder for [15, 7, 9] Reed-Solomon Code over GF(16)