Guruswami-Sudan decoder for (Generalized) Reed-Solomon codes

REFERENCES:

AUTHORS:

  • Johan S. R. Nielsen, original implementation (see [Nie] for details)
  • David Lucas, ported the original implementation in Sage
class sage.coding.guruswami_sudan.gs_decoder.GRSGuruswamiSudanDecoder(code, tau=None, parameters=None, interpolation_alg=None, root_finder=None)

Bases: sage.coding.decoder.Decoder

The Guruswami-Sudan list-decoding algorithm for decoding Generalized Reed-Solomon codes.

The Guruswami-Sudan algorithm is a polynomial time algorithm to decode beyond half the minimum distance of the code. It can decode up to the Johnson radius which is \(n - \sqrt(n(n-d))\), where \(n, d\) is the length, respectively minimum distance of the RS code. See [GS1999] for more details. It is a list-decoder meaning that it returns a list of all closest codewords or their corresponding message polynomials. Note that the output of the decode_to_code and decode_to_message methods are therefore lists.

The algorithm has two free parameters, the list size and the multiplicity, and these determine how many errors the method will correct: generally, higher decoding radius requires larger values of these parameters. To decode all the way to the Johnson radius, one generally needs values in the order of \(O(n^2)\), while decoding just one error less requires just \(O(n)\).

This class has static methods for computing choices of parameters given the decoding radius or vice versa.

The Guruswami-Sudan consists of two computationally intensive steps: Interpolation and Root finding, either of which can be completed in multiple ways. This implementation allows choosing the sub-algorithms among currently implemented possibilities, or supplying your own.

INPUT:

  • code – A code associated to this decoder.

  • tau – (default: None) an integer, the number of errors one wants the Guruswami-Sudan algorithm to correct.

  • parameters – (default: None) a pair of integers, where:
    • the first integer is the multiplicity parameter, and
    • the second integer is the list size parameter.
  • interpolation_alg – (default: None) the interpolation algorithm that will be used. The following possibilities are currently available:

    • "LinearAlgebra" – uses a linear system solver.
    • "LeeOSullivan" – uses Lee O’Sullivan method based on row reduction of a matrix
    • None – one of the above will be chosen based on the size of the code and the parameters.

    You can also supply your own function to perform the interpolation. See NOTE section for details on the signature of this function.

  • root_finder – (default: None) the rootfinding algorithm that will be used. The following possibilities are currently available:

    • "Alekhnovich" – uses Alekhnovich’s algorithm.
    • "RothRuckenstein" – uses Roth-Ruckenstein algorithm.
    • None – one of the above will be chosen based on the size of the code and the parameters.

    You can also supply your own function to perform the interpolation. See NOTE section for details on the signature of this function.

Note

One has to provide either tau or parameters. If neither are given, an exception will be raised.

If one provides a function as root_finder, its signature has to be: my_rootfinder(Q, maxd=default_value, precision=default_value). \(Q\) will be given as an element of \(F[x][y]\). The function must return the roots as a list of polynomials over a univariate polynomial ring. See roth_ruckenstein_root_finder() for an example.

If one provides a function as interpolation_alg, its signature has to be: my_inter(interpolation_points, tau, s_and_l, wy). See sage.coding.guruswami_sudan.interpolation.gs_interpolation_linalg() for an example.

EXAMPLES:

sage: C = codes.GeneralizedReedSolomonCode(GF(251).list()[:250], 70)
sage: D = codes.decoders.GRSGuruswamiSudanDecoder(C, tau = 97)
sage: D
Guruswami-Sudan decoder for [250, 70, 181] Reed-Solomon Code over GF(251) decoding 97 errors with parameters (1, 2)

One can specify multiplicity and list size instead of tau:

sage: D = codes.decoders.GRSGuruswamiSudanDecoder(C, parameters = (1,2))
sage: D
Guruswami-Sudan decoder for [250, 70, 181] Reed-Solomon Code over GF(251) decoding 97 errors with parameters (1, 2)

One can pass a method as root_finder (works also for interpolation_alg):

sage: from sage.coding.guruswami_sudan.gs_decoder import roth_ruckenstein_root_finder
sage: rf = roth_ruckenstein_root_finder
sage: D = codes.decoders.GRSGuruswamiSudanDecoder(C, parameters = (1,2), root_finder = rf)
sage: D
Guruswami-Sudan decoder for [250, 70, 181] Reed-Solomon Code over GF(251) decoding 97 errors with parameters (1, 2)

If one wants to use the native Sage algorithms for the root finding step, one can directly pass the string given in the Input block of this class. This works for interpolation_alg as well:

sage: D = codes.decoders.GRSGuruswamiSudanDecoder(C, parameters = (1,2), root_finder="RothRuckenstein")
sage: D
Guruswami-Sudan decoder for [250, 70, 181] Reed-Solomon Code over GF(251) decoding 97 errors with parameters (1, 2)

Actually, we can construct the decoder from C directly:

sage: D = C.decoder("GuruswamiSudan", tau = 97)
sage: D
Guruswami-Sudan decoder for [250, 70, 181] Reed-Solomon Code over GF(251) decoding 97 errors with parameters (1, 2)
decode_to_code(r)

Return the list of all codeword within radius self.decoding_radius() of the received word \(r\).

INPUT:

  • r – a received word, i.e. a vector in \(F^n\) where \(F\) and \(n\) are the base field respectively length of self.code().

EXAMPLES:

sage: C = codes.GeneralizedReedSolomonCode(GF(17).list()[:15], 6)
sage: D = codes.decoders.GRSGuruswamiSudanDecoder(C, tau=5)
sage: c = vector(GF(17), [3,13,12,0,0,7,5,1,8,11,1,9,4,12,14])
sage: c in C
True
sage: r = vector(GF(17), [3,13,12,0,0,7,5,1,8,11,15,12,14,7,10])
sage: r in C
False
sage: codewords = D.decode_to_code(r)
sage: len(codewords)
2
sage: c in codewords
True
decode_to_message(r)

Decodes r to the list of polynomials whose encoding by self.code() is within Hamming distance self.decoding_radius() of r.

INPUT:

  • r – a received word, i.e. a vector in \(F^n\) where \(F\) and \(n\) are the base field respectively length of self.code().

EXAMPLES:

sage: C = codes.GeneralizedReedSolomonCode(GF(17).list()[:15], 6)
sage: D = codes.decoders.GRSGuruswamiSudanDecoder(C, tau=5)
sage: F.<x> = GF(17)[]
sage: m = 13*x^4 + 7*x^3 + 10*x^2 + 14*x + 3
sage: c = D.connected_encoder().encode(m)
sage: r = vector(GF(17), [3,13,12,0,0,7,5,1,8,11,15,12,14,7,10])
sage: (c-r).hamming_weight()
5
sage: messages = D.decode_to_message(r)
sage: len(messages)
2
sage: m in messages
True
decoding_radius()

Returns the maximal number of errors that self is able to correct.

EXAMPLES:

sage: C = codes.GeneralizedReedSolomonCode(GF(251).list()[:250], 70)
sage: D = C.decoder("GuruswamiSudan", tau = 97)
sage: D.decoding_radius()
97

An example where tau is not one of the inputs to the constructor:

sage: C = codes.GeneralizedReedSolomonCode(GF(251).list()[:250], 70)
sage: D = C.decoder("GuruswamiSudan", parameters = (2,4))
sage: D.decoding_radius()
105
static gs_satisfactory(tau, s, l, C=None, n_k=None)

Returns whether input parameters satisfy the governing equation of Guruswami-Sudan.

See [Nie2013] page 49, definition 3.3 and proposition 3.4 for details.

INPUT:

  • tau – an integer, number of errors one expects Guruswami-Sudan algorithm to correct
  • s – an integer, multiplicity parameter of Guruswami-Sudan algorithm
  • l – an integer, list size parameter
  • C – (default: None) a GeneralizedReedSolomonCode
  • n_k – (default: None) a tuple of integers, respectively the length and the dimension of the GeneralizedReedSolomonCode

Note

One has to provide either C or (n, k). If none or both are given, an exception will be raised.

EXAMPLES:

sage: tau, s, l = 97, 1, 2
sage: n, k = 250, 70
sage: codes.decoders.GRSGuruswamiSudanDecoder.gs_satisfactory(tau, s, l, n_k = (n, k))
True

One can also pass a GRS code:

sage: C = codes.GeneralizedReedSolomonCode(GF(251).list()[:250], 70)
sage: codes.decoders.GRSGuruswamiSudanDecoder.gs_satisfactory(tau, s, l, C = C)
True

Another example where s and l does not satisfy the equation:

sage: tau, s, l = 118, 47, 80
sage: codes.decoders.GRSGuruswamiSudanDecoder.gs_satisfactory(tau, s, l, n_k = (n, k))
False

If one provides both C and n_k an exception is returned:

sage: tau, s, l = 97, 1, 2
sage: n, k = 250, 70
sage: C = codes.GeneralizedReedSolomonCode(GF(251).list()[:250], 70)
sage: codes.decoders.GRSGuruswamiSudanDecoder.gs_satisfactory(tau, s, l, C = C, n_k = (n, k))
Traceback (most recent call last):
...
ValueError: Please provide only the code or its length and dimension

Same if one provides none of these:

sage: codes.decoders.GRSGuruswamiSudanDecoder.gs_satisfactory(tau, s, l)
Traceback (most recent call last):
...
ValueError: Please provide either the code or its length and dimension
static guruswami_sudan_decoding_radius(C=None, n_k=None, l=None, s=None)

Returns the maximal decoding radius of the Guruswami-Sudan decoder and the parameter choices needed for this.

If s is set but l is not it will return the best decoding radius using this s alongside with the required l. Vice versa for l. If both are set, it returns the decoding radius given this parameter choice.

INPUT:

  • C – (default: None) a GeneralizedReedSolomonCode
  • n_k – (default: None) a pair of integers, respectively the length and the dimension of the GeneralizedReedSolomonCode
  • s – (default: None) an integer, the multiplicity parameter of Guruswami-Sudan algorithm
  • l – (default: None) an integer, the list size parameter

Note

One has to provide either C or n_k. If none or both are given, an exception will be raised.

OUTPUT:

  • (tau, (s, l)) – where
    • tau is the obtained decoding radius, and
    • s, ell are the multiplicity parameter, respectively list size parameter giving this radius.

EXAMPLES:

sage: n, k = 250, 70
sage: codes.decoders.GRSGuruswamiSudanDecoder.guruswami_sudan_decoding_radius(n_k = (n, k))
(118, (47, 89))

One parameter can be restricted at a time:

sage: n, k = 250, 70
sage: codes.decoders.GRSGuruswamiSudanDecoder.guruswami_sudan_decoding_radius(n_k = (n, k), s=3)
(109, (3, 5))
sage: codes.decoders.GRSGuruswamiSudanDecoder.guruswami_sudan_decoding_radius(n_k = (n, k), l=7)
(111, (4, 7))

The function can also just compute the decoding radius given the parameters:

sage: codes.decoders.GRSGuruswamiSudanDecoder.guruswami_sudan_decoding_radius(n_k = (n, k), s=2, l=6)
(92, (2, 6))
interpolation_algorithm()

Returns the interpolation algorithm that will be used.

Remember that its signature has to be: my_inter(interpolation_points, tau, s_and_l, wy). See sage.coding.guruswami_sudan.interpolation.gs_interpolation_linalg() for an example.

EXAMPLES:

sage: C = codes.GeneralizedReedSolomonCode(GF(251).list()[:250], 70)
sage: D = C.decoder("GuruswamiSudan", tau = 97)
sage: D.interpolation_algorithm()
<function gs_interpolation_lee_osullivan at 0x...>
list_size()

Returns the list size parameter of self.

EXAMPLES:

sage: C = codes.GeneralizedReedSolomonCode(GF(251).list()[:250], 70)
sage: D = C.decoder("GuruswamiSudan", tau = 97)
sage: D.list_size()
2
multiplicity()

Returns the multiplicity parameter of self.

EXAMPLES:

sage: C = codes.GeneralizedReedSolomonCode(GF(251).list()[:250], 70)
sage: D = C.decoder("GuruswamiSudan", tau = 97)
sage: D.multiplicity()
1
parameters()

Returns the multiplicity and list size parameters of self.

EXAMPLES:

sage: C = codes.GeneralizedReedSolomonCode(GF(251).list()[:250], 70)
sage: D = C.decoder("GuruswamiSudan", tau = 97)
sage: D.parameters()
(1, 2)
static parameters_given_tau(tau, C=None, n_k=None)

Returns the smallest possible multiplicity and list size given the given parameters of the code and decoding radius.

INPUT:

  • tau – an integer, number of errors one wants the Guruswami-Sudan algorithm to correct
  • C – (default: None) a GeneralizedReedSolomonCode
  • n_k – (default: None) a pair of integers, respectively the length and the dimension of the GeneralizedReedSolomonCode

OUTPUT:

  • (s, l) – a pair of integers, where:
    • s is the multiplicity parameter, and
    • l is the list size parameter.

Note

One should to provide either C or (n, k). If neither or both are given, an exception will be raised.

EXAMPLES:

sage: tau, n, k = 97, 250, 70
sage: codes.decoders.GRSGuruswamiSudanDecoder.parameters_given_tau(tau, n_k = (n, k))
(1, 2)

Another example with a bigger decoding radius:

sage: tau, n, k = 118, 250, 70
sage: codes.decoders.GRSGuruswamiSudanDecoder.parameters_given_tau(tau, n_k = (n, k))
(47, 89)

Choosing a decoding radius which is too large results in an errors:

sage: tau = 200
sage: codes.decoders.GRSGuruswamiSudanDecoder.parameters_given_tau(tau, n_k = (n, k))
Traceback (most recent call last):
...
ValueError: The decoding radius must be less than the Johnson radius (which is 118.66)
rootfinding_algorithm()

Returns the rootfinding algorithm that will be used.

Remember that its signature has to be: my_rootfinder(Q, maxd=default_value, precision=default_value). See roth_ruckenstein_root_finder() for an example.

EXAMPLES:

sage: C = codes.GeneralizedReedSolomonCode(GF(251).list()[:250], 70)
sage: D = C.decoder("GuruswamiSudan", tau = 97)
sage: D.rootfinding_algorithm()
<function alekhnovich_root_finder at 0x...>
sage.coding.guruswami_sudan.gs_decoder.alekhnovich_root_finder(p, maxd=None, precision=None)

Wrapper for Alekhnovich’s algorithm to compute the roots of a polynomial with coefficients in F[x].

sage.coding.guruswami_sudan.gs_decoder.n_k_params(C, n_k)

Internal helper function for the GRSGuruswamiSudanDecoder class for allowing to specify either a GRS code \(C\) or the length and dimensions \(n, k\) directly, in all the static functions.

If neither \(C\) or \(n,k\) were specified to those functions, an appropriate error should be raised. Otherwise, \(n, k\) of the code or the supplied tuple directly is returned.

INPUT:

  • C – A GRS code or \(None\)
  • n_k – A tuple \((n,k)\) being length and dimension of a GRS code, or \(None\).

OUTPUT:

  • n_k – A tuple \((n,k)\) being length and dimension of a GRS code.

EXAMPLES:

sage: from sage.coding.guruswami_sudan.gs_decoder import n_k_params
sage: n_k_params(None, (10, 5))
(10, 5)
sage: C = codes.GeneralizedReedSolomonCode(GF(11).list()[:10], 5)
sage: n_k_params(C,None)
(10, 5)
sage: n_k_params(None,None)
Traceback (most recent call last):
...
ValueError: Please provide either the code or its length and dimension
sage: n_k_params(C,(12, 2))
Traceback (most recent call last):
...
ValueError: Please provide only the code or its length and dimension
sage.coding.guruswami_sudan.gs_decoder.roth_ruckenstein_root_finder(p, maxd=None, precision=None)

Wrapper for Roth-Ruckenstein algorithm to compute the roots of a polynomial with coefficients in F[x].