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 seekQ
with(xi,yi)
being a root ofQ
with multiplicitys
.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 seekQ
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)
, wheren
is the number of pointsINPUT:
points
– a list of tuples(xi, yi)
such that we seekQ
with(xi,yi)
being a root ofQ
with multiplicitys
.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 seekQ
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 seekQ
with(xi,yi)
being a root ofQ
with multiplicitys
.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 seekQ
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]