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)

Bases: sage.coding.linear_code.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)
original_code()

Returns 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)
parity_check_matrix()

Returns 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]
random_element()

Returns 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
class sage.coding.extended_code.ExtendedCodeExtendedMatrixEncoder(code)

Bases: sage.coding.encoder.Encoder

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

INPUT:

  • code – The associated code of self.
generator_matrix()

Returns 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]
class sage.coding.extended_code.ExtendedCodeOriginalCodeDecoder(code, original_decoder=None, **kwargs)

Bases: sage.coding.decoder.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)
decode_to_code(y, **kwargs)

Decodes 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

Another example, with a list decoder:

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
decoding_radius(*args, **kwargs)

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