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

Bases: sage.coding.linear_code.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)

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)

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)

bch_bound(arithmetic=False)¶

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

check_polynomial()¶

Returns 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

defining_set(primitive_root=None)¶

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

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]

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]

Both operations give the same result:

sage: C1 = codes.CyclicCode(length=n, field=F, D=[1, 2, 4])
sage: 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

field_embedding()¶

Returns 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()
Relative field extension between Finite Field in z3 of size 2^3 and Finite Field of size 2

generator_polynomial()¶

Returns 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

parity_check_matrix()¶

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

primitive_root()¶

Returns 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

surrounding_bch_code()¶

Returns 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

class sage.coding.cyclic_code.CyclicCodePolynomialEncoder(code)¶

Bases: sage.coding.encoder.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 \times 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)

encode(p)¶

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)

message_space()¶

Returns 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()
Univariate Polynomial Ring in x over Finite Field of size 2 (using GF2X)

unencode_nocheck(c)¶

Returns 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

class sage.coding.cyclic_code.CyclicCodeSurroundingBCHDecoder(code, **kwargs)¶

Bases: sage.coding.decoder.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)

bch_code()¶

Returns 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

bch_decoder()¶

Returns 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

decode_to_code(y)¶

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

decoding_radius()¶

Returns 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

class sage.coding.cyclic_code.CyclicCodeVectorEncoder(code)¶

Bases: sage.coding.encoder.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 following multiplication: \(P_m \times 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)

encode(m)¶

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)

generator_matrix()¶

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

message_space()¶

Returns 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

unencode_nocheck(c)¶

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

sage.coding.cyclic_code.bch_bound(n, D, arithmetic=False)¶

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

sage.coding.cyclic_code.find_generator_polynomial(code, check=True)¶

Returns 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

Cyclic code¶

Previous topic

Next topic

This Page