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)

>>> from sage.all import *
>>> F = GF(Integer(2)**Integer(6))
>>> R = F['x']; (x,) = R._first_ngens(1)
>>> g = x**Integer(9) + Integer(1)
>>> L = [a for a in F.list() if g(a) != Integer(0)]
>>> C = codes.GoppaCode(g, L)
>>> C
[55, 16] Goppa code over GF(2)
>>> E = codes.encoders.GoppaCodeEncoder(C)
>>> 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)[source]

Bases: 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 number

  • defining_set – 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)

>>> from sage.all import *
>>> F = GF(Integer(2)**Integer(6))
>>> R = F['x']; (x,) = R._first_ngens(1)
>>> g = x**Integer(9) + Integer(1)
>>> L = [a for a in F.list() if g(a) != Integer(0)]
>>> C = codes.GoppaCode(g, L)
>>> C
[55, 16] Goppa code over GF(2)
distance_bound()[source]

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()                                                  # needs sage.libs.gap
5

>>> from sage.all import *
>>> F = GF(Integer(2)**Integer(3))
>>> R = F['x']; (x,) = R._first_ngens(1)
>>> g = x**Integer(2) + x + Integer(1)
>>> L = [a for a in F.list() if g(a) != Integer(0)]
>>> C = codes.GoppaCode(g, L)
>>> C
[8, 2] Goppa code over GF(2)
>>> C.distance_bound()
3
>>> C.minimum_distance()                                                  # needs sage.libs.gap
5
parity_check_matrix()[source]

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]

>>> from sage.all import *
>>> F  = GF(Integer(2)**Integer(3))
>>> R = F['x']; (x,) = R._first_ngens(1)
>>> g = x**Integer(2) + x+ Integer(1)
>>> L = [a for a in F.list() if g(a) != Integer(0)]
>>> C = codes.GoppaCode(g, L)
>>> C
[8, 2] Goppa code over GF(2)
>>> 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)[source]

Bases: 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 of self, 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

>>> from sage.all import *
>>> F = GF(Integer(2)**Integer(3))
>>> R = F['x']; (x,) = R._first_ngens(1)
>>> g = x**Integer(2) + x + Integer(1)
>>> L = [a for a in F.list() if g(a) != Integer(0)]
>>> C = codes.GoppaCode(g, L)
>>> C
[8, 2] Goppa code over GF(2)
>>> E = codes.encoders.GoppaCodeEncoder(C)
>>> E
Encoder for [8, 2] Goppa code over GF(2)
>>> word = vector(GF(Integer(2)), (Integer(0), Integer(1)))
>>> c = E.encode(word)
>>> c
(0, 1, 1, 1, 1, 1, 1, 0)
>>> c in C
True
generator_matrix()[source]

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 of self.

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]

>>> from sage.all import *
>>> F = GF(Integer(2)**Integer(3))
>>> R = F['x']; (x,) = R._first_ngens(1)
>>> g = (x**Integer(2) + x + Integer(1))**Integer(2)
>>> L = [a for a in F.list() if g(a) != Integer(0)]
>>> C = codes.GoppaCode(g, L)
>>> C
[8, 2] Goppa code over GF(2)
>>> C.generator_matrix()
[1 0 0 1 0 1 1 1]
[0 1 1 1 1 1 1 0]