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 codeverbose
– boolean; ifTrue
, verbose information is printeddetect_decoding_failure
– boolean; ifTrue
, early failure detection is activateddetect_Q_polynomial
– boolean; ifTrue
, 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 fieldG
– a divisor of the function fieldQ
– a non-rational placeverbose
– ifTrue
, 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 fieldG
– a divisor of the function fieldQ
– a rational place not inpls
verbose
– ifTrue
, 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 fieldG
– a divisor of the function fieldQ
– a non-rational placeverbose
– ifTrue
, 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 codedecoder
– 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 codeQ
– (optional) a place, not one of the places supporting the codebasis
– (optional) a basis of the space of differentials to take residuesverbose
– ifTrue
, 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 bycode.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 codeverbose
– boolean; ifTrue
, 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 codeverbose
– boolean; ifTrue
, 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 fieldG
– a divisor of the function fieldQ
– a rational place not inpls
verbose
– ifTrue
, 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 fieldG
– a divisor of the function fieldQ
– a non-rational placeverbose
– ifTrue
, 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 codedecoder
– 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 codeQ
– (optional) a place, not one of the places supporting the codebasis
– (optional) a basis of the space of functions to evaluateverbose
– ifTrue
, 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 bycode.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 codeverbose
– boolean; ifTrue
, 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 codeverbose
– boolean; ifTrue
, 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