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:

• QAryReedMullerCode, the class for Reed-Muller codes over non-binary field of size q and \(r<q\)

• BinaryReedMullerCode, the class for Reed-Muller codes over binary field and \(r<=m\)

• ReedMullerVectorEncoder, an encoder with a vectorial message space (for both the two code classes)

• ReedMullerPolynomialEncoder, an encoder with a polynomial message space (for both the code classes)

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

Bases: AbstractLinearCode

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

Return 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()

Return 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()

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

Bases: AbstractLinearCode

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

Return 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()

Return 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()

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

Return 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

We ask for its parameters:

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)

Bases: Encoder

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 x_2\), \(x_1 x_2^2\) and \(x_1^2 x_2\), the ordering is: \(x_1 x_2 < x_1 x_2^2 < x_1^2 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 \bmod{q^j}}\) for all \(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()

Return 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()

Return 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()

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

Return 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:

• A 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)

Bases: Encoder

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 x_2\), \(x_1 x_2^2\) and \(x_1^2 x_2\), the ordering is: \(x_1 x_2 < x_1 x_2^2 < x_1^2 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 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 \bmod{q^j}}\) for all \(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()

Return 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()

Return the points of \(F^m\), where \(F\) is the 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)]