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

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

Python

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

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

Python

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

Bases: object

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

EXAMPLES:

Sage

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)

Python

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

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)

Encode message to a codeword.

info

class sage.coding.ag_code_decoders.Decoder_K_extension

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

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)

Python

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

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)

Python

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

Decode the received vector to a message.

INPUT:

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

encode(message, **kwargs)

Encode message to a codeword.

info

class sage.coding.ag_code_decoders.DifferentialAGCodeDecoder_K

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

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

Python

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

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

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

Python

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

Bases: Encoder

Encoder of a differential AG code.

INPUT:

• code – a differential AG code

• decoder – a decoder of the code

EXAMPLES:

Sage

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)

Python

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

Return the codeword encoded from the message.

INPUT:

• message – a vector in the message space

EXAMPLES:

Sage

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

Python

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

Return the message unencoded from codeword.

INPUT:

• codeword – a vector in the code

EXAMPLES:

Sage

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

Python

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

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

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

Python

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

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

Python

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

Return the connected encoder for this decoder.

INPUT:

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

EXAMPLES:

Sage

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)

Python

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

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

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

Python

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

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

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

Python

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

Return the decoding radius of the decoder.

EXAMPLES:

Sage

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

Python

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

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

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

Python

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

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

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

Python

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

Bases: Encoder

Encoder of an evaluation AG code.

INPUT:

• code – an evaluation AG code

• decoder – a decoder of the code

EXAMPLES:

Sage

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)

Python

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

Return the codeword encoded from the message.

INPUT:

• message – a vector in the message space

EXAMPLES:

Sage

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

Python

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

Return the message unencoded from codeword.

INPUT:

• codeword – a vector in the code

EXAMPLES:

Sage

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

Python

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

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

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

Python

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

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

Python

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

Return the connected encoder for this decoder.

INPUT:

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

EXAMPLES:

Sage

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)

Python

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

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

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

Python

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

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

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

Python

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

Return the decoding radius of the decoder.

EXAMPLES:

Sage

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

Python

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