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 – boolean (default: False); 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

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)

Python

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

Sage Live

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

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

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)

Python

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

Sage Live

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

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

Sage

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)

Python

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

Sage Live

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

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

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

Python

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

Sage Live

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

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

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

Python

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

Sage Live

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

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

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]

Python

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

Sage Live

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

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

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

Python

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

Sage Live

C = codes.CyclicCode(length=13, field=F, D=[1, 2])
C.defining_set()

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

Sage

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]

Python

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

Sage Live

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

Both operations give the same result:

Sage

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

Python

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

Sage Live

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

Another one, in a reversed order:

Sage

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

Python

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

Sage Live

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

field_embedding()[source]¶

Return the base field embedding into the splitting field.

EXAMPLES:

Sage

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

Python

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

Sage Live

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

generator_polynomial()[source]¶

Return the generator polynomial of self.

EXAMPLES:

Sage

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

Python

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

Sage Live

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

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

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]

Python

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

Sage Live

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

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

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

Python

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

Sage Live

F.<x> = GF(2)[]
n = 7
g = x ** 3 + x + 1
C = codes.CyclicCode(generator_pol=g, length=n)
C.primitive_root()
F = GF(16, 'a')
n = 15
a = F.gen()
Cc = codes.CyclicCode(length=n, field=F, D=[1,2],
                      primitive_root=a^2 + 1)
Cc.primitive_root()

surrounding_bch_code()[source]¶

Return the surrounding BCH code of self.

EXAMPLES:

Sage

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

Python

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

Sage Live

C = codes.CyclicCode(field=GF(2), length=63, D=[1, 7, 17])
C.dimension()
CC = C.surrounding_bch_code()
CC
all(r in CC for r in C.generator_matrix())

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

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)

Python

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

Sage Live

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

encode(p)[source]¶

Transform \(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

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)

Python

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

Sage Live

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

message_space()[source]¶

Return the message space of self.

EXAMPLES:

Sage

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)

Python

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

Sage Live

F.<x> = GF(2)[]
n = 7
g = x ** 3 + x + 1
C = codes.CyclicCode(generator_pol=g, length=n)
E = codes.encoders.CyclicCodePolynomialEncoder(C)
E.message_space()                                                     # needs sage.libs.ntl

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

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

Python

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

Sage Live

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

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

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)

Python

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

Sage Live

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

bch_code()[source]¶

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

EXAMPLES:

Sage

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

Python

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

Sage Live

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

bch_decoder()[source]¶

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

EXAMPLES:

Sage

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

Python

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

Sage Live

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

decode_to_code(y)[source]¶

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

EXAMPLES:

Sage

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

Python

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

Sage Live

F = GF(16, 'a')
C = codes.CyclicCode(field=F, length=15, D=[14, 1, 2, 11, 12])
a = F.gen()
D = codes.decoders.CyclicCodeSurroundingBCHDecoder(C)
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])
D.decode_to_code(y) in C

decoding_radius()[source]¶

Return maximal number of errors that self can decode.

EXAMPLES:

Sage

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

Python

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

Sage Live

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

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

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)

Python

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

Sage Live

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

encode(m)[source]¶

Transform \(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

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)

Python

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

Sage Live

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

generator_matrix()[source]¶

Return a generator matrix of self.

EXAMPLES:

Sage

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]

Python

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

Sage Live

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

message_space()[source]¶

Return the message space of self.

EXAMPLES:

Sage

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

Python

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

Sage Live

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

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

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)

Python

>>> 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 Live

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

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 – integer
D – 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

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

Python

>>> 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 Live

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

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

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

Python

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

Sage Live

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