Cyclic code#

Let \(F\) be a field. A \([n, k]\) code \(C\) over \(F\) is called cyclic if every cyclic shift of a codeword is also a codeword [Rot2006]:

\[\forall c \in C, c = (c_{0}, c_{1}, \dots , c_{n-1}) \in C \Rightarrow (c_{n-1}, c_{0}, \dots , c_{n-2}) \in C\]

Let \(c = (c_0, c_1, \dots, c_{n-1})\) be a codeword of \(C\). This codeword can be seen as a polynomial over \(F_q[x]\) as follows: \(\Sigma_{i=0}^{n-1} c_i x^i\). There is a unique monic polynomial \(g(x)\) such that for every \(c(x) \in F_q[x]\) of degree less than \(n-1\), we have \(c(x) \in C \Leftrightarrow g(x) | c(x)\). This polynomial is called the generator polynomial of \(C\).

For now, only single-root cyclic codes (i.e. whose length \(n\) and field order \(q\) are coprimes) are implemented.

class sage.coding.cyclic_code.CyclicCode(generator_pol=None, length=None, code=None, check=True, D=None, field=None, primitive_root=None)[source]#

Bases: AbstractLinearCode

Representation of a cyclic code.

We propose three different ways to create a new CyclicCode, either by providing:

  • the generator polynomial and the length (1)

  • an existing linear code. In that case, a generator polynomial will be computed from the provided linear code’s parameters (2)

  • (a subset of) the defining set of the cyclic code (3)

For now, only single-root cyclic codes are implemented. That is, only cyclic codes such that its length \(n\) and field order \(q\) are coprimes.

Depending on which behaviour you want, you need to specify the names of the arguments to CyclicCode. See EXAMPLES section below for details.

INPUT:

  • generator_pol – (default: None) the generator polynomial of self. That is, the highest-degree monic polynomial which divides every polynomial representation of a codeword in self.

  • length – (default: None) the length of self. It has to be bigger than the degree of generator_pol.

  • code – (default: None) a linear code.

  • check – (default: False) a boolean representing whether the cyclicity of self must be checked while finding the generator polynomial. See find_generator_polynomial() for details.

  • D – (default: None) a list of integers between 0 and length-1, corresponding to (a subset of) the defining set of the code. Will be modified if it is not cyclotomic-closed.

  • field – (default: None) the base field of self.

  • primitive_root – (default: None) the primitive root of the splitting field which contains the roots of the generator polynomial. It has to be of multiplicative order length over this field. If the splitting field is not field, it also have to be a polynomial in zx, where x is the degree of the extension over the prime field. For instance, over GF(16), it must be a polynomial in z4.

EXAMPLES:

We can construct a CyclicCode object using three different methods. First (1), we provide a generator polynomial and a code length:

sage: F.<x> = GF(2)[]
sage: n = 7
sage: g = x ** 3 + x + 1
sage: C = codes.CyclicCode(generator_pol=g, length=n)
sage: C
[7, 4] Cyclic Code over GF(2)

>>> from sage.all import *
>>> F = GF(Integer(2))['x']; (x,) = F._first_ngens(1)
>>> n = Integer(7)
>>> g = x ** Integer(3) + x + Integer(1)
>>> C = codes.CyclicCode(generator_pol=g, length=n)
>>> C
[7, 4] Cyclic Code over GF(2)

We can also provide a code (2). In that case, the program will try to extract a generator polynomial (see find_generator_polynomial() for details):

sage: C = codes.GeneralizedReedSolomonCode(GF(8, 'a').list()[1:], 4)
sage: Cc = codes.CyclicCode(code = C)
sage: Cc
[7, 4] Cyclic Code over GF(8)

>>> from sage.all import *
>>> C = codes.GeneralizedReedSolomonCode(GF(Integer(8), 'a').list()[Integer(1):], Integer(4))
>>> Cc = codes.CyclicCode(code = C)
>>> Cc
[7, 4] Cyclic Code over GF(8)

Finally, we can give (a subset of) a defining set for the code (3). In this case, the generator polynomial will be computed:

sage: F = GF(16, 'a')
sage: n = 15
sage: Cc = codes.CyclicCode(length=n, field=F, D = [1,2])
sage: Cc
[15, 13] Cyclic Code over GF(16)

>>> from sage.all import *
>>> F = GF(Integer(16), 'a')
>>> n = Integer(15)
>>> Cc = codes.CyclicCode(length=n, field=F, D = [Integer(1),Integer(2)])
>>> Cc
[15, 13] Cyclic Code over GF(16)
bch_bound(arithmetic=False)[source]#

Return the BCH bound of self which is a bound on self minimum distance.

See sage.coding.cyclic_code.bch_bound() for details.

INPUT:

  • arithmetic – (default: False), if it is set to True, then it computes the BCH bound using the longest arithmetic sequence definition

OUTPUT:

  • (delta + 1, (l, c)) – such that delta + 1 is the BCH bound, and l, c are the parameters of the largest arithmetic sequence

EXAMPLES:

sage: F = GF(16, 'a')
sage: n = 15
sage: D = [14,1,2,11,12]
sage: C = codes.CyclicCode(field=F, length=n, D = D)
sage: C.bch_bound()
(3, (1, 1))

sage: F = GF(16, 'a')
sage: n = 15
sage: D = [14,1,2,11,12]
sage: C = codes.CyclicCode(field=F, length=n, D = D)
sage: C.bch_bound(True)
(4, (2, 12))

>>> from sage.all import *
>>> F = GF(Integer(16), 'a')
>>> n = Integer(15)
>>> D = [Integer(14),Integer(1),Integer(2),Integer(11),Integer(12)]
>>> C = codes.CyclicCode(field=F, length=n, D = D)
>>> C.bch_bound()
(3, (1, 1))

>>> F = GF(Integer(16), 'a')
>>> n = Integer(15)
>>> D = [Integer(14),Integer(1),Integer(2),Integer(11),Integer(12)]
>>> C = codes.CyclicCode(field=F, length=n, D = D)
>>> C.bch_bound(True)
(4, (2, 12))
check_polynomial()[source]#

Return the check polynomial of self.

Let \(C\) be a cyclic code of length \(n\) and \(g\) its generator polynomial. The following: \(h = \frac{x^n - 1}{g(x)}\) is called \(C\)’s check polynomial.

EXAMPLES:

sage: F.<x> = GF(2)[]
sage: n = 7
sage: g = x ** 3 + x + 1
sage: C = codes.CyclicCode(generator_pol=g, length=n)
sage: h = C.check_polynomial()
sage: h == (x**n - 1)/C.generator_polynomial()
True

>>> from sage.all import *
>>> F = GF(Integer(2))['x']; (x,) = F._first_ngens(1)
>>> n = Integer(7)
>>> g = x ** Integer(3) + x + Integer(1)
>>> C = codes.CyclicCode(generator_pol=g, length=n)
>>> h = C.check_polynomial()
>>> h == (x**n - Integer(1))/C.generator_polynomial()
True
defining_set(primitive_root=None)[source]#

Return the set of exponents of the roots of self’s generator polynomial over the extension field.

Of course, it depends on the choice of the primitive root of the splitting field.

INPUT:

  • primitive_root (optional) – a primitive root of the extension field

EXAMPLES:

We provide a defining set at construction time:

sage: F = GF(16, 'a')
sage: n = 15
sage: C = codes.CyclicCode(length=n, field=F, D=[1,2])
sage: C.defining_set()
[1, 2]

>>> from sage.all import *
>>> F = GF(Integer(16), 'a')
>>> n = Integer(15)
>>> C = codes.CyclicCode(length=n, field=F, D=[Integer(1),Integer(2)])
>>> C.defining_set()
[1, 2]

If the defining set was provided by the user, it might have been expanded at construction time. In this case, the expanded defining set will be returned:

sage: C = codes.CyclicCode(length=13, field=F, D=[1, 2])
sage: C.defining_set()
[1, 2, 3, 5, 6, 9]

>>> from sage.all import *
>>> C = codes.CyclicCode(length=Integer(13), field=F, D=[Integer(1), Integer(2)])
>>> C.defining_set()
[1, 2, 3, 5, 6, 9]

If a generator polynomial was passed at construction time, the defining set is computed using this polynomial:

sage: R.<x> = F[]
sage: n = 7
sage: g = x ** 3 + x + 1
sage: C = codes.CyclicCode(generator_pol=g, length=n)
sage: C.defining_set()
[1, 2, 4]

>>> from sage.all import *
>>> R = F['x']; (x,) = R._first_ngens(1)
>>> n = Integer(7)
>>> g = x ** Integer(3) + x + Integer(1)
>>> C = codes.CyclicCode(generator_pol=g, length=n)
>>> C.defining_set()
[1, 2, 4]

Both operations give the same result:

sage: C1 = codes.CyclicCode(length=n, field=F, D=[1, 2, 4])
sage: C1.generator_polynomial() == g
True

>>> from sage.all import *
>>> C1 = codes.CyclicCode(length=n, field=F, D=[Integer(1), Integer(2), Integer(4)])
>>> C1.generator_polynomial() == g
True

Another one, in a reversed order:

sage: n = 13
sage: C1 = codes.CyclicCode(length=n, field=F, D=[1, 2])
sage: g = C1.generator_polynomial()
sage: C2 = codes.CyclicCode(generator_pol=g, length=n)
sage: C1.defining_set() == C2.defining_set()
True

>>> from sage.all import *
>>> n = Integer(13)
>>> C1 = codes.CyclicCode(length=n, field=F, D=[Integer(1), Integer(2)])
>>> g = C1.generator_polynomial()
>>> C2 = codes.CyclicCode(generator_pol=g, length=n)
>>> C1.defining_set() == C2.defining_set()
True
field_embedding()[source]#

Return the base field embedding into the splitting field.

EXAMPLES:

sage: F.<x> = GF(2)[]
sage: n = 7
sage: g = x ** 3 + x + 1
sage: C = codes.CyclicCode(generator_pol=g, length=n)
sage: C.field_embedding()
Ring morphism:
  From: Finite Field of size 2
  To:   Finite Field in z3 of size 2^3
  Defn: 1 |--> 1

>>> from sage.all import *
>>> F = GF(Integer(2))['x']; (x,) = F._first_ngens(1)
>>> n = Integer(7)
>>> g = x ** Integer(3) + x + Integer(1)
>>> C = codes.CyclicCode(generator_pol=g, length=n)
>>> C.field_embedding()
Ring morphism:
  From: Finite Field of size 2
  To:   Finite Field in z3 of size 2^3
  Defn: 1 |--> 1
generator_polynomial()[source]#

Return the generator polynomial of self.

EXAMPLES:

sage: F.<x> = GF(2)[]
sage: n = 7
sage: g = x ** 3 + x + 1
sage: C = codes.CyclicCode(generator_pol=g, length=n)
sage: C.generator_polynomial()
x^3 + x + 1

>>> from sage.all import *
>>> F = GF(Integer(2))['x']; (x,) = F._first_ngens(1)
>>> n = Integer(7)
>>> g = x ** Integer(3) + x + Integer(1)
>>> C = codes.CyclicCode(generator_pol=g, length=n)
>>> C.generator_polynomial()
x^3 + x + 1
parity_check_matrix()[source]#

Return the parity check matrix of self.

The parity check matrix of a linear code \(C\) corresponds to the generator matrix of the dual code of \(C\).

EXAMPLES:

sage: F.<x> = GF(2)[]
sage: n = 7
sage: g = x ** 3 + x + 1
sage: C = codes.CyclicCode(generator_pol=g, length=n)
sage: C.parity_check_matrix()
[1 0 1 1 1 0 0]
[0 1 0 1 1 1 0]
[0 0 1 0 1 1 1]

>>> from sage.all import *
>>> F = GF(Integer(2))['x']; (x,) = F._first_ngens(1)
>>> n = Integer(7)
>>> g = x ** Integer(3) + x + Integer(1)
>>> C = codes.CyclicCode(generator_pol=g, length=n)
>>> C.parity_check_matrix()
[1 0 1 1 1 0 0]
[0 1 0 1 1 1 0]
[0 0 1 0 1 1 1]
primitive_root()[source]#

Return the primitive root of the splitting field that is used to build the defining set of the code.

If it has not been specified by the user, it is set by default with the output of the zeta method of the splitting field.

EXAMPLES:

sage: F.<x> = GF(2)[]
sage: n = 7
sage: g = x ** 3 + x + 1
sage: C = codes.CyclicCode(generator_pol=g, length=n)
sage: C.primitive_root()
z3

sage: F = GF(16, 'a')
sage: n = 15
sage: a = F.gen()
sage: Cc = codes.CyclicCode(length=n, field=F, D=[1,2],
....:                       primitive_root=a^2 + 1)
sage: Cc.primitive_root()
a^2 + 1

>>> from sage.all import *
>>> F = GF(Integer(2))['x']; (x,) = F._first_ngens(1)
>>> n = Integer(7)
>>> g = x ** Integer(3) + x + Integer(1)
>>> C = codes.CyclicCode(generator_pol=g, length=n)
>>> C.primitive_root()
z3

>>> F = GF(Integer(16), 'a')
>>> n = Integer(15)
>>> a = F.gen()
>>> Cc = codes.CyclicCode(length=n, field=F, D=[Integer(1),Integer(2)],
...                       primitive_root=a**Integer(2) + Integer(1))
>>> Cc.primitive_root()
a^2 + 1
surrounding_bch_code()[source]#

Return the surrounding BCH code of self.

EXAMPLES:

sage: C = codes.CyclicCode(field=GF(2), length=63, D=[1, 7, 17])
sage: C.dimension()
45
sage: CC = C.surrounding_bch_code()
sage: CC
[63, 51] BCH Code over GF(2) with designed distance 3
sage: all(r in CC for r in C.generator_matrix())
True

>>> from sage.all import *
>>> C = codes.CyclicCode(field=GF(Integer(2)), length=Integer(63), D=[Integer(1), Integer(7), Integer(17)])
>>> C.dimension()
45
>>> CC = C.surrounding_bch_code()
>>> CC
[63, 51] BCH Code over GF(2) with designed distance 3
>>> all(r in CC for r in C.generator_matrix())
True
class sage.coding.cyclic_code.CyclicCodePolynomialEncoder(code)[source]#

Bases: Encoder

An encoder encoding polynomials into codewords.

Let \(C\) be a cyclic code over some finite field \(F\), and let \(g\) be its generator polynomial.

This encoder encodes any polynomial \(p \in F[x]_{<k}\) by computing \(c = p g\) and returning the vector of its coefficients.

INPUT:

  • code – The associated code of this encoder

EXAMPLES:

sage: F.<x> = GF(2)[]
sage: n = 7
sage: g = x ** 3 + x + 1
sage: C = codes.CyclicCode(generator_pol=g, length=n)
sage: E = codes.encoders.CyclicCodePolynomialEncoder(C)
sage: E
Polynomial-style encoder for [7, 4] Cyclic Code over GF(2)

>>> from sage.all import *
>>> F = GF(Integer(2))['x']; (x,) = F._first_ngens(1)
>>> n = Integer(7)
>>> g = x ** Integer(3) + x + Integer(1)
>>> C = codes.CyclicCode(generator_pol=g, length=n)
>>> E = codes.encoders.CyclicCodePolynomialEncoder(C)
>>> E
Polynomial-style encoder for [7, 4] Cyclic Code over GF(2)
encode(p)[source]#

Transforms p into an element of the associated code of self.

INPUT:

  • p – A polynomial from self message space

OUTPUT:

  • A codeword in associated code of self

EXAMPLES:

sage: F.<x> = GF(2)[]
sage: n = 7
sage: g = x ** 3 + x + 1
sage: C = codes.CyclicCode(generator_pol=g, length=n)
sage: E = codes.encoders.CyclicCodePolynomialEncoder(C)
sage: m = x ** 2 + 1
sage: E.encode(m)
(1, 1, 1, 0, 0, 1, 0)

>>> from sage.all import *
>>> F = GF(Integer(2))['x']; (x,) = F._first_ngens(1)
>>> n = Integer(7)
>>> g = x ** Integer(3) + x + Integer(1)
>>> C = codes.CyclicCode(generator_pol=g, length=n)
>>> E = codes.encoders.CyclicCodePolynomialEncoder(C)
>>> m = x ** Integer(2) + Integer(1)
>>> E.encode(m)
(1, 1, 1, 0, 0, 1, 0)
message_space()[source]#

Return the message space of self

EXAMPLES:

sage: F.<x> = GF(2)[]
sage: n = 7
sage: g = x ** 3 + x + 1
sage: C = codes.CyclicCode(generator_pol=g, length=n)
sage: E = codes.encoders.CyclicCodePolynomialEncoder(C)
sage: E.message_space()                                                     # needs sage.libs.ntl
Univariate Polynomial Ring in x over Finite Field of size 2 (using GF2X)

>>> from sage.all import *
>>> F = GF(Integer(2))['x']; (x,) = F._first_ngens(1)
>>> n = Integer(7)
>>> g = x ** Integer(3) + x + Integer(1)
>>> C = codes.CyclicCode(generator_pol=g, length=n)
>>> E = codes.encoders.CyclicCodePolynomialEncoder(C)
>>> E.message_space()                                                     # needs sage.libs.ntl
Univariate Polynomial Ring in x over Finite Field of size 2 (using GF2X)
unencode_nocheck(c)[source]#

Return the message corresponding to c. Does not check if c belongs to the code.

INPUT:

  • c – A vector with the same length as the code

OUTPUT:

  • An element of the message space

EXAMPLES:

sage: F.<x> = GF(2)[]
sage: n = 7
sage: g = x ** 3 + x + 1
sage: C = codes.CyclicCode(generator_pol=g, length=n)
sage: E = codes.encoders.CyclicCodePolynomialEncoder(C)
sage: c = vector(GF(2), (1, 1, 1, 0, 0, 1, 0))
sage: E.unencode_nocheck(c)
x^2 + 1

>>> from sage.all import *
>>> F = GF(Integer(2))['x']; (x,) = F._first_ngens(1)
>>> n = Integer(7)
>>> g = x ** Integer(3) + x + Integer(1)
>>> C = codes.CyclicCode(generator_pol=g, length=n)
>>> E = codes.encoders.CyclicCodePolynomialEncoder(C)
>>> c = vector(GF(Integer(2)), (Integer(1), Integer(1), Integer(1), Integer(0), Integer(0), Integer(1), Integer(0)))
>>> E.unencode_nocheck(c)
x^2 + 1
class sage.coding.cyclic_code.CyclicCodeSurroundingBCHDecoder(code, **kwargs)[source]#

Bases: Decoder

A decoder which decodes through the surrounding BCH code of the cyclic code.

INPUT:

  • code – The associated code of this decoder.

  • **kwargs – All extra arguments are forwarded to the BCH decoder

EXAMPLES:

sage: C = codes.CyclicCode(field=GF(16), length=15, D=[14, 1, 2, 11, 12])
sage: D = codes.decoders.CyclicCodeSurroundingBCHDecoder(C)
sage: D
Decoder through the surrounding BCH code of the [15, 10] Cyclic Code over GF(16)

>>> from sage.all import *
>>> C = codes.CyclicCode(field=GF(Integer(16)), length=Integer(15), D=[Integer(14), Integer(1), Integer(2), Integer(11), Integer(12)])
>>> D = codes.decoders.CyclicCodeSurroundingBCHDecoder(C)
>>> D
Decoder through the surrounding BCH code of the [15, 10] Cyclic Code over GF(16)
bch_code()[source]#

Return the surrounding BCH code of sage.coding.encoder.Encoder.code().

EXAMPLES:

sage: C = codes.CyclicCode(field=GF(16), length=15, D=[14, 1, 2, 11, 12])
sage: D = codes.decoders.CyclicCodeSurroundingBCHDecoder(C)
sage: D.bch_code()
[15, 12] BCH Code over GF(16) with designed distance 4

>>> from sage.all import *
>>> C = codes.CyclicCode(field=GF(Integer(16)), length=Integer(15), D=[Integer(14), Integer(1), Integer(2), Integer(11), Integer(12)])
>>> D = codes.decoders.CyclicCodeSurroundingBCHDecoder(C)
>>> D.bch_code()
[15, 12] BCH Code over GF(16) with designed distance 4
bch_decoder()[source]#

Return the decoder that will be used over the surrounding BCH code.

EXAMPLES:

sage: C = codes.CyclicCode(field=GF(16), length=15, D=[14, 1, 2, 11, 12])
sage: D = codes.decoders.CyclicCodeSurroundingBCHDecoder(C)
sage: D.bch_decoder()
Decoder through the underlying GRS code of [15, 12] BCH Code
 over GF(16) with designed distance 4

>>> from sage.all import *
>>> C = codes.CyclicCode(field=GF(Integer(16)), length=Integer(15), D=[Integer(14), Integer(1), Integer(2), Integer(11), Integer(12)])
>>> D = codes.decoders.CyclicCodeSurroundingBCHDecoder(C)
>>> D.bch_decoder()
Decoder through the underlying GRS code of [15, 12] BCH Code
 over GF(16) with designed distance 4
decode_to_code(y)[source]#

Decodes r to an element in sage.coding.encoder.Encoder.code().

EXAMPLES:

sage: F = GF(16, 'a')
sage: C = codes.CyclicCode(field=F, length=15, D=[14, 1, 2, 11, 12])
sage: a = F.gen()
sage: D = codes.decoders.CyclicCodeSurroundingBCHDecoder(C)
sage: y = vector(F, [0, a^3, a^3 + a^2 + a, 1, a^2 + 1, a^3 + a^2 + 1,
....:                a^3 + a^2 + a, a^3 + a^2 + a, a^2 + a, a^2 + 1,
....:                a^2 + a + 1, a^3 + 1, a^2, a^3 + a, a^3 + a])
sage: D.decode_to_code(y) in C
True

>>> from sage.all import *
>>> F = GF(Integer(16), 'a')
>>> C = codes.CyclicCode(field=F, length=Integer(15), D=[Integer(14), Integer(1), Integer(2), Integer(11), Integer(12)])
>>> a = F.gen()
>>> D = codes.decoders.CyclicCodeSurroundingBCHDecoder(C)
>>> y = vector(F, [Integer(0), a**Integer(3), a**Integer(3) + a**Integer(2) + a, Integer(1), a**Integer(2) + Integer(1), a**Integer(3) + a**Integer(2) + Integer(1),
...                a**Integer(3) + a**Integer(2) + a, a**Integer(3) + a**Integer(2) + a, a**Integer(2) + a, a**Integer(2) + Integer(1),
...                a**Integer(2) + a + Integer(1), a**Integer(3) + Integer(1), a**Integer(2), a**Integer(3) + a, a**Integer(3) + a])
>>> D.decode_to_code(y) in C
True
decoding_radius()[source]#

Return maximal number of errors that self can decode.

EXAMPLES:

sage: C = codes.CyclicCode(field=GF(16), length=15, D=[14, 1, 2, 11, 12])
sage: D = codes.decoders.CyclicCodeSurroundingBCHDecoder(C)
sage: D.decoding_radius()
1

>>> from sage.all import *
>>> C = codes.CyclicCode(field=GF(Integer(16)), length=Integer(15), D=[Integer(14), Integer(1), Integer(2), Integer(11), Integer(12)])
>>> D = codes.decoders.CyclicCodeSurroundingBCHDecoder(C)
>>> D.decoding_radius()
1
class sage.coding.cyclic_code.CyclicCodeVectorEncoder(code)[source]#

Bases: Encoder

An encoder which can encode vectors into codewords.

Let \(C\) be a cyclic code over some finite field \(F\), and let \(g\) be its generator polynomial.

Let \(m = (m_1, m_2, \dots, m_k)\) be a vector in \(F^{k}\). This codeword can be seen as a polynomial over \(F[x]\), as follows: \(P_m = \Sigma_{i=0}^{k-1} m_i \times x^i\).

To encode \(m\), this encoder does the multiplication \(P_m g\).

INPUT:

  • code – The associated code of this encoder

EXAMPLES:

sage: F.<x> = GF(2)[]
sage: n = 7
sage: g = x ** 3 + x + 1
sage: C = codes.CyclicCode(generator_pol=g, length=n)
sage: E = codes.encoders.CyclicCodeVectorEncoder(C)
sage: E
Vector-style encoder for [7, 4] Cyclic Code over GF(2)

>>> from sage.all import *
>>> F = GF(Integer(2))['x']; (x,) = F._first_ngens(1)
>>> n = Integer(7)
>>> g = x ** Integer(3) + x + Integer(1)
>>> C = codes.CyclicCode(generator_pol=g, length=n)
>>> E = codes.encoders.CyclicCodeVectorEncoder(C)
>>> E
Vector-style encoder for [7, 4] Cyclic Code over GF(2)
encode(m)[source]#

Transforms m into an element of the associated code of self.

INPUT:

  • m – an element from self’s message space

OUTPUT:

  • A codeword in the associated code of self

EXAMPLES:

sage: F.<x> = GF(2)[]
sage: n = 7
sage: g = x ** 3 + x + 1
sage: C = codes.CyclicCode(generator_pol=g, length=n)
sage: E = codes.encoders.CyclicCodeVectorEncoder(C)
sage: m = vector(GF(2), (1, 0, 1, 0))
sage: E.encode(m)
(1, 1, 1, 0, 0, 1, 0)

>>> from sage.all import *
>>> F = GF(Integer(2))['x']; (x,) = F._first_ngens(1)
>>> n = Integer(7)
>>> g = x ** Integer(3) + x + Integer(1)
>>> C = codes.CyclicCode(generator_pol=g, length=n)
>>> E = codes.encoders.CyclicCodeVectorEncoder(C)
>>> m = vector(GF(Integer(2)), (Integer(1), Integer(0), Integer(1), Integer(0)))
>>> E.encode(m)
(1, 1, 1, 0, 0, 1, 0)
generator_matrix()[source]#

Return a generator matrix of self

EXAMPLES:

sage: F.<x> = GF(2)[]
sage: n = 7
sage: g = x ** 3 + x + 1
sage: C = codes.CyclicCode(generator_pol=g, length=n)
sage: E = codes.encoders.CyclicCodeVectorEncoder(C)
sage: E.generator_matrix()
[1 1 0 1 0 0 0]
[0 1 1 0 1 0 0]
[0 0 1 1 0 1 0]
[0 0 0 1 1 0 1]

>>> from sage.all import *
>>> F = GF(Integer(2))['x']; (x,) = F._first_ngens(1)
>>> n = Integer(7)
>>> g = x ** Integer(3) + x + Integer(1)
>>> C = codes.CyclicCode(generator_pol=g, length=n)
>>> E = codes.encoders.CyclicCodeVectorEncoder(C)
>>> E.generator_matrix()
[1 1 0 1 0 0 0]
[0 1 1 0 1 0 0]
[0 0 1 1 0 1 0]
[0 0 0 1 1 0 1]
message_space()[source]#

Return the message space of self

EXAMPLES:

sage: F.<x> = GF(2)[]
sage: n = 7
sage: g = x ** 3 + x + 1
sage: C = codes.CyclicCode(generator_pol=g, length=n)
sage: E = codes.encoders.CyclicCodeVectorEncoder(C)
sage: E.message_space()
Vector space of dimension 4 over Finite Field of size 2

>>> from sage.all import *
>>> F = GF(Integer(2))['x']; (x,) = F._first_ngens(1)
>>> n = Integer(7)
>>> g = x ** Integer(3) + x + Integer(1)
>>> C = codes.CyclicCode(generator_pol=g, length=n)
>>> E = codes.encoders.CyclicCodeVectorEncoder(C)
>>> E.message_space()
Vector space of dimension 4 over Finite Field of size 2
unencode_nocheck(c)[source]#

Return the message corresponding to c. Does not check if c belongs to the code.

INPUT:

  • c – A vector with the same length as the code

OUTPUT:

  • An element of the message space

EXAMPLES:

sage: F.<x> = GF(2)[]
sage: n = 7
sage: g = x ** 3 + x + 1
sage: C = codes.CyclicCode(generator_pol=g, length=n)
sage: E = codes.encoders.CyclicCodeVectorEncoder(C)
sage: c = vector(GF(2), (1, 1, 1, 0, 0, 1, 0))
sage: E.unencode_nocheck(c)
(1, 0, 1, 0)

>>> from sage.all import *
>>> F = GF(Integer(2))['x']; (x,) = F._first_ngens(1)
>>> n = Integer(7)
>>> g = x ** Integer(3) + x + Integer(1)
>>> C = codes.CyclicCode(generator_pol=g, length=n)
>>> E = codes.encoders.CyclicCodeVectorEncoder(C)
>>> c = vector(GF(Integer(2)), (Integer(1), Integer(1), Integer(1), Integer(0), Integer(0), Integer(1), Integer(0)))
>>> E.unencode_nocheck(c)
(1, 0, 1, 0)
sage.coding.cyclic_code.bch_bound(n, D, arithmetic=False)[source]#

Return the BCH bound obtained for a cyclic code of length n and defining set D.

Consider a cyclic code \(C\), with defining set \(D\), length \(n\), and minimum distance \(d\). We have the following bound, called BCH bound, on \(d\): \(d \geq \delta + 1\), where \(\delta\) is the length of the longest arithmetic sequence (modulo \(n\)) of elements in \(D\).

That is, if \(\exists c, \gcd(c,n) = 1\) such that \(\{l, l+c, \dots, l + (\delta - 1) \times c\} \subseteq D\), then \(d \geq \delta + 1\) [1]

The BCH bound is often known in the particular case \(c = 1\). The user can specify by setting arithmetic = False.

Note

As this is a specific use case of the BCH bound, it is not available in the global namespace. Call it by using sage.coding.cyclic_code.bch_bound. You can also load it into the global namespace by typing from sage.coding.cyclic_code import bch_bound.

INPUT:

  • n – an integer

  • D – a list of integers

  • arithmetic – (default: False), if it is set to True, then it computes the BCH bound using the longest arithmetic sequence definition

OUTPUT:

  • (delta + 1, (l, c)) – such that delta + 1 is the BCH bound, and l, c are the parameters of the longest arithmetic sequence (see below)

EXAMPLES:

sage: n = 15
sage: D = [14,1,2,11,12]
sage: sage.coding.cyclic_code.bch_bound(n, D)
(3, (1, 1))

sage: n = 15
sage: D = [14,1,2,11,12]
sage: sage.coding.cyclic_code.bch_bound(n, D, True)
(4, (2, 12))

>>> from sage.all import *
>>> n = Integer(15)
>>> D = [Integer(14),Integer(1),Integer(2),Integer(11),Integer(12)]
>>> sage.coding.cyclic_code.bch_bound(n, D)
(3, (1, 1))

>>> n = Integer(15)
>>> D = [Integer(14),Integer(1),Integer(2),Integer(11),Integer(12)]
>>> sage.coding.cyclic_code.bch_bound(n, D, True)
(4, (2, 12))
sage.coding.cyclic_code.find_generator_polynomial(code, check=True)[source]#

Return a possible generator polynomial for code.

If the code is cyclic, the generator polynomial is the gcd of all the polynomial forms of the codewords. Conversely, if this gcd exactly generates the code code, then code is cyclic.

If check is set to True, then it also checks that the code is indeed cyclic. Otherwise it doesn’t.

INPUT:

  • code – a linear code

  • check – whether the cyclicity should be checked

OUTPUT:

  • the generator polynomial of code (if the code is cyclic).

EXAMPLES:

sage: from sage.coding.cyclic_code import find_generator_polynomial
sage: C = codes.GeneralizedReedSolomonCode(GF(8, 'a').list()[1:], 4)
sage: find_generator_polynomial(C)
x^3 + (a^2 + 1)*x^2 + a*x + a^2 + 1

>>> from sage.all import *
>>> from sage.coding.cyclic_code import find_generator_polynomial
>>> C = codes.GeneralizedReedSolomonCode(GF(Integer(8), 'a').list()[Integer(1):], Integer(4))
>>> find_generator_polynomial(C)
x^3 + (a^2 + 1)*x^2 + a*x + a^2 + 1