# Reed-Muller code¶

Given integers $$m, r$$ and a finite field $$F$$, the corresponding Reed-Muller Code is the set:

$\{ (f(\alpha_i)\mid \alpha_i \in F^m) \mid f \in F[x_1,x_2,\ldots,x_m], \deg f \leq r \}$

This file contains the following elements:

class sage.coding.reed_muller_code.BinaryReedMullerCode(order, num_of_var)

Representation of a binary Reed-Muller code.

For details on the definition of Reed-Muller codes, refer to ReedMullerCode().

Note

It is better to use the aforementioned method rather than calling this class directly, as ReedMullerCode() creates either a binary or a q-ary Reed-Muller code according to the arguments it receives.

INPUT:

• order – The order of the Reed-Muller Code, i.e., the maximum degree of the polynomial to be used in the code.

• num_of_var – The number of variables used in the polynomial.

EXAMPLES:

A binary Reed-Muller code can be constructed by simply giving the order of the code and the number of variables:

sage: C = codes.BinaryReedMullerCode(2, 4)
sage: C
Binary Reed-Muller Code of order 2 and number of variables 4

minimum_distance()

Returns the minimum distance of self. The minimum distance of a binary Reed-Muller code of order $$d$$ and number of variables $$m$$ is $$q^{m-d}$$

EXAMPLES:

sage: C = codes.BinaryReedMullerCode(2, 4)
sage: C.minimum_distance()
4

number_of_variables()

Returns the number of variables of the polynomial ring used in self.

EXAMPLES:

sage: C = codes.BinaryReedMullerCode(2, 4)
sage: C.number_of_variables()
4

order()

Returns the order of self. Order is the maximum degree of the polynomial used in the Reed-Muller code.

EXAMPLES:

sage: C = codes.BinaryReedMullerCode(2, 4)
sage: C.order()
2

class sage.coding.reed_muller_code.QAryReedMullerCode(base_field, order, num_of_var)

Representation of a q-ary Reed-Muller code.

For details on the definition of Reed-Muller codes, refer to ReedMullerCode().

Note

It is better to use the aforementioned method rather than calling this class directly, as ReedMullerCode() creates either a binary or a q-ary Reed-Muller code according to the arguments it receives.

INPUT:

• base_field – A finite field, which is the base field of the code.

• order – The order of the Reed-Muller Code, i.e., the maximum degree of the polynomial to be used in the code.

• num_of_var – The number of variables used in polynomial.

Warning

For now, this implementation only supports Reed-Muller codes whose order is less than q.

EXAMPLES:

sage: from sage.coding.reed_muller_code import QAryReedMullerCode
sage: F = GF(3)
sage: C = QAryReedMullerCode(F, 2, 2)
sage: C
Reed-Muller Code of order 2 and 2 variables over Finite Field of size 3

minimum_distance()

Returns the minimum distance between two words in self.

The minimum distance of a q-ary Reed-Muller code with order $$d$$ and number of variables $$m$$ is $$(q-d)q^{m-1}$$

EXAMPLES:

sage: from sage.coding.reed_muller_code import QAryReedMullerCode
sage: F = GF(5)
sage: C = QAryReedMullerCode(F, 2, 4)
sage: C.minimum_distance()
375

number_of_variables()

Returns the number of variables of the polynomial ring used in self.

EXAMPLES:

sage: from sage.coding.reed_muller_code import QAryReedMullerCode
sage: F = GF(59)
sage: C = QAryReedMullerCode(F, 2, 4)
sage: C.number_of_variables()
4

order()

Returns the order of self.

Order is the maximum degree of the polynomial used in the Reed-Muller code.

EXAMPLES:

sage: from sage.coding.reed_muller_code import QAryReedMullerCode
sage: F = GF(59)
sage: C = QAryReedMullerCode(F, 2, 4)
sage: C.order()
2

sage.coding.reed_muller_code.ReedMullerCode(base_field, order, num_of_var)

Returns a Reed-Muller code.

A Reed-Muller Code of order $$r$$ and number of variables $$m$$ over a finite field $$F$$ is the set:

$\{ (f(\alpha_i)\mid \alpha_i \in F^m) \mid f \in F[x_1,x_2,\ldots,x_m], \deg f \leq r \}$

INPUT:

• base_field – The finite field $$F$$ over which the code is built.

• order – The order of the Reed-Muller Code, which is the maximum

degree of the polynomial to be used in the code.

• num_of_var – The number of variables used in polynomial.

Warning

For now, this implementation only supports Reed-Muller codes whose order is less than q. Binary Reed-Muller codes must have their order less than or equal to their number of variables.

EXAMPLES:

We build a Reed-Muller code:

sage: F = GF(3)
sage: C = codes.ReedMullerCode(F, 2, 2)
sage: C
Reed-Muller Code of order 2 and 2 variables over Finite Field of size 3


sage: C.length()
9
sage: C.dimension()
6
sage: C.minimum_distance()
3


If one provides a finite field of size 2, a Binary Reed-Muller code is built:

sage: F = GF(2)
sage: C = codes.ReedMullerCode(F, 2, 2)
sage: C
Binary Reed-Muller Code of order 2 and number of variables 2

class sage.coding.reed_muller_code.ReedMullerPolynomialEncoder(code, polynomial_ring=None)

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

encode(p)

Transforms the polynomial p into a codeword of 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

message_space()

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

points()

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)]

polynomial_ring()

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

unencode_nocheck(c)

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 unencode().

INPUT:

• c – A codeword of 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

class sage.coding.reed_muller_code.ReedMullerVectorEncoder(code)

Encoder for Reed-Muller codes which encodes vectors 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 $$(v_1,v_2,\ldots,v_k)$$ be a vector of $$F$$, which corresponds to the polynomial $$f = \Sigma^{k}_{i=1} v_i \times x_i$$.

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.

EXAMPLES:

sage: C1=codes.ReedMullerCode(GF(2), 2, 4)
sage: E1=codes.encoders.ReedMullerVectorEncoder(C1)
sage: E1
Evaluation vector-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.ReedMullerVectorEncoder(C2)
sage: E2
Evaluation vector-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: C=codes.ReedMullerCode(GF(2), 2, 4)
sage: E = C.encoder("EvaluationVector")
sage: E
Evaluation vector-style encoder for Binary Reed-Muller Code of order 2 and number of variables 4

generator_matrix()

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]

points()

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)]