Goppa code¶
This module implements Goppa codes and an encoder for them.
EXAMPLES:
sage: F = GF(2^6)
sage: R.<x> = F[]
sage: g = x^9 + 1
sage: L = [a for a in F.list() if g(a) != 0]
sage: C = codes.GoppaCode(g, L)
sage: C
[55, 16] Goppa code over GF(2)
sage: E = codes.encoders.GoppaCodeEncoder(C)
sage: E
Encoder for [55, 16] Goppa code over GF(2)
AUTHORS:
Filip Ion, Marketa Slukova (2019-06): initial version
- class sage.coding.goppa_code.GoppaCode(generating_pol, defining_set)¶
Bases:
sage.coding.linear_code.AbstractLinearCode
Implementation of Goppa codes.
Goppa codes are a generalization of narrow-sense BCH codes. These codes are defined by a generating polynomial \(g\) over a finite field \(\GF{p^m}\), and a defining set \(L\) of elements from \(\GF{p^m}\), which are not roots of \(g\). The number of defining elements determines the length of the code.
In binary cases, the minimum distance is \(2t + 1\), where \(t\) is the degree of \(g\).
INPUT:
generating_pol
– a monic polynomial with coefficients in a finite field \(\GF{p^m}\), the code is defined over \(\GF{p}\), \(p\) must be a prime numberdefining_set
– a set of elements of \(\GF{p^m}\) that are not roots of \(g\), its cardinality is the length of the code
EXAMPLES:
sage: F = GF(2^6) sage: R.<x> = F[] sage: g = x^9 + 1 sage: L = [a for a in F.list() if g(a) != 0] sage: C = codes.GoppaCode(g, L) sage: C [55, 16] Goppa code over GF(2)
- distance_bound()¶
Return a lower bound for the minimum distance of the code.
Computed using the degree of the generating polynomial of
self
. The minimum distance is guaranteed to be bigger than or equal to this bound.EXAMPLES:
sage: F = GF(2^3) sage: R.<x> = F[] sage: g = x^2 + x + 1 sage: L = [a for a in F.list() if g(a) != 0] sage: C = codes.GoppaCode(g, L) sage: C [8, 2] Goppa code over GF(2) sage: C.distance_bound() 3 sage: C.minimum_distance() 5
- parity_check_matrix()¶
Return a parity check matrix for
self
.The element in row \(t\), column \(i\) is \(h[i](D[i]^t)\), where:
\(h[i]\) – is the inverse of \(g(D[i])\)
\(D[i]\) – is the \(i\)-th element of the defining set
In the resulting \(d \times n\) matrix we interpret each entry as an \(m\)-column vector and return a \(dm \times n\) matrix.
EXAMPLES:
sage: F = GF(2^3) sage: R.<x> = F[] sage: g = x^2 + x+ 1 sage: L = [a for a in F.list() if g(a) != 0] sage: C = codes.GoppaCode(g, L) sage: C [8, 2] Goppa code over GF(2) sage: C.parity_check_matrix() [1 0 0 0 0 0 0 1] [0 0 1 0 1 1 1 0] [0 1 1 1 0 0 1 0] [0 1 1 1 1 1 1 1] [0 1 0 1 1 0 1 0] [0 0 1 1 1 1 0 0]
- class sage.coding.goppa_code.GoppaCodeEncoder(code)¶
Bases:
sage.coding.encoder.Encoder
Encoder for Goppa codes
Encodes words represented as vectors of length \(k\), where \(k\) is the dimension of
self
, with entries from \(\GF{p}\), the prime field of the base field of the generating polynomial ofself
, into codewords of length \(n\), with entries from \(\GF{p}\).EXAMPLES:
sage: F = GF(2^3) sage: R.<x> = F[] sage: g = x^2 + x + 1 sage: L = [a for a in F.list() if g(a) != 0] sage: C = codes.GoppaCode(g, L) sage: C [8, 2] Goppa code over GF(2) sage: E = codes.encoders.GoppaCodeEncoder(C) sage: E Encoder for [8, 2] Goppa code over GF(2) sage: word = vector(GF(2), (0, 1)) sage: c = E.encode(word) sage: c (0, 1, 1, 1, 1, 1, 1, 0) sage: c in C True
- generator_matrix()¶
A generator matrix for
self
Dimension of resulting matrix is \(k \times n\), where \(k\) is the dimension of
self
and \(n\) is the length ofself
.EXAMPLES:
sage: F = GF(2^3) sage: R.<x> = F[] sage: g = (x^2 + x + 1)^2 sage: L = [a for a in F.list() if g(a) != 0] sage: C = codes.GoppaCode(g, L) sage: C [8, 2] Goppa code over GF(2) sage: C.generator_matrix() [1 0 0 1 0 1 1 1] [0 1 1 1 1 1 1 0]