Interpolation algorithms for the Guruswami-Sudan decoder¶

AUTHORS:

• Johan S. R. Nielsen, original implementation (see [Nie] for details)

• David Lucas, ported the original implementation in Sage

sage.coding.guruswami_sudan.interpolation.gs_interpolation_lee_osullivan(points, tau, parameters, wy)

Returns an interpolation polynomial Q(x,y) for the given input using the module-based algorithm of Lee and O’Sullivan.

This algorithm constructs an explicit $$(\ell+1) \times (\ell+1)$$ polynomial matrix whose rows span the $$\GF q[x]$$ module of all interpolation polynomials. It then runs a row reduction algorithm to find a low-shifted degree vector in this row space, corresponding to a low weighted-degree interpolation polynomial.

INPUT:

• points – a list of tuples (xi, yi) such that we seek Q with (xi,yi) being a root of Q with multiplicity s.

• tau – an integer, the number of errors one wants to decode.

• parameters – (default: None) a pair of integers, where:
• the first integer is the multiplicity parameter of Guruswami-Sudan algorithm and

• the second integer is the list size parameter.

• wy – an integer, the $$y$$-weight, where we seek Q of low (1,wy) weighted degree.

EXAMPLES:

sage: from sage.coding.guruswami_sudan.interpolation import gs_interpolation_lee_osullivan
sage: F = GF(11)
sage: points = [(F(0), F(2)), (F(1), F(5)), (F(2), F(0)), (F(3), F(4)), (F(4), F(9))\
, (F(5), F(1)), (F(6), F(9)), (F(7), F(10))]
sage: tau = 1
sage: params = (1, 1)
sage: wy = 1
sage: Q = gs_interpolation_lee_osullivan(points, tau, params, wy)
sage: Q / Q.lc() # make monic
x^3*y + 2*x^3 - x^2*y + 5*x^2 + 5*x*y - 5*x + 2*y - 4
sage.coding.guruswami_sudan.interpolation.gs_interpolation_linalg(points, tau, parameters, wy)

Compute an interpolation polynomial Q(x,y) for the Guruswami-Sudan algorithm by solving a linear system of equations.

Q is a bivariate polynomial over the field of the points, such that the polynomial has a zero of multiplicity at least $$s$$ at each of the points, where $$s$$ is the multiplicity parameter. Furthermore, its (1, wy)-weighted degree should be less than _interpolation_max_weighted_deg(n, tau, wy), where n is the number of points

INPUT:

• points – a list of tuples (xi, yi) such that we seek Q with (xi,yi) being a root of Q with multiplicity s.

• tau – an integer, the number of errors one wants to decode.

• parameters – (default: None) a pair of integers, where:
• the first integer is the multiplicity parameter of Guruswami-Sudan algorithm and

• the second integer is the list size parameter.

• wy – an integer, the $$y$$-weight, where we seek Q of low (1,wy) weighted degree.

EXAMPLES:

The following parameters arise from Guruswami-Sudan decoding of an [6,2,5] GRS code over F(11) with multiplicity 2 and list size 4:

sage: from sage.coding.guruswami_sudan.interpolation import gs_interpolation_linalg
sage: F = GF(11)
sage: points = [(F(x),F(y)) for (x,y) in [(0, 5), (1, 1), (2, 4), (3, 6), (4, 3), (5, 3)]]
sage: tau = 3
sage: params = (2, 4)
sage: wy = 1
sage: Q = gs_interpolation_linalg(points, tau, params, wy); Q
4*x^5 - 4*x^4*y - 2*x^2*y^3 - x*y^4 + 3*x^4 - 4*x^2*y^2 + 5*y^4 - x^3 + x^2*y + 5*x*y^2 - 5*y^3 + 3*x*y - 2*y^2 + x - 4*y + 1

We verify that the interpolation polynomial has a zero of multiplicity at least 2 in each point:

sage: all( Q(x=a, y=b).is_zero() for (a,b) in points )
True
sage: x,y = Q.parent().gens()
sage: dQdx = Q.derivative(x)
sage: all( dQdx(x=a, y=b).is_zero() for (a,b) in points )
True
sage: dQdy = Q.derivative(y)
sage: all( dQdy(x=a, y=b).is_zero() for (a,b) in points )
True
sage.coding.guruswami_sudan.interpolation.lee_osullivan_module(points, parameters, wy)

Returns the analytically straight-forward basis for the $$\GF q[x]$$ module containing all interpolation polynomials, as according to Lee and O’Sullivan.

The module is constructed in the following way: Let $$R(x)$$ be the Lagrange interpolation polynomial through the sought interpolation points $$(x_i, y_i)$$, i.e. $$R(x_i) = y_i$$. Let $$G(x) = \prod_{i=1}^n (x-x_i)$$. Then the $$i$$’th row of the basis matrix of the module is the coefficient-vector of the following polynomial in $$\GF q[x][y]$$:

$$P_i(x,y) = G(x)^{[i-s]} (y - R(x))^{i - [i-s]} y^{[i-s]}$$ ,

where $$[a]$$ for real $$a$$ is $$a$$ when $$a > 0$$ and 0 otherwise. It is easily seen that $$P_i(x,y)$$ is an interpolation polynomial, i.e. it is zero with multiplicity at least $$s$$ on each of the points $$(x_i, y_i)$$.

INPUT:

• points – a list of tuples (xi, yi) such that we seek Q with (xi,yi) being a root of Q with multiplicity s.

• parameters – (default: None) a pair of integers, where:
• the first integer is the multiplicity parameter $$s$$ of Guruswami-Sudan algorithm and

• the second integer is the list size parameter.

• wy – an integer, the $$y$$-weight, where we seek Q of low (1,wy) weighted degree.

EXAMPLES:

sage: from sage.coding.guruswami_sudan.interpolation import lee_osullivan_module
sage: F = GF(11)
sage: points = [(F(0), F(2)), (F(1), F(5)), (F(2), F(0)), (F(3), F(4)), (F(4), F(9))\
, (F(5), F(1)), (F(6), F(9)), (F(7), F(10))]
sage: params = (1, 1)
sage: wy = 1
sage: lee_osullivan_module(points, params, wy)
[x^8 + 5*x^7 + 3*x^6 + 9*x^5 + 4*x^4 + 2*x^3 + 9*x   0]
[ 10*x^7 + 4*x^6 + 9*x^4 + 7*x^3 + 2*x^2 + 9*x + 9   1]