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

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

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

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

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)

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

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

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

encode(message)

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

unencode_nocheck(codeword)

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

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

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

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

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

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

decoding_radius()

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

class sage.coding.ag_code_decoders.EvaluationAGCodeDecoder_K

Bases: Decoder_K

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

INPUT:

• pls – a 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

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

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

encode(message)

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

unencode_nocheck(codeword)

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

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

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

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

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

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

decoding_radius()

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