Coverage for local/lib/python2.7/site-packages/sage/coding/reed_muller

\textnormal{Evaluation vector-style encoder for }\textnormal{Reed-Muller Code of order} 2 \textnormal{and }4 \textnormal{variables over} \Bold{F}_{11}

"""

return "\\textnormal{Evaluation vector-style encoder for }%s" % self.code()._latex_()

def __eq__(self, other):

r"""

Tests equality between ReedMullerVectorEncoder objects.

EXAMPLES::

sage: F = GF(11)

sage: C = codes.ReedMullerCode(F, 2, 4)

sage: D1 = codes.encoders.ReedMullerVectorEncoder(C)

sage: D2 = codes.encoders.ReedMullerVectorEncoder(C)

sage: D1.__eq__(D2)

True

sage: D1 is D2

False

"""

return (isinstance(other, ReedMullerVectorEncoder)

) and self.code() == other.code()

@cached_method

def generator_matrix(self):

r"""

Returns a generator matrix of ``self``

EXAMPLES::

sage: F = GF(3)

sage: C = codes.ReedMullerCode(F, 2, 2)

sage: E = codes.encoders.ReedMullerVectorEncoder(C)

sage: E.generator_matrix()

[1 1 1 1 1 1 1 1 1]

[0 1 2 0 1 2 0 1 2]

[0 0 0 1 1 1 2 2 2]

[0 1 1 0 1 1 0 1 1]

[0 0 0 0 1 2 0 2 1]

[0 0 0 1 1 1 1 1 1]

"""

C = self.code()

base_field = C.base_field()

order = C.order()

num_of_var = C.number_of_variables()

q = base_field.cardinality()

dimension = C.dimension()

points = base_field**num_of_var

matrix_list = []

max_individual_degree = min(order, (q - 1))

for degree in range(order + 1):

exponents = Subsets(list(range(num_of_var)) * max_individual_degree,

degree, submultiset=True)

matrix_list += [[reduce(mul, [x[i] for i in exponent], 1)

for x in points] for exponent in exponents]

M = matrix(base_field, matrix_list)

M.set_immutable()

return M

def points(self):

r"""

Returns the points of $F^m$, where $F$ is base field and $m$ is the number of variables, in order of which polynomials are evaluated on.

EXAMPLES::

sage: F = GF(3)

sage: Fx.<x0,x1> = F[]

sage: C = codes.ReedMullerCode(F, 2, 2)

sage: E = C.encoder("EvaluationVector")

sage: E.points()

[(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)]

"""

code = self.code()

return ((code.base_field())**code.number_of_variables()).list()

class ReedMullerPolynomialEncoder(Encoder):

r"""

Encoder for Reed-Muller codes which encodes appropriate multivariate polynomials into codewords.

Consider a Reed-Muller code of order `r`, number of variables `m`, length `n`,

dimension `k` over some finite field `F`.

Let those variables be `(x_1, x_2, \dots, x_m)`.

We order the monomials by lowest power on lowest index variables. If we have three monomials

`x_1 \times x_2`, `x_1 \times x_2^2` and `x_1^2 \times x_2`, the ordering is:

`x_1 \times x_2 < x_1 \times x_2^2 < x_1^2 \times x_2`

Let now `f` be a polynomial of the multivariate polynomial ring `F[x_1, \dots, x_m]`.

Let `(\beta_1, \beta_2, \ldots, \beta_q)` be the elements of `F` ordered as they are

returned by Sage when calling ``F.list()``.

The aforementioned polynomial `f` is encoded as:

`(f(\alpha_{11},\alpha_{12},\ldots,\alpha_{1m}),f(\alpha_{21},\alpha_{22},\ldots,

\alpha_{2m}),\ldots,f(\alpha_{q^m1},\alpha_{q^m2},\ldots,\alpha_{q^mm}`, with

`\alpha_{ij}=\beta_{i \ mod \ q^j} \forall (i,j)`

INPUT:

- ``code`` -- The associated code of this encoder.

-``polynomial_ring`` -- (default:``None``) The polynomial ring from which the message is chosen.

If this is set to ``None``, a polynomial ring in `x` will be built

from the code parameters.

EXAMPLES::

sage: C1=codes.ReedMullerCode(GF(2), 2, 4)

sage: E1=codes.encoders.ReedMullerPolynomialEncoder(C1)

sage: E1

Evaluation polynomial-style encoder for Binary Reed-Muller Code of order 2 and number of variables 4

sage: C2=codes.ReedMullerCode(GF(3), 2, 2)

sage: E2=codes.encoders.ReedMullerPolynomialEncoder(C2)

sage: E2

Evaluation polynomial-style encoder for Reed-Muller Code of order 2 and 2 variables over Finite Field of size 3

We can also pass a predefined polynomial ring::

sage: R=PolynomialRing(GF(3), 2, 'y')

sage: C=codes.ReedMullerCode(GF(3), 2, 2)

sage: E=codes.encoders.ReedMullerPolynomialEncoder(C, R)

sage: E

Evaluation polynomial-style encoder for Reed-Muller Code of order 2 and 2 variables over Finite Field of size 3

Actually, we can construct the encoder from ``C`` directly::

sage: E = C1.encoder("EvaluationPolynomial")

sage: E

Evaluation polynomial-style encoder for Binary Reed-Muller Code of order 2 and number of variables 4

"""

def __init__(self, code, polynomial_ring=None):

r"""

TESTS:

If ``code`` is not a Reed-Muller code, an error is raised::

sage: C = codes.random_linear_code(GF(11), 10, 4)

sage: codes.encoders.ReedMullerPolynomialEncoder(C)

Traceback (most recent call last):

...

ValueError: the code has to be a Reed-Muller code

If the polynomial ring passed is not according to the requirement (over a different field or different number of variables) then an error is raised::

sage: F=GF(59)

sage: R.<x,y,z,w>=F[]

sage: C=codes.ReedMullerCode(F, 2, 3)

sage: E=codes.encoders.ReedMullerPolynomialEncoder(C, R)

Traceback (most recent call last):

...

ValueError: The Polynomial ring should be on Finite Field of size 59 and should have 3 variables

"""

if not (

isinstance(code, QAryReedMullerCode)

or isinstance(code, BinaryReedMullerCode)):

raise ValueError("the code has to be a Reed-Muller code")

super(ReedMullerPolynomialEncoder, self).__init__(code)

if polynomial_ring is None:

self._polynomial_ring = PolynomialRing(code.base_field(),

code.number_of_variables(), 'x')

else:

if (polynomial_ring.base_ring() == code.base_field()) and (

len(polynomial_ring.variable_names()) == code.number_of_variables()):

self._polynomial_ring = polynomial_ring

else:

raise ValueError(

"The Polynomial ring should be on %s and should have %s variables" %

(code.base_field(), code.number_of_variables()))

def _repr_(self):

r"""

Returns a string representation of ``self``.

EXAMPLES::

sage: F = GF(59)

sage: C = codes.ReedMullerCode(F, 2, 4)

sage: E=codes.encoders.ReedMullerPolynomialEncoder(C)

sage: E

Evaluation polynomial-style encoder for Reed-Muller Code of order 2 and 4 variables over Finite Field of size 59

"""

return "Evaluation polynomial-style encoder for %s" % self.code()

def _latex_(self):

r"""

Returns a string representation of ``self``.

EXAMPLES::

sage: F = GF(59)

sage: C = codes.ReedMullerCode(F, 2, 4)

sage: E=codes.encoders.ReedMullerPolynomialEncoder(C)

sage: latex(E)

\textnormal{Evaluation polynomial-style encoder for }\textnormal{Reed-Muller Code of order} 2 \textnormal{and }4 \textnormal{variables over} \Bold{F}_{59}

"""

return "\\textnormal{Evaluation polynomial-style encoder for }%s" % self.code()._latex_()

def __eq__(self, other):

r"""

Tests equality between ReedMullerVectorEncoder objects.

EXAMPLES::

sage: F = GF(11)

sage: C = codes.ReedMullerCode(F, 2, 4)

sage: D1 = codes.encoders.ReedMullerPolynomialEncoder(C)

sage: D2 = codes.encoders.ReedMullerPolynomialEncoder(C)

sage: D1.__eq__(D2)

True

sage: D1 is D2

False

"""

return isinstance(other, ReedMullerPolynomialEncoder) \

and self.code() == other.code()

def encode(self, p):

r"""

Transforms the polynomial ``p`` into a codeword of :meth:`code`.

INPUT:

- ``p`` -- A polynomial from the message space of ``self`` of degree

less than ``self.code().order()``.

OUTPUT:

- A codeword in associated code of ``self``

EXAMPLES::

sage: F = GF(3)

sage: Fx.<x0,x1> = F[]

sage: C = codes.ReedMullerCode(F, 2, 2)

sage: E = C.encoder("EvaluationPolynomial")

sage: p = x0*x1 + x1^2 + x0 + x1 + 1

sage: c = E.encode(p); c

(1, 2, 0, 0, 2, 1, 1, 1, 1)

sage: c in C

True

If a polynomial with good monomial degree but wrong monomial

degree is given,an error is raised::

sage: p = x0^2*x1

sage: E.encode(p)

Traceback (most recent call last):

...

ValueError: The polynomial to encode must have degree at most 2

If ``p`` is not an element of the proper polynomial ring, an error is raised::

sage: Qy.<y1,y2> = QQ[]

sage: p = y1^2 + 1

sage: E.encode(p)

Traceback (most recent call last):

...

ValueError: The value to encode must be in Multivariate Polynomial Ring in x0, x1 over Finite Field of size 3

"""

M = self.message_space()

if p not in M:

raise ValueError("The value to encode must be in %s" % M)

C = self.code()

if p.degree() > C.order():

raise ValueError("The polynomial to encode must have degree at most %s"

% C.order())

base_fieldTuple = Tuples(C.base_field().list(), C.number_of_variables())

return vector(C.base_ring(), [p(x) for x in base_fieldTuple])

def unencode_nocheck(self, c):

r"""

Returns the message corresponding to the codeword ``c``.

Use this method with caution: it does not check if ``c``

belongs to the code, and if this is not the case, the output is

unspecified. Instead, use :meth:`unencode`.

INPUT:

- ``c`` -- A codeword of :meth:`code`.

OUTPUT:

- An polynomial of degree less than ``self.code().order()``.

EXAMPLES::

sage: F = GF(3)

sage: C = codes.ReedMullerCode(F, 2, 2)

sage: E = C.encoder("EvaluationPolynomial")

sage: c = vector(F, (1, 2, 0, 0, 2, 1, 1, 1, 1))

sage: c in C

True

sage: p = E.unencode_nocheck(c); p

x0*x1 + x1^2 + x0 + x1 + 1

sage: E.encode(p) == c

True

Note that no error is thrown if ``c`` is not a codeword, and that the

result is undefined::

sage: c = vector(F, (1, 2, 0, 0, 2, 1, 0, 1, 1))

sage: c in C

False

sage: p = E.unencode_nocheck(c); p

-x0*x1 - x1^2 + x0 + 1

sage: E.encode(p) == c

False

"""

return _multivariate_polynomial_interpolation(

self.code().order(),

self.polynomial_ring())

def message_space(self):

r"""

Returns the message space of ``self``

EXAMPLES::

sage: F = GF(11)

sage: C = codes.ReedMullerCode(F, 2, 4)

sage: E = C.encoder("EvaluationPolynomial")

sage: E.message_space()

Multivariate Polynomial Ring in x0, x1, x2, x3 over Finite Field of size 11

"""

return self._polynomial_ring

def polynomial_ring(self):

r"""

Returns the polynomial ring associated with ``self``

EXAMPLES::

sage: F = GF(11)

sage: C = codes.ReedMullerCode(F, 2, 4)

sage: E = C.encoder("EvaluationPolynomial")

sage: E.polynomial_ring()

Multivariate Polynomial Ring in x0, x1, x2, x3 over Finite Field of size 11

"""

return self._polynomial_ring

def points(self):

r"""

Returns the evaluation points in the appropriate order as used by ``self`` when

encoding a message.

EXAMPLES::

sage: F = GF(3)

sage: Fx.<x0,x1> = F[]

sage: C = codes.ReedMullerCode(F, 2, 2)

sage: E = C.encoder("EvaluationPolynomial")

sage: E.points()

[(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)]

"""

code = self.code()

return ((code.base_field())**code.number_of_variables()).list()

####################### registration ###############################

QAryReedMullerCode._registered_encoders["EvaluationVector"] = ReedMullerVectorEncoder

QAryReedMullerCode._registered_encoders["EvaluationPolynomial"] = ReedMullerPolynomialEncoder

QAryReedMullerCode._registered_decoders["Syndrome"] = LinearCodeSyndromeDecoder

BinaryReedMullerCode._registered_encoders["EvaluationVector"] = ReedMullerVectorEncoder

BinaryReedMullerCode._registered_encoders["EvaluationPolynomial"] = ReedMullerPolynomialEncoder

BinaryReedMullerCode._registered_decoders["Syndrome"] = LinearCodeSyndromeDecoder

Coverage for local/lib/python2.7/site-packages/sage/coding/reed_muller_code.py : 98%

190 statements 187 run 3 missing 0 excluded