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 ofself
. That is, the highest-degree monic polynomial which divides every polynomial representation of a codeword inself
.length
– (default:None
) the length ofself
. It has to be bigger than the degree ofgenerator_pol
.code
– (default:None
) a linear code.check
– (default:False
) a boolean representing whether the cyclicity ofself
must be checked while finding the generator polynomial. Seefind_generator_polynomial()
for details.D
– (default:None
) a list of integers between0
andlength-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 ofself
.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 orderlength
over this field. If the splitting field is notfield
, it also have to be a polynomial inzx
, wherex
is the degree of the extension over the prime field. For instance, overGF(16)
, it must be a polynomial inz4
.
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 onself
minimum distance.See
sage.coding.cyclic_code.bch_bound()
for details.INPUT:
arithmetic
– (default:False
), if it is set toTrue
, then it computes the BCH bound using the longest arithmetic sequence definition
OUTPUT:
(delta + 1, (l, c))
– such thatdelta + 1
is the BCH bound, andl, 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() Ring morphism: From: Finite Field of size 2 To: Finite Field in z3 of size 2^3 Defn: 1 |--> 1
- 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 ofself
.INPUT:
p
– A polynomial fromself
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 ifc
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 insage.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 ofself
.INPUT:
m
– an element fromself
’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 ifc
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 setD
.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 typingfrom sage.coding.cyclic_code import bch_bound
.INPUT:
n
– an integerD
– a list of integersarithmetic
– (default:False
), if it is set toTrue
, then it computes the BCH bound using the longest arithmetic sequence definition
OUTPUT:
(delta + 1, (l, c))
– such thatdelta + 1
is the BCH bound, andl, 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
, thencode
is cyclic.If
check
is set toTrue
, then it also checks that the code is indeed cyclic. Otherwise it doesn’t.INPUT:
code
– a linear codecheck
– 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