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 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 codecheck
– boolean (default:False
); 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)
>>> 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 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))
>>> 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]¶
Transform \(p\) into an element of the associated code of
self
.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)
>>> 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 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
>>> 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 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
>>> 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]¶
Transform \(m\) into an element of the associated code of
self
.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)
>>> 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 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)
>>> 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 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
– integerD
– 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))
>>> 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
, 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
>>> 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