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)

Bases: sage.coding.linear_code.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()
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

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

See also

sage.coding.linear_code.

REFERENCES:

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

generator_matrix()

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]

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()

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)