Guruswami-Sudan utility methods¶
AUTHORS:
- Johan S. R. Nielsen, original implementation (see [Nielsen] for details)
- David Lucas, ported the original implementation in Sage
-
sage.coding.guruswami_sudan.utils.
apply_shifts
(M, shifts)¶ Applies column shifts inplace to the polynomial matrix \(M\).
This is equivalent to multiplying the \(n`th column of `M\) with \(x^{shifts[n]}\).
INPUT:
M
– a polynomial matrixshifts
– a list of non-negative integer shifts
EXAMPLES:
sage: from sage.coding.guruswami_sudan.utils import apply_shifts sage: F.<x> = GF(7)[] sage: M = matrix(F, [[2*x^2 + x, 5*x^2 + 2*x + 1, 4*x^2 + x],\ [x^2 + 3*x + 3, 5*x^2 + 5*x + 1, 6*x^2 + 5*x + 4],\ [5*x^2 + 2*x + 4, 4*x^2 + 2*x, 5*x^2 + x + 2]]) sage: shifts = [1, 2, 3] sage: apply_shifts(M, shifts) sage: M [ 2*x^3 + x^2 5*x^4 + 2*x^3 + x^2 4*x^5 + x^4] [ x^3 + 3*x^2 + 3*x 5*x^4 + 5*x^3 + x^2 6*x^5 + 5*x^4 + 4*x^3] [ 5*x^3 + 2*x^2 + 4*x 4*x^4 + 2*x^3 5*x^5 + x^4 + 2*x^3]
-
sage.coding.guruswami_sudan.utils.
gilt
(x)¶ Returns the greatest integer smaller than
x
.EXAMPLES:
sage: from sage.coding.guruswami_sudan.utils import gilt sage: gilt(43) 42
It works with any type of numbers (not only integers):
sage: gilt(43.041) 43
-
sage.coding.guruswami_sudan.utils.
johnson_radius
(n, d)¶ Returns the Johnson-radius for the code length \(n\) and the minimum distance \(d\).
The Johnson radius is defined as \(n - \sqrt(n(n-d))\).
INPUT:
n
– an integer, the length of the coded
– an integer, the minimum distance of the code
EXAMPLES:
sage: sage.coding.guruswami_sudan.utils.johnson_radius(250, 181) -5*sqrt(690) + 250
-
sage.coding.guruswami_sudan.utils.
leading_term
(v, shifts=None)¶ Returns the term of
v
with the highest degree.This methods can manage shifted degree, by providing
shift
to it.In case of several positions having the same, highest degree, the term with the right-most position is returned.
INPUT:
v
– a vector of polynomialsshifts
– (default:None
) a list of integer shifts to considerv
under. IfNone
, all shifts are considered as0
.
EXAMPLES:
sage: from sage.coding.guruswami_sudan.utils import leading_term sage: F.<x> = GF(7)[] sage: v = vector(F, [3*x^2 + 3*x + 4, 4*x + 3, 4*x^2 + 4*x + 5, x^2 + 2*x + 5, 3*x^2 + 5*x]) sage: leading_term(v) 3*x^2 + 5*x
-
sage.coding.guruswami_sudan.utils.
ligt
(x)¶ Returns the least integer greater than
x
.EXAMPLES:
sage: from sage.coding.guruswami_sudan.utils import ligt sage: ligt(41) 42
It works with any type of numbers (not only integers):
sage: ligt(41.041) 42
-
sage.coding.guruswami_sudan.utils.
polynomial_to_list
(p, len)¶ Returns
p
as a list of its coefficients of lengthlen
.INPUT:
p
– a polynomiallen
– an integer. Iflen
is smaller than the degree ofp
, the returned list will be of size degree ofp
, else it will be of sizelen
.
EXAMPLES:
sage: from sage.coding.guruswami_sudan.utils import polynomial_to_list sage: F.<x> = GF(41)[] sage: p = 9*x^2 + 8*x + 37 sage: polynomial_to_list(p, 4) [37, 8, 9, 0]
-
sage.coding.guruswami_sudan.utils.
remove_shifts
(M, shifts)¶ Removes the shifts inplace to the matrix \(M\) as they were introduced by
apply_shifts()
.If \(M\) was not earlier called with
apply_shifts()
using the same shifts, then the least significant coefficients of the entries of \(M\), corresponding to how much we are shifting down, will be lost.INPUT:
M
– a polynomial matrixshifts
– a list of non-negative integer shifts
EXAMPLES:
sage: from sage.coding.guruswami_sudan.utils import remove_shifts sage: F.<x> = GF(7)[] sage: M = matrix(F, [[2*x^3 + x^2, 5*x^4 + 2*x^3 + x^2, 4*x^5 + x^4],\ [x^3 + 3*x^2 + 3*x, 5*x^4 + 5*x^3 + x^2, 6*x^5 + 5*x^4 + 4*x^3],\ [5*x^3 + 2*x^2 + 4*x, 4*x^4 + 2*x^3, 5*x^5 + x^4 + 2*x^3]]) sage: shifts = [1, 2, 3] sage: remove_shifts(M, shifts) sage: M [ 2*x^2 + x 5*x^2 + 2*x + 1 4*x^2 + x] [ x^2 + 3*x + 3 5*x^2 + 5*x + 1 6*x^2 + 5*x + 4] [5*x^2 + 2*x + 4 4*x^2 + 2*x 5*x^2 + x + 2]
-
sage.coding.guruswami_sudan.utils.
solve_degree2_to_integer_range
(a, b, c)¶ Returns the greatest integer range \([i_1, i_2]\) such that \(i_1 > x_1\) and \(i_2 < x_2\) where \(x_1, x_2\) are the two zeroes of the equation in \(x\): \(ax^2+bx+c=0\).
If there is no real solution to the equation, it returns an empty range with negative coefficients.
INPUT:
a
,b
andc
– coefficients of a second degree equation,a
being the coefficient of the higher degree term.
EXAMPLES:
sage: from sage.coding.guruswami_sudan.utils import solve_degree2_to_integer_range sage: solve_degree2_to_integer_range(1, -5, 1) (1, 4)
If there is no real solution:
sage: solve_degree2_to_integer_range(50, 5, 42) (-2, -1)