Decoders for AG codes

This module implements decoders for evaluation and differential AG codes.

The implemented algorithm for unique decoding of AG codes, named K, is from [LBO2014] and [Lee2016].

EXAMPLES:

sage: F.<a> = GF(9)
sage: A2.<x,y> = AffineSpace(F, 2)
sage: C = Curve(y^3 + y - x^4)
sage: Q, = C.places_at_infinity()
sage: O = C(0,0).place()
sage: pls = C.places()
sage: pls.remove(Q)
sage: pls.remove(O)
sage: G = -O + 18*Q
sage: code = codes.EvaluationAGCode(pls, G)  # long time
sage: code                                   # long time
[26, 15] evaluation AG code over GF(9)
sage: decoder = code.decoder('K')            # long time
sage: tau = decoder.decoding_radius()        # long time
sage: tau                                    # long time
4

>>> from sage.all import *
>>> F = GF(Integer(9), names=('a',)); (a,) = F._first_ngens(1)
>>> A2 = AffineSpace(F, Integer(2), names=('x', 'y',)); (x, y,) = A2._first_ngens(2)
>>> C = Curve(y**Integer(3) + y - x**Integer(4))
>>> Q, = C.places_at_infinity()
>>> O = C(Integer(0),Integer(0)).place()
>>> pls = C.places()
>>> pls.remove(Q)
>>> pls.remove(O)
>>> G = -O + Integer(18)*Q
>>> code = codes.EvaluationAGCode(pls, G)  # long time
>>> code                                   # long time
[26, 15] evaluation AG code over GF(9)
>>> decoder = code.decoder('K')            # long time
>>> tau = decoder.decoding_radius()        # long time
>>> tau                                    # long time
4

The decoder is now ready for correcting vectors received from a noisy channel:

sage: # long time
sage: channel = channels.StaticErrorRateChannel(code.ambient_space(), tau)
sage: message_space = decoder.message_space()
sage: message = message_space.random_element()
sage: encoder = decoder.connected_encoder()
sage: sent_codeword = encoder.encode(message)
sage: received_vector = channel(sent_codeword)
sage: (received_vector - sent_codeword).hamming_weight()
4
sage: decoder.decode_to_code(received_vector) == sent_codeword
True
sage: decoder.decode_to_message(received_vector) == message
True

>>> from sage.all import *
>>> # long time
>>> channel = channels.StaticErrorRateChannel(code.ambient_space(), tau)
>>> message_space = decoder.message_space()
>>> message = message_space.random_element()
>>> encoder = decoder.connected_encoder()
>>> sent_codeword = encoder.encode(message)
>>> received_vector = channel(sent_codeword)
>>> (received_vector - sent_codeword).hamming_weight()
4
>>> decoder.decode_to_code(received_vector) == sent_codeword
True
>>> decoder.decode_to_message(received_vector) == message
True

AUTHORS:

  • Kwankyu Lee (2019-03): initial version

class sage.coding.ag_code_decoders.Decoder_K[source]

Bases: object

Common base class for the implementation of decoding algorithm K for AG codes.

EXAMPLES:

sage: F.<a> = GF(4)
sage: P.<x,y> = AffineSpace(F, 2);
sage: C = Curve(y^2 + y - x^3)
sage: pls = C.places()
sage: p = C([0,0])
sage: Q, = p.places()
sage: D = [pl for pl in pls if pl != Q]
sage: G = 5*Q
sage: from sage.coding.ag_code_decoders import EvaluationAGCodeDecoder_K
sage: circuit = EvaluationAGCodeDecoder_K(D, G, Q)

>>> from sage.all import *
>>> F = GF(Integer(4), names=('a',)); (a,) = F._first_ngens(1)
>>> P = AffineSpace(F, Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2);
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> pls = C.places()
>>> p = C([Integer(0),Integer(0)])
>>> Q, = p.places()
>>> D = [pl for pl in pls if pl != Q]
>>> G = Integer(5)*Q
>>> from sage.coding.ag_code_decoders import EvaluationAGCodeDecoder_K
>>> circuit = EvaluationAGCodeDecoder_K(D, G, Q)
decode(received_vector, verbose=False, detect_decoding_failure=True, detect_Q_polynomial=True)[source]

Return the message vector that corresponds to the corrected codeword from the received vector.

INPUT:

  • received_vector – a received vector in the ambient space of the code

  • verbose – boolean; if True, verbose information is printed

  • detect_decoding_failure – boolean; if True, early failure detection is activated

  • detect_Q_polynomial – boolean; if True, a Q-polynomial is detected for fast decoding

If decoding fails for some reason, DecodingError is raised. The message contained in the exception indicates the type of the decoding failure.

encode(message)[source]

Encode message to a codeword.

info[source]
class sage.coding.ag_code_decoders.Decoder_K_extension[source]

Bases: object

Common base class for decoding algorithm K for AG codes via constant field extension.

INPUT:

  • pls – list of places of a function field

  • G – a divisor of the function field

  • Q – a non-rational place

  • verbose – if True, verbose information is printed

EXAMPLES:

sage: A.<x,y> = AffineSpace(GF(4), 2)
sage: C = Curve(y^2 + y - x^3)
sage: pls = C.places()
sage: F = C.function_field()
sage: G = 1*F.get_place(4)
sage: code = codes.EvaluationAGCode(pls, G)
sage: dec = code.decoder('K'); dec  # long time
Unique decoder for [9, 4] evaluation AG code over GF(4)

>>> from sage.all import *
>>> A = AffineSpace(GF(Integer(4)), Integer(2), names=('x', 'y',)); (x, y,) = A._first_ngens(2)
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> pls = C.places()
>>> F = C.function_field()
>>> G = Integer(1)*F.get_place(Integer(4))
>>> code = codes.EvaluationAGCode(pls, G)
>>> dec = code.decoder('K'); dec  # long time
Unique decoder for [9, 4] evaluation AG code over GF(4)


sage: P.<x,y> = ProjectiveSpace(GF(4), 1)
sage: C = Curve(P)
sage: pls = C.places()
sage: len(pls)
5
sage: F = C.function_field()
sage: G = F.get_place(2).divisor()
sage: code = codes.EvaluationAGCode(pls, G)
sage: code.decoder('K')
Unique decoder for [5, 3] evaluation AG code over GF(4)

>>> from sage.all import *
>>> P = ProjectiveSpace(GF(Integer(4)), Integer(1), names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> C = Curve(P)
>>> pls = C.places()
>>> len(pls)
5
>>> F = C.function_field()
>>> G = F.get_place(Integer(2)).divisor()
>>> code = codes.EvaluationAGCode(pls, G)
>>> code.decoder('K')
Unique decoder for [5, 3] evaluation AG code over GF(4)
decode(received_vector, **kwargs)[source]

Decode the received vector to a message.

INPUT:

  • received_vector – a vector in the ambient space of the code

encode(message, **kwargs)[source]

Encode message to a codeword.

info[source]
class sage.coding.ag_code_decoders.DifferentialAGCodeDecoder_K[source]

Bases: Decoder_K

This class implements the decoding algorithm K for differential AG codes.

INPUT:

  • pls – list of places of a function field

  • G – a divisor of the function field

  • Q – a rational place not in pls

  • verbose – if True, verbose information is printed

EXAMPLES:

sage: F.<a> = GF(4)
sage: P.<x,y> = AffineSpace(F, 2);
sage: C = Curve(y^2 + y - x^3)
sage: pls = C.places()
sage: p = C([0,0])
sage: Q, = p.places()
sage: D = [pl for pl in pls if pl != Q]
sage: G = 5*Q
sage: from sage.coding.ag_code_decoders import DifferentialAGCodeDecoder_K
sage: circuit = DifferentialAGCodeDecoder_K(D, G, Q)  # long time
sage: rv = vector([1, a, 1, a, 1, a, a, a + 1])
sage: cw = circuit.encode(circuit.decode(rv))  # long time
sage: rv - cw  # long time
(0, 0, 0, a + 1, 1, 0, 0, 0)
sage: circuit.info['designed_distance']  # long time
5
sage: circuit.info['decoding_radius']  # long time
2

>>> from sage.all import *
>>> F = GF(Integer(4), names=('a',)); (a,) = F._first_ngens(1)
>>> P = AffineSpace(F, Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2);
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> pls = C.places()
>>> p = C([Integer(0),Integer(0)])
>>> Q, = p.places()
>>> D = [pl for pl in pls if pl != Q]
>>> G = Integer(5)*Q
>>> from sage.coding.ag_code_decoders import DifferentialAGCodeDecoder_K
>>> circuit = DifferentialAGCodeDecoder_K(D, G, Q)  # long time
>>> rv = vector([Integer(1), a, Integer(1), a, Integer(1), a, a, a + Integer(1)])
>>> cw = circuit.encode(circuit.decode(rv))  # long time
>>> rv - cw  # long time
(0, 0, 0, a + 1, 1, 0, 0, 0)
>>> circuit.info['designed_distance']  # long time
5
>>> circuit.info['decoding_radius']  # long time
2
class sage.coding.ag_code_decoders.DifferentialAGCodeDecoder_K_extension[source]

Bases: Decoder_K_extension

This class implements the decoding algorithm K for differential AG codes via constant field extension.

INPUT:

  • pls – list of places of a function field

  • G – a divisor of the function field

  • Q – a non-rational place

  • verbose – if True, verbose information is printed

EXAMPLES:

sage: F.<a> = GF(4)
sage: A.<x,y> = AffineSpace(F, 2)
sage: C = Curve(y^2 + y - x^3)
sage: pls = C.places()
sage: F = C.function_field()
sage: G = 1*F.get_place(4)
sage: code = codes.DifferentialAGCode(pls, G)
sage: Q = F.get_place(3)
sage: from sage.coding.ag_code_decoders import DifferentialAGCodeDecoder_K_extension
sage: circuit = DifferentialAGCodeDecoder_K_extension(pls, G, Q)  # long time
sage: cw = code.random_element()
sage: rv = cw + vector([0,0,a,0,0,0,0,0,0])
sage: circuit.encode(circuit.decode(circuit._lift(rv))) == circuit._lift(cw)  # long time
True

>>> from sage.all import *
>>> F = GF(Integer(4), names=('a',)); (a,) = F._first_ngens(1)
>>> A = AffineSpace(F, Integer(2), names=('x', 'y',)); (x, y,) = A._first_ngens(2)
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> pls = C.places()
>>> F = C.function_field()
>>> G = Integer(1)*F.get_place(Integer(4))
>>> code = codes.DifferentialAGCode(pls, G)
>>> Q = F.get_place(Integer(3))
>>> from sage.coding.ag_code_decoders import DifferentialAGCodeDecoder_K_extension
>>> circuit = DifferentialAGCodeDecoder_K_extension(pls, G, Q)  # long time
>>> cw = code.random_element()
>>> rv = cw + vector([Integer(0),Integer(0),a,Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0)])
>>> circuit.encode(circuit.decode(circuit._lift(rv))) == circuit._lift(cw)  # long time
True
class sage.coding.ag_code_decoders.DifferentialAGCodeEncoder(code, decoder=None)[source]

Bases: Encoder

Encoder of a differential AG code.

INPUT:

  • code – a differential AG code

  • decoder – a decoder of the code

EXAMPLES:

sage: F.<a> = GF(4)
sage: P.<x,y> = AffineSpace(F, 2);
sage: C = Curve(y^2 + y - x^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: p = C([0,0])
sage: Q, = p.places()
sage: D = [pl for pl in pls if pl != Q]
sage: G = 5*Q
sage: code = codes.DifferentialAGCode(D, G)
sage: dec = code.decoder('K', Q)  # long time
sage: enc = dec.connected_encoder(); enc  # long time
Encoder for [8, 3] differential AG code over GF(4)

>>> from sage.all import *
>>> F = GF(Integer(4), names=('a',)); (a,) = F._first_ngens(1)
>>> P = AffineSpace(F, Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2);
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> p = C([Integer(0),Integer(0)])
>>> Q, = p.places()
>>> D = [pl for pl in pls if pl != Q]
>>> G = Integer(5)*Q
>>> code = codes.DifferentialAGCode(D, G)
>>> dec = code.decoder('K', Q)  # long time
>>> enc = dec.connected_encoder(); enc  # long time
Encoder for [8, 3] differential AG code over GF(4)
encode(message)[source]

Return the codeword encoded from the message.

INPUT:

  • message – a vector in the message space

EXAMPLES:

sage: F.<a> = GF(4)
sage: P.<x,y> = AffineSpace(F, 2)
sage: C = Curve(y^2 + y - x^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: p = C([0,0])
sage: Q, = p.places()
sage: D = [pl for pl in pls if pl != Q]
sage: G = 5*Q
sage: code = codes.DifferentialAGCode(D, G)      # long time
sage: dec = code.decoder('K', Q)                 # long time
sage: enc = dec.connected_encoder()              # long time
sage: msg = enc.message_space().random_element() # long time
sage: codeword = enc.encode(msg)                 # long time
sage: enc.unencode(codeword) == msg              # long time
True

>>> from sage.all import *
>>> F = GF(Integer(4), names=('a',)); (a,) = F._first_ngens(1)
>>> P = AffineSpace(F, Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> p = C([Integer(0),Integer(0)])
>>> Q, = p.places()
>>> D = [pl for pl in pls if pl != Q]
>>> G = Integer(5)*Q
>>> code = codes.DifferentialAGCode(D, G)      # long time
>>> dec = code.decoder('K', Q)                 # long time
>>> enc = dec.connected_encoder()              # long time
>>> msg = enc.message_space().random_element() # long time
>>> codeword = enc.encode(msg)                 # long time
>>> enc.unencode(codeword) == msg              # long time
True
unencode_nocheck(codeword)[source]

Return the message unencoded from codeword.

INPUT:

  • codeword – a vector in the code

EXAMPLES:

sage: F.<a> = GF(4)
sage: P.<x,y> = AffineSpace(F, 2)
sage: C = Curve(y^2 + y - x^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: p = C([0,0])
sage: Q, = p.places()
sage: D = [pl for pl in pls if pl != Q]
sage: G = 5*Q
sage: code = codes.DifferentialAGCode(D, G)      # long time
sage: dec = code.decoder('K', Q)                 # long time
sage: enc = dec.connected_encoder()              # long time
sage: msg = enc.message_space().random_element() # long time
sage: codeword = enc.encode(msg)                 # long time
sage: enc.unencode(codeword) in enc.message_space()  # indirect doctest, long time
True

>>> from sage.all import *
>>> F = GF(Integer(4), names=('a',)); (a,) = F._first_ngens(1)
>>> P = AffineSpace(F, Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> p = C([Integer(0),Integer(0)])
>>> Q, = p.places()
>>> D = [pl for pl in pls if pl != Q]
>>> G = Integer(5)*Q
>>> code = codes.DifferentialAGCode(D, G)      # long time
>>> dec = code.decoder('K', Q)                 # long time
>>> enc = dec.connected_encoder()              # long time
>>> msg = enc.message_space().random_element() # long time
>>> codeword = enc.encode(msg)                 # long time
>>> enc.unencode(codeword) in enc.message_space()  # indirect doctest, long time
True
class sage.coding.ag_code_decoders.DifferentialAGCodeUniqueDecoder(code, Q=None, basis=None, verbose=False)[source]

Bases: Decoder

Unique decoder for a differential AG codes.

INPUT:

  • code – an evaluation AG code

  • Q – (optional) a place, not one of the places supporting the code

  • basis – (optional) a basis of the space of differentials to take residues

  • verbose – if True, verbose information is printed

EXAMPLES:

sage: F.<a> = GF(4)
sage: P.<x,y> = AffineSpace(F, 2);
sage: C = Curve(y^2 + y - x^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: p = C(0,0)
sage: Q, = p.places()
sage: D = [pl for pl in pls if pl != Q]
sage: G = 5*Q
sage: code = codes.DifferentialAGCode(D, G)
sage: chan = channels.StaticErrorRateChannel(code.ambient_space(), 2)
sage: rv = chan.transmit(code.random_element())  # long time
sage: dec = code.decoder('K', Q)  # long time
sage: enc = dec.connected_encoder()  # long time
sage: enc.encode(dec.decode_to_message(rv)) in code  # long time
True

>>> from sage.all import *
>>> F = GF(Integer(4), names=('a',)); (a,) = F._first_ngens(1)
>>> P = AffineSpace(F, Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2);
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> p = C(Integer(0),Integer(0))
>>> Q, = p.places()
>>> D = [pl for pl in pls if pl != Q]
>>> G = Integer(5)*Q
>>> code = codes.DifferentialAGCode(D, G)
>>> chan = channels.StaticErrorRateChannel(code.ambient_space(), Integer(2))
>>> rv = chan.transmit(code.random_element())  # long time
>>> dec = code.decoder('K', Q)  # long time
>>> enc = dec.connected_encoder()  # long time
>>> enc.encode(dec.decode_to_message(rv)) in code  # long time
True

If basis is given, that defines the associated residue encoding map:

sage: basis = tuple((G - sum(D)).basis_differential_space())
sage: w = basis[0]
sage: cw = vector(w.residue(p) for p in D)
sage: dec2 = code.decoder('K', Q, basis)  # long time
sage: enc2 = dec2.connected_encoder()  # long time
sage: temp = enc2.unencode(cw); temp  # long time
(1, 0, 0)
sage: enc2.encode(temp) == cw  # long time
True
sage: w = basis[1]
sage: cw = vector(w.residue(p) for p in D)
sage: temp = enc2.unencode(cw); temp  # long time
(0, 1, 0)
sage: enc2.encode(temp) == cw  # long time
True

>>> from sage.all import *
>>> basis = tuple((G - sum(D)).basis_differential_space())
>>> w = basis[Integer(0)]
>>> cw = vector(w.residue(p) for p in D)
>>> dec2 = code.decoder('K', Q, basis)  # long time
>>> enc2 = dec2.connected_encoder()  # long time
>>> temp = enc2.unencode(cw); temp  # long time
(1, 0, 0)
>>> enc2.encode(temp) == cw  # long time
True
>>> w = basis[Integer(1)]
>>> cw = vector(w.residue(p) for p in D)
>>> temp = enc2.unencode(cw); temp  # long time
(0, 1, 0)
>>> enc2.encode(temp) == cw  # long time
True

The default basis is given by code.basis_differentials().

connected_encoder(*args, **kwargs)[source]

Return the connected encoder for this decoder.

INPUT:

  • args, kwargs – all additional arguments are forwarded to the constructor of the connected encoder

EXAMPLES:

sage: F.<a> = GF(4)
sage: P.<x,y> = AffineSpace(F, 2);
sage: C = Curve(y^2 + y - x^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: p = C([0,0])
sage: Q, = p.places()
sage: D = [pl for pl in pls if pl != Q]
sage: G = 5*Q
sage: code = codes.DifferentialAGCode(D, G)  # long time
sage: dec = code.decoder('K', Q)             # long time
sage: dec.connected_encoder()                # long time
Encoder for [8, 3] differential AG code over GF(4)

>>> from sage.all import *
>>> F = GF(Integer(4), names=('a',)); (a,) = F._first_ngens(1)
>>> P = AffineSpace(F, Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2);
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> p = C([Integer(0),Integer(0)])
>>> Q, = p.places()
>>> D = [pl for pl in pls if pl != Q]
>>> G = Integer(5)*Q
>>> code = codes.DifferentialAGCode(D, G)  # long time
>>> dec = code.decoder('K', Q)             # long time
>>> dec.connected_encoder()                # long time
Encoder for [8, 3] differential AG code over GF(4)
decode_to_code(received_vector, **kwargs)[source]

Return the codeword decoded from received_vector.

INPUT:

  • received_vector – a vector in the ambient space of the code

  • verbose – boolean; if True, verbose information on the decoding process is printed

EXAMPLES:

sage: F.<a> = GF(4)
sage: P.<x,y> = AffineSpace(F, 2);
sage: C = Curve(y^2 + y - x^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: p = C([0,0])
sage: Q, = p.places()
sage: D = [pl for pl in pls if pl != Q]
sage: G = 5*Q
sage: code = codes.DifferentialAGCode(D, G)  # long time
sage: dec = code.decoder('K', Q)             # long time
sage: enc = dec.connected_encoder()          # long time
sage: code = dec.code()                      # long time
sage: chan = channels.StaticErrorRateChannel(code.ambient_space(), 2) # long time
sage: rv = chan.transmit(code.random_element())  # long time
sage: cw = dec.decode_to_code(rv)                # long time
sage: (cw - rv).hamming_weight() == 2            # long time
True

>>> from sage.all import *
>>> F = GF(Integer(4), names=('a',)); (a,) = F._first_ngens(1)
>>> P = AffineSpace(F, Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2);
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> p = C([Integer(0),Integer(0)])
>>> Q, = p.places()
>>> D = [pl for pl in pls if pl != Q]
>>> G = Integer(5)*Q
>>> code = codes.DifferentialAGCode(D, G)  # long time
>>> dec = code.decoder('K', Q)             # long time
>>> enc = dec.connected_encoder()          # long time
>>> code = dec.code()                      # long time
>>> chan = channels.StaticErrorRateChannel(code.ambient_space(), Integer(2)) # long time
>>> rv = chan.transmit(code.random_element())  # long time
>>> cw = dec.decode_to_code(rv)                # long time
>>> (cw - rv).hamming_weight() == Integer(2)            # long time
True
decode_to_message(received_vector, **kwargs)[source]

Return the message decoded from received_vector.

INPUT:

  • received_vector – a vector in the ambient space of the code

  • verbose – boolean; if True, verbose information on the decoding process is printed

EXAMPLES:

sage: F.<a> = GF(4)
sage: P.<x,y> = AffineSpace(F, 2);
sage: C = Curve(y^2 + y - x^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: p = C([0,0])
sage: Q, = p.places()
sage: D = [pl for pl in pls if pl != Q]
sage: G = 5*Q
sage: code = codes.DifferentialAGCode(D, G)  # long time
sage: dec = code.decoder('K', Q)             # long time
sage: enc = dec.connected_encoder()          # long time
sage: code = dec.code()                      # long time
sage: chan = channels.StaticErrorRateChannel(code.ambient_space(), 2)  # long time
sage: rv = chan.transmit(code.random_element())  # long time
sage: msg = dec.decode_to_message(rv)            # long time
sage: cw = enc.encode(msg)                       # long time
sage: (cw - rv).hamming_weight() == 2            # long time
True

>>> from sage.all import *
>>> F = GF(Integer(4), names=('a',)); (a,) = F._first_ngens(1)
>>> P = AffineSpace(F, Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2);
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> p = C([Integer(0),Integer(0)])
>>> Q, = p.places()
>>> D = [pl for pl in pls if pl != Q]
>>> G = Integer(5)*Q
>>> code = codes.DifferentialAGCode(D, G)  # long time
>>> dec = code.decoder('K', Q)             # long time
>>> enc = dec.connected_encoder()          # long time
>>> code = dec.code()                      # long time
>>> chan = channels.StaticErrorRateChannel(code.ambient_space(), Integer(2))  # long time
>>> rv = chan.transmit(code.random_element())  # long time
>>> msg = dec.decode_to_message(rv)            # long time
>>> cw = enc.encode(msg)                       # long time
>>> (cw - rv).hamming_weight() == Integer(2)            # long time
True
decoding_radius()[source]

Return the decoding radius of the decoder.

EXAMPLES:

sage: F.<a> = GF(4)
sage: P.<x,y> = AffineSpace(F, 2);
sage: C = Curve(y^2 + y - x^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: p = C([0,0])
sage: Q, = p.places()
sage: D = [pl for pl in pls if pl != Q]
sage: G = 5*Q
sage: code = codes.DifferentialAGCode(D, G)  # long time
sage: dec = code.decoder('K', Q)             # long time
sage: dec.decoding_radius()                  # long time
2

>>> from sage.all import *
>>> F = GF(Integer(4), names=('a',)); (a,) = F._first_ngens(1)
>>> P = AffineSpace(F, Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2);
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> p = C([Integer(0),Integer(0)])
>>> Q, = p.places()
>>> D = [pl for pl in pls if pl != Q]
>>> G = Integer(5)*Q
>>> code = codes.DifferentialAGCode(D, G)  # long time
>>> dec = code.decoder('K', Q)             # long time
>>> dec.decoding_radius()                  # long time
2
class sage.coding.ag_code_decoders.EvaluationAGCodeDecoder_K[source]

Bases: Decoder_K

This class implements the decoding algorithm K for evaluation AG codes.

INPUT:

  • pls – list of places of a function field

  • G – a divisor of the function field

  • Q – a rational place not in pls

  • verbose – if True, verbose information is printed

EXAMPLES:

sage: F.<a> = GF(4)
sage: P.<x,y> = AffineSpace(F, 2);
sage: C = Curve(y^2 + y - x^3)
sage: pls = C.places()
sage: p = C([0,0])
sage: Q, = p.places()
sage: D = [pl for pl in pls if pl != Q]
sage: G = 5*Q
sage: from sage.coding.ag_code_decoders import EvaluationAGCodeDecoder_K
sage: circuit = EvaluationAGCodeDecoder_K(D, G, Q)
sage: rv = vector([a, 0, 0, a, 1, 1, a + 1, 0])
sage: cw = circuit.encode(circuit.decode(rv))
sage: rv - cw
(a + 1, 0, 0, 0, 0, 0, 0, 0)
sage: circuit.info['designed_distance']
3
sage: circuit.info['decoding_radius']
1

>>> from sage.all import *
>>> F = GF(Integer(4), names=('a',)); (a,) = F._first_ngens(1)
>>> P = AffineSpace(F, Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2);
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> pls = C.places()
>>> p = C([Integer(0),Integer(0)])
>>> Q, = p.places()
>>> D = [pl for pl in pls if pl != Q]
>>> G = Integer(5)*Q
>>> from sage.coding.ag_code_decoders import EvaluationAGCodeDecoder_K
>>> circuit = EvaluationAGCodeDecoder_K(D, G, Q)
>>> rv = vector([a, Integer(0), Integer(0), a, Integer(1), Integer(1), a + Integer(1), Integer(0)])
>>> cw = circuit.encode(circuit.decode(rv))
>>> rv - cw
(a + 1, 0, 0, 0, 0, 0, 0, 0)
>>> circuit.info['designed_distance']
3
>>> circuit.info['decoding_radius']
1
class sage.coding.ag_code_decoders.EvaluationAGCodeDecoder_K_extension[source]

Bases: Decoder_K_extension

This class implements the decoding algorithm K for evaluation AG codes via constant field extension.

INPUT:

  • pls – list of places of a function field

  • G – a divisor of the function field

  • Q – a non-rational place

  • verbose – if True, verbose information is printed

EXAMPLES:

sage: F.<a> = GF(4)
sage: A.<x,y> = AffineSpace(F, 2)
sage: C = Curve(y^2 + y - x^3)
sage: pls = C.places()
sage: F = C.function_field()
sage: G = 1*F.get_place(4)
sage: code = codes.EvaluationAGCode(pls, G)
sage: Q = F.get_place(3)
sage: from sage.coding.ag_code_decoders import EvaluationAGCodeDecoder_K_extension
sage: circuit = EvaluationAGCodeDecoder_K_extension(pls, G, Q)
sage: cw = code.random_element()
sage: rv = cw + vector([0,1,1,0,0,0,0,0,0])
sage: circuit.encode(circuit.decode(circuit._lift(rv))) == circuit._lift(cw)
True

>>> from sage.all import *
>>> F = GF(Integer(4), names=('a',)); (a,) = F._first_ngens(1)
>>> A = AffineSpace(F, Integer(2), names=('x', 'y',)); (x, y,) = A._first_ngens(2)
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> pls = C.places()
>>> F = C.function_field()
>>> G = Integer(1)*F.get_place(Integer(4))
>>> code = codes.EvaluationAGCode(pls, G)
>>> Q = F.get_place(Integer(3))
>>> from sage.coding.ag_code_decoders import EvaluationAGCodeDecoder_K_extension
>>> circuit = EvaluationAGCodeDecoder_K_extension(pls, G, Q)
>>> cw = code.random_element()
>>> rv = cw + vector([Integer(0),Integer(1),Integer(1),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0)])
>>> circuit.encode(circuit.decode(circuit._lift(rv))) == circuit._lift(cw)
True
class sage.coding.ag_code_decoders.EvaluationAGCodeEncoder(code, decoder=None)[source]

Bases: Encoder

Encoder of an evaluation AG code.

INPUT:

  • code – an evaluation AG code

  • decoder – a decoder of the code

EXAMPLES:

sage: F.<a> = GF(4)
sage: P.<x,y> = AffineSpace(F, 2);
sage: C = Curve(y^2 + y - x^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: p = C([0,0])
sage: Q, = p.places()
sage: D = [pl for pl in pls if pl != Q]
sage: G = 5*Q
sage: code = codes.EvaluationAGCode(D, G)
sage: dec = code.decoder('K', Q)
sage: enc = dec.connected_encoder()
sage: enc
Encoder for [8, 5] evaluation AG code over GF(4)

>>> from sage.all import *
>>> F = GF(Integer(4), names=('a',)); (a,) = F._first_ngens(1)
>>> P = AffineSpace(F, Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2);
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> p = C([Integer(0),Integer(0)])
>>> Q, = p.places()
>>> D = [pl for pl in pls if pl != Q]
>>> G = Integer(5)*Q
>>> code = codes.EvaluationAGCode(D, G)
>>> dec = code.decoder('K', Q)
>>> enc = dec.connected_encoder()
>>> enc
Encoder for [8, 5] evaluation AG code over GF(4)
encode(message)[source]

Return the codeword encoded from the message.

INPUT:

  • message – a vector in the message space

EXAMPLES:

sage: F.<a> = GF(4)
sage: P.<x,y> = AffineSpace(F, 2)
sage: C = Curve(y^2 + y - x^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: p = C([0,0])
sage: Q, = p.places()
sage: D = [pl for pl in pls if pl != Q]
sage: G = 5*Q
sage: code = codes.EvaluationAGCode(D, G)        # long time
sage: dec = code.decoder('K', Q)                 # long time
sage: enc = dec.connected_encoder()              # long time
sage: msg = enc.message_space().random_element() # long time
sage: codeword = enc.encode(msg)                 # long time
sage: enc.unencode(codeword) == msg              # long time
True

>>> from sage.all import *
>>> F = GF(Integer(4), names=('a',)); (a,) = F._first_ngens(1)
>>> P = AffineSpace(F, Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> p = C([Integer(0),Integer(0)])
>>> Q, = p.places()
>>> D = [pl for pl in pls if pl != Q]
>>> G = Integer(5)*Q
>>> code = codes.EvaluationAGCode(D, G)        # long time
>>> dec = code.decoder('K', Q)                 # long time
>>> enc = dec.connected_encoder()              # long time
>>> msg = enc.message_space().random_element() # long time
>>> codeword = enc.encode(msg)                 # long time
>>> enc.unencode(codeword) == msg              # long time
True
unencode_nocheck(codeword)[source]

Return the message unencoded from codeword.

INPUT:

  • codeword – a vector in the code

EXAMPLES:

sage: F.<a> = GF(4)
sage: P.<x,y> = AffineSpace(F, 2)
sage: C = Curve(y^2 + y - x^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: p = C([0,0])
sage: Q, = p.places()
sage: D = [pl for pl in pls if pl != Q]
sage: G = 5*Q
sage: code = codes.EvaluationAGCode(D, G)        # long time
sage: dec = code.decoder('K', Q)                 # long time
sage: enc = dec.connected_encoder()              # long time
sage: msg = enc.message_space().random_element() # long time
sage: codeword = enc.encode(msg)                 # long time
sage: enc.unencode(codeword) in enc.message_space()  # long time, indirect doctest
True

>>> from sage.all import *
>>> F = GF(Integer(4), names=('a',)); (a,) = F._first_ngens(1)
>>> P = AffineSpace(F, Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> p = C([Integer(0),Integer(0)])
>>> Q, = p.places()
>>> D = [pl for pl in pls if pl != Q]
>>> G = Integer(5)*Q
>>> code = codes.EvaluationAGCode(D, G)        # long time
>>> dec = code.decoder('K', Q)                 # long time
>>> enc = dec.connected_encoder()              # long time
>>> msg = enc.message_space().random_element() # long time
>>> codeword = enc.encode(msg)                 # long time
>>> enc.unencode(codeword) in enc.message_space()  # long time, indirect doctest
True
class sage.coding.ag_code_decoders.EvaluationAGCodeUniqueDecoder(code, Q=None, basis=None, verbose=False)[source]

Bases: Decoder

Unique decoder for evaluation AG codes.

INPUT:

  • code – an evaluation AG code

  • Q – (optional) a place, not one of the places supporting the code

  • basis – (optional) a basis of the space of functions to evaluate

  • verbose – if True, verbose information is printed

EXAMPLES:

sage: k.<a> = GF(4)
sage: P.<x,y> = AffineSpace(k, 2);
sage: C = Curve(y^2 + y - x^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: p = C(0,0)
sage: Q, = p.places()
sage: D = [pl for pl in pls if pl != Q]
sage: G = 5*Q
sage: code = codes.EvaluationAGCode(D, G)
sage: dec = code.decoder('K', Q)
sage: enc = dec.connected_encoder()
sage: chan = channels.StaticErrorRateChannel(code.ambient_space(), 1)
sage: rv = chan.transmit(code.random_element())
sage: enc.encode(dec.decode_to_message(rv)) in code
True

>>> from sage.all import *
>>> k = GF(Integer(4), names=('a',)); (a,) = k._first_ngens(1)
>>> P = AffineSpace(k, Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2);
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> p = C(Integer(0),Integer(0))
>>> Q, = p.places()
>>> D = [pl for pl in pls if pl != Q]
>>> G = Integer(5)*Q
>>> code = codes.EvaluationAGCode(D, G)
>>> dec = code.decoder('K', Q)
>>> enc = dec.connected_encoder()
>>> chan = channels.StaticErrorRateChannel(code.ambient_space(), Integer(1))
>>> rv = chan.transmit(code.random_element())
>>> enc.encode(dec.decode_to_message(rv)) in code
True

If basis is given, that defines the associated evaluation encoding map:

sage: basis = tuple(G.basis_function_space())
sage: dec2 = code.decoder('K', Q, basis)
sage: enc2 = dec2.connected_encoder()
sage: f = basis[0]
sage: cw = vector(f.evaluate(p) for p in D)
sage: enc2.unencode(cw)
(1, 0, 0, 0, 0)
sage: enc2.encode(_) == cw
True
sage: f = basis[1]
sage: cw = vector(f.evaluate(p) for p in D)
sage: enc2.unencode(cw)
(0, 1, 0, 0, 0)
sage: enc2.encode(_) == cw
True

>>> from sage.all import *
>>> basis = tuple(G.basis_function_space())
>>> dec2 = code.decoder('K', Q, basis)
>>> enc2 = dec2.connected_encoder()
>>> f = basis[Integer(0)]
>>> cw = vector(f.evaluate(p) for p in D)
>>> enc2.unencode(cw)
(1, 0, 0, 0, 0)
>>> enc2.encode(_) == cw
True
>>> f = basis[Integer(1)]
>>> cw = vector(f.evaluate(p) for p in D)
>>> enc2.unencode(cw)
(0, 1, 0, 0, 0)
>>> enc2.encode(_) == cw
True

The default basis is given by code.basis_functions().

connected_encoder(*args, **kwargs)[source]

Return the connected encoder for this decoder.

INPUT:

  • args, kwargs – all additional arguments are forwarded to the constructor of the connected encoder

EXAMPLES:

sage: F.<a> = GF(4)
sage: P.<x,y> = AffineSpace(F, 2)
sage: C = Curve(y^2 + y - x^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: p = C([0,0])
sage: Q, = p.places()
sage: D = [pl for pl in pls if pl != Q]
sage: G = 5*Q
sage: code = codes.EvaluationAGCode(D, G)  # long time
sage: dec = code.decoder('K', Q)           # long time
sage: dec.connected_encoder()              # long time
Encoder for [8, 5] evaluation AG code over GF(4)

>>> from sage.all import *
>>> F = GF(Integer(4), names=('a',)); (a,) = F._first_ngens(1)
>>> P = AffineSpace(F, Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> p = C([Integer(0),Integer(0)])
>>> Q, = p.places()
>>> D = [pl for pl in pls if pl != Q]
>>> G = Integer(5)*Q
>>> code = codes.EvaluationAGCode(D, G)  # long time
>>> dec = code.decoder('K', Q)           # long time
>>> dec.connected_encoder()              # long time
Encoder for [8, 5] evaluation AG code over GF(4)
decode_to_code(received_vector, **kwargs)[source]

Return the codeword decoded from received_vector.

INPUT:

  • received_vector – a vector in the ambient space of the code

  • verbose – boolean; if True, verbose information on the decoding process is printed

EXAMPLES:

sage: F.<a> = GF(4)
sage: P.<x,y> = AffineSpace(F, 2)
sage: C = Curve(y^2 + y - x^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: p = C([0,0])
sage: Q, = p.places()
sage: D = [pl for pl in pls if pl != Q]
sage: G = 5*Q
sage: code = codes.EvaluationAGCode(D, G)  # long time
sage: dec = code.decoder('K', Q)           # long time
sage: code = dec.code()                    # long time
sage: chan = channels.StaticErrorRateChannel(code.ambient_space(), 1)  # long time
sage: rv = chan.transmit(code.random_element())  # long time
sage: cw = dec.decode_to_code(rv)                # long time
sage: (cw - rv).hamming_weight() == 1            # long time
True

>>> from sage.all import *
>>> F = GF(Integer(4), names=('a',)); (a,) = F._first_ngens(1)
>>> P = AffineSpace(F, Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> p = C([Integer(0),Integer(0)])
>>> Q, = p.places()
>>> D = [pl for pl in pls if pl != Q]
>>> G = Integer(5)*Q
>>> code = codes.EvaluationAGCode(D, G)  # long time
>>> dec = code.decoder('K', Q)           # long time
>>> code = dec.code()                    # long time
>>> chan = channels.StaticErrorRateChannel(code.ambient_space(), Integer(1))  # long time
>>> rv = chan.transmit(code.random_element())  # long time
>>> cw = dec.decode_to_code(rv)                # long time
>>> (cw - rv).hamming_weight() == Integer(1)            # long time
True
decode_to_message(received_vector, **kwargs)[source]

Return the message decoded from received_vector.

INPUT:

  • received_vector – a vector in the ambient space of the code

  • verbose – boolean; if True, verbose information on the decoding process is printed

EXAMPLES:

sage: F.<a> = GF(4)
sage: P.<x,y> = AffineSpace(F, 2)
sage: C = Curve(y^2 + y - x^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: p = C([0,0])
sage: Q, = p.places()
sage: D = [pl for pl in pls if pl != Q]
sage: G = 5*Q
sage: code = codes.EvaluationAGCode(D, G)  # long time
sage: dec = code.decoder('K', Q)           # long time
sage: enc = dec.connected_encoder()        # long time
sage: code = dec.code()                    # long time
sage: chan = channels.StaticErrorRateChannel(code.ambient_space(), 1)  # long time
sage: rv = chan.transmit(code.random_element())  # long time
sage: msg = dec.decode_to_message(rv)            # long time
sage: cw = enc.encode(msg)                       # long time
sage: (cw - rv).hamming_weight() == 1            # long time
True

>>> from sage.all import *
>>> F = GF(Integer(4), names=('a',)); (a,) = F._first_ngens(1)
>>> P = AffineSpace(F, Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> p = C([Integer(0),Integer(0)])
>>> Q, = p.places()
>>> D = [pl for pl in pls if pl != Q]
>>> G = Integer(5)*Q
>>> code = codes.EvaluationAGCode(D, G)  # long time
>>> dec = code.decoder('K', Q)           # long time
>>> enc = dec.connected_encoder()        # long time
>>> code = dec.code()                    # long time
>>> chan = channels.StaticErrorRateChannel(code.ambient_space(), Integer(1))  # long time
>>> rv = chan.transmit(code.random_element())  # long time
>>> msg = dec.decode_to_message(rv)            # long time
>>> cw = enc.encode(msg)                       # long time
>>> (cw - rv).hamming_weight() == Integer(1)            # long time
True
decoding_radius()[source]

Return the decoding radius of the decoder.

EXAMPLES:

sage: F.<a> = GF(4)
sage: P.<x,y> = AffineSpace(F, 2)
sage: C = Curve(y^2 + y - x^3)
sage: F = C.function_field()
sage: pls = F.places()
sage: p = C([0,0])
sage: Q, = p.places()
sage: D = [pl for pl in pls if pl != Q]
sage: G = 5*Q
sage: code = codes.EvaluationAGCode(D, G)  # long time
sage: dec = code.decoder('K', Q)           # long time
sage: dec.decoding_radius()                # long time
1

>>> from sage.all import *
>>> F = GF(Integer(4), names=('a',)); (a,) = F._first_ngens(1)
>>> P = AffineSpace(F, Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> C = Curve(y**Integer(2) + y - x**Integer(3))
>>> F = C.function_field()
>>> pls = F.places()
>>> p = C([Integer(0),Integer(0)])
>>> Q, = p.places()
>>> D = [pl for pl in pls if pl != Q]
>>> G = Integer(5)*Q
>>> code = codes.EvaluationAGCode(D, G)  # long time
>>> dec = code.decoder('K', Q)           # long time
>>> dec.decoding_radius()                # long time
1