Kasami code#

This module implements a construction for the extended Kasami codes. The “regular” Kasami codes are obtained from truncating the extended version.

The extended Kasami code with parameters \((s,t)\) is defined as

\[\{ v \in \GF{2}^s \mid \sum_{a \in \GF{s}} v_a = \sum_{a \in \GF{s}} a v_a = \sum_{a \in \GF{s}} a^{t+1} v_a = 0 \}\]

It follows that these are subfield subcodes of the code having those three equations as parity checks. The only valid parameters \(s,t\) are given by the below, where \(q\) is a power of 2

  • \(s = q^{2j+1}\), \(t = q^m\) with \(m \leq j\) and \(\gcd(m,2j+1) = 1\)

  • \(s = q^2\), \(t=q\)

The coset graphs of the Kasami codes are distance-regular. In particular, the extended Kasami codes result in distance-regular graphs with intersection arrays

  • \([q^{2j+1}, q^{2j+1} - 1, q^{2j+1} - q, q^{2j+1} - q^{2j} + 1;\) \(1, q, q^{2j} -1, q^{2j+1}]\)

  • \([q^2, q^2 - 1, q^2 - q, 1; 1, q, q^2 - 1, q^2]\)

The Kasami codes result in distance-regular graphs with intersection arrays

  • \([q^{2j+1} - 1, q^{2j+1} - q, q^{2j+1} - q^{2j} + 1; 1, q, q^{2j} -1]\)

  • \([q^2 - 1, q^2 - q, 1; 1, q, q^2 - 1]\)

REFERENCES:

AUTHORS:

  • Ivo Maffei (2020-07-09): initial version

class sage.coding.kasami_codes.KasamiCode(s, t, extended=True)[source]#

Bases: AbstractLinearCode

Representation of a Kasami Code.

The extended Kasami code with parameters \((s,t)\) is defined as

\[\{ v \in \GF{2}^s \mid \sum_{a \in \GF{s}} v_a = \sum_{a \in \GF{s}} a v_a = \sum_{a \in \GF{s}} a^{t+1} v_a = 0 \}\]

The only valid parameters \(s,t\) are given by the below, where \(q\) is a power of 2:

  • \(s = q^{2j+1}\), \(t = q^m\) with \(m \leq j\) and \(\gcd(m,2j+1) = 1\)

  • \(s = q^2\), \(t=q\)

The Kasami code \((s,t)\) is obtained from the extended Kasami code \((s,t)\), via truncation of all words.

INPUT:

  • s, t – (integer) the parameters of the Kasami code

  • extended – (default: True) if set to True, creates an extended Kasami code.

EXAMPLES:

sage: codes.KasamiCode(16,4)
[16, 9] Extended (16, 4)-Kasami code
sage: _.minimum_distance()                                                      # needs sage.libs.gap
4

sage: codes.KasamiCode(8, 2, extended=False)
[7, 1] (8, 2)-Kasami code

sage: codes.KasamiCode(8,4)
Traceback (most recent call last):
...
ValueError: The parameters(=8,4) are invalid. Check the documentation

>>> from sage.all import *
>>> codes.KasamiCode(Integer(16),Integer(4))
[16, 9] Extended (16, 4)-Kasami code
>>> _.minimum_distance()                                                      # needs sage.libs.gap
4

>>> codes.KasamiCode(Integer(8), Integer(2), extended=False)
[7, 1] (8, 2)-Kasami code

>>> codes.KasamiCode(Integer(8),Integer(4))
Traceback (most recent call last):
...
ValueError: The parameters(=8,4) are invalid. Check the documentation

The extended Kasami code is the extension of the Kasami code:

sage: C = codes.KasamiCode(16, 4, extended=False)
sage: Cext = C.extended_code()
sage: D = codes.KasamiCode(16, 4, extended=True)
sage: D.generator_matrix() == Cext.generator_matrix()
True

>>> from sage.all import *
>>> C = codes.KasamiCode(Integer(16), Integer(4), extended=False)
>>> Cext = C.extended_code()
>>> D = codes.KasamiCode(Integer(16), Integer(4), extended=True)
>>> D.generator_matrix() == Cext.generator_matrix()
True

See also

sage.coding.linear_code.

REFERENCES:

For more information on Kasami codes and their use see [BCN1989] or [Kas1966a], [Kas1966b], [Kas1971]

generator_matrix()[source]#

Return a generator matrix of self.

EXAMPLES:

sage: C = codes.KasamiCode(16, 4, extended=False)
sage: C.generator_matrix()
[1 0 0 0 0 0 0 0 0 1 0 0 1 1 1]
[0 1 0 0 0 0 0 0 0 1 1 0 1 0 0]
[0 0 1 0 0 0 0 0 0 0 1 1 0 1 0]
[0 0 0 1 0 0 0 0 0 0 0 1 1 0 1]
[0 0 0 0 1 0 0 0 0 0 0 0 1 1 0]
[0 0 0 0 0 1 0 0 0 1 1 0 1 1 1]
[0 0 0 0 0 0 1 0 0 0 1 1 0 1 1]
[0 0 0 0 0 0 0 1 0 1 1 1 0 0 1]
[0 0 0 0 0 0 0 0 1 1 0 1 0 0 0]

>>> from sage.all import *
>>> C = codes.KasamiCode(Integer(16), Integer(4), extended=False)
>>> C.generator_matrix()
[1 0 0 0 0 0 0 0 0 1 0 0 1 1 1]
[0 1 0 0 0 0 0 0 0 1 1 0 1 0 0]
[0 0 1 0 0 0 0 0 0 0 1 1 0 1 0]
[0 0 0 1 0 0 0 0 0 0 0 1 1 0 1]
[0 0 0 0 1 0 0 0 0 0 0 0 1 1 0]
[0 0 0 0 0 1 0 0 0 1 1 0 1 1 1]
[0 0 0 0 0 0 1 0 0 0 1 1 0 1 1]
[0 0 0 0 0 0 0 1 0 1 1 1 0 0 1]
[0 0 0 0 0 0 0 0 1 1 0 1 0 0 0]

ALGORITHM:

We build the parity check matrix given by the three equations that the codewords must satisfy. Then we generate the parity check matrix over \(\GF{2}\) and from this the obtain the generator matrix for the extended Kasami codes.

For the Kasami codes, we truncate the last column.

parameters()[source]#

Return the parameters \(s,t\) of self.

EXAMPLES:

sage: C = codes.KasamiCode(16, 4, extended=True)
sage: C.parameters()
(16, 4)
sage: D = codes.KasamiCode(16, 4, extended=False)
sage: D.parameters()
(16, 4)
sage: C = codes.KasamiCode(8,2)
sage: C.parameters()
(8, 2)

>>> from sage.all import *
>>> C = codes.KasamiCode(Integer(16), Integer(4), extended=True)
>>> C.parameters()
(16, 4)
>>> D = codes.KasamiCode(Integer(16), Integer(4), extended=False)
>>> D.parameters()
(16, 4)
>>> C = codes.KasamiCode(Integer(8),Integer(2))
>>> C.parameters()
(8, 2)