Linear Codes¶

VERSION: 1.2

Let $F$ be a finite field. Here, we will denote the finite field with $q$ elements by $\GF{q}$ . A subspace of $F^n$ (with the standard basis) is called a linear code of length $n$ . If its dimension is denoted $k$ then we typically store a basis of $C$ as a $k \times n$ matrix, with rows the basis vectors. It is called the generator matrix of $C$ . The rows of the parity check matrix of $C$ are a basis for the code,

$C^* = \{ v \in GF(q)^n\ |\ v\cdot c = 0,\ for \ all\ c \in C \},$

called the dual space of $C$ .

If $F=\GF{2}$ then $C$ is called a binary code. If $F = \GF{q}$ then $C$ is called a $q$ -ary code. The elements of a code $C$ are called codewords.

The symmetric group $S_n$ acts on $F^n$ by permuting coordinates. If an element $p \in S_n$ sends a code $C$ of length $n$ to itself (in other words, every codeword of $C$ is sent to some other codeword of $C$ ) then $p$ is called a permutation automorphism of $C$ . The (permutation) automorphism group is denoted $Aut(C)$ .

This file contains

LinearCode class definition; LinearCodeFromVectorspace conversion function,
The spectrum (weight distribution), covering_radius, minimum distance programs (calling Steve Linton’s or CJ Tjhal’s C programs), characteristic_function, and several implementations of the Duursma zeta function (sd_zeta_polynomial, zeta_polynomial, zeta_function, chinen_polynomial, for example),
interface with best_known_linear_code_www (interface with codetables.de since A. Brouwer’s online tables have been disabled), bounds_minimum_distance which call tables in GUAVA (updated May 2006) created by Cen Tjhai instead of the online internet tables,
gen_mat, gen_mat_systematic, information_set, list, check_mat, decode, dual_code, extended_code, shortened, punctured, genus, binomial_moment, and divisor methods for LinearCode,
Boolean-valued functions such as “==”, is_self_dual, is_self_orthogonal, is_subcode, is_permutation_automorphism, is_permutation_equivalent (which interfaces with Robert Miller’s partition refinement code),
permutation methods: automorphism_group_binary_code, is_permutation_automorphism, (permutation_automorphism_group is deprecated), permuted_code, standard_form, module_composition_factors,
design-theoretic methods: assmus_mattson_designs (implementing Assmus-Mattson Theorem),
code constructions, such as HammingCode and ToricCode, are in a separate code_constructions.py module; in the separate guava.py module, you will find constructions, such as RandomLinearCodeGuava and BinaryReedMullerCode, wrapped from the corresponding GUAVA codes.

EXAMPLES:

sage: MS = MatrixSpace(GF(2),4,7)
sage: G = MS([[1,1,1,0,0,0,0], [1,0,0,1,1,0,0], [0,1,0,1,0,1,0], [1,1,0,1,0,0,1]])
sage: C = LinearCode(G)
sage: C.basis()
[(1, 1, 1, 0, 0, 0, 0),
 (1, 0, 0, 1, 1, 0, 0),
 (0, 1, 0, 1, 0, 1, 0),
 (1, 1, 0, 1, 0, 0, 1)]
sage: c = C.basis()[1]
sage: c in C
True
sage: c.nonzero_positions()
[0, 3, 4]
sage: c.support()
[0, 3, 4]
sage: c.parent()
Vector space of dimension 7 over Finite Field of size 2

To be added:

More wrappers
GRS codes and special decoders.
$P^1$ Goppa codes and group actions on $P^1$ RR space codes.

REFERENCES:

[HP] W. C. Huffman and V. Pless, Fundamentals of error-correcting codes, Cambridge Univ. Press, 2003.
[Gu] GUAVA manual, http://www.gap-system.org/Packages/guava.html

AUTHORS:

David Joyner (2005-11-22, 2006-12-03): initial version
William Stein (2006-01-23): Inclusion in Sage
David Joyner (2006-01-30, 2006-04): small fixes
David Joyner (2006-07): added documentation, group-theoretical methods, ToricCode
David Joyner (2006-08): hopeful latex fixes to documentation, added list and __iter__ methods to LinearCode and examples, added hamming_weight function, fixed random method to return a vector, TrivialCode, fixed subtle bug in dual_code, added galois_closure method, fixed mysterious bug in permutation_automorphism_group (GAP was over-using “G” somehow?)
David Joyner (2006-08): hopeful latex fixes to documentation, added CyclicCode, best_known_linear_code, bounds_minimum_distance, assmus_mattson_designs (implementing Assmus-Mattson Theorem).
David Joyner (2006-09): modified decode syntax, fixed bug in is_galois_closed, added LinearCode_from_vectorspace, extended_code, zeta_function
Nick Alexander (2006-12-10): factor GUAVA code to guava.py
David Joyner (2007-05): added methods punctured, shortened, divisor, characteristic_polynomial, binomial_moment, support for LinearCode. Completely rewritten zeta_function (old version is now zeta_function2) and a new function, LinearCodeFromVectorSpace.
David Joyner (2007-11): added zeta_polynomial, weight_enumerator, chinen_polynomial; improved best_known_code; made some pythonic revisions; added is_equivalent (for binary codes)
David Joyner (2008-01): fixed bug in decode reported by Harald Schilly, (with Mike Hansen) added some doctests.
David Joyner (2008-02): translated standard_form, dual_code to Python.
David Joyner (2008-03): translated punctured, shortened, extended_code, random (and renamed random to random_element), deleted zeta_function2, zeta_function3, added wrapper automorphism_group_binary_code to Robert Miller’s code), added direct_sum_code, is_subcode, is_self_dual, is_self_orthogonal, redundancy_matrix, did some alphabetical reorganizing to make the file more readable. Fixed a bug in permutation_automorphism_group which caused it to crash.
David Joyner (2008-03): fixed bugs in spectrum and zeta_polynomial, which misbehaved over non-prime base rings.
David Joyner (2008-10): use CJ Tjhal’s MinimumWeight if char = 2 or 3 for min_dist; add is_permutation_equivalent and improve permutation_automorphism_group using an interface with Robert Miller’s code; added interface with Leon’s code for the spectrum method.
David Joyner (2009-02): added native decoding methods (see module_decoder.py)
David Joyner (2009-05): removed dependence on Guava, allowing it to be an option. Fixed errors in some docstrings.
Kwankyu Lee (2010-01): added methods gen_mat_systematic, information_set, and magma interface for linear codes.

TESTS:

sage: MS = MatrixSpace(GF(2),4,7)
sage: G  = MS([[1,1,1,0,0,0,0], [1,0,0,1,1,0,0], [0,1,0,1,0,1,0], [1,1,0,1,0,0,1]])
sage: C  = LinearCode(G)
sage: C == loads(dumps(C))
True

class sage.coding.linear_code.LinearCode(gen_mat)¶

Bases: sage.modules.module.Module

A class for linear codes over a finite field or finite ring. Each instance is a linear code determined by a generator matrix $G$ (i.e., a $k \times n$ matrix of (full) rank $k$ , $k \leq n$ over a finite field $F$ .

INPUT:

G - a generator matrix over $F$ . (G can be defined over a finite ring but the matrices over that ring must have certain attributes, such as rank.)

OUTPUT:

The linear code of length $n$ over $F$ having $G$ as a generator matrix.

EXAMPLES:

sage: MS = MatrixSpace(GF(2),4,7)
sage: G  = MS([[1,1,1,0,0,0,0], [1,0,0,1,1,0,0], [0,1,0,1,0,1,0], [1,1,0,1,0,0,1]])
sage: C  = LinearCode(G)
sage: C
Linear code of length 7, dimension 4 over Finite Field of size 2
sage: C.base_ring()
Finite Field of size 2
sage: C.dimension()
4
sage: C.length()
7
sage: C.minimum_distance()
3
sage: C.spectrum()
[1, 0, 0, 7, 7, 0, 0, 1]
sage: C.weight_distribution()
[1, 0, 0, 7, 7, 0, 0, 1]
sage: MS = MatrixSpace(GF(5),4,7)
sage: G  = MS([[1,1,1,0,0,0,0], [1,0,0,1,1,0,0], [0,1,0,1,0,1,0], [1,1,0,1,0,0,1]])
sage: C  = LinearCode(G)
sage: C
Linear code of length 7, dimension 4 over Finite Field of size 5

AUTHORS:

David Joyner (11-2005)

ambient_space()¶

assmus_mattson_designs(t, mode=None)¶

Assmus and Mattson Theorem (section 8.4, page 303 of [HP]): Let $A_0, A_1, ..., A_n$ be the weights of the codewords in a binary linear $[n , k, d]$ code $C$ , and let $A_0^*, A_1^*, ..., A_n^*$ be the weights of the codewords in its dual $[n, n-k, d^*]$ code $C^*$ . Fix a $t$ , $0<t<d$ , and let

$s = |\{ i\ |\ A_i^* \not= 0, 0< i \leq n-t\}|.$

Assume $s\leq d-t$ .

If $A_i\not= 0$ and $d\leq i\leq n$ then $C_i = \{ c \in C\ |\ wt(c) = i\}$ holds a simple t-design.
If $A_i^*\not= 0$ and $d*\leq i\leq n-t$ then $C_i^* = \{ c \in C^*\ |\ wt(c) = i\}$ holds a simple t-design.

A block design is a pair $(X,B)$ , where $X$ is a non-empty finite set of $v>0$ elements called points, and $B$ is a non-empty finite multiset of size b whose elements are called blocks, such that each block is a non-empty finite multiset of $k$ points. $A$ design without repeated blocks is called a simple block design. If every subset of points of size $t$ is contained in exactly $\lambda$ blocks the block design is called a $t-(v,k,\lambda)$ design (or simply a $t$ -design when the parameters are not specified). When $\lambda=1$ then the block design is called a $S(t,k,v)$ Steiner system.

In the Assmus and Mattson Theorem (1), $X$ is the set $\{1,2,...,n\}$ of coordinate locations and $B = \{supp(c)\ |\ c \in C_i\}$ is the set of supports of the codewords of $C$ of weight $i$ . Therefore, the parameters of the $t$ -design for $C_i$ are

t =       given
v =       n
k =       i   (k not to be confused with dim(C))
b =       Ai
lambda = b*binomial(k,t)/binomial(v,t) (by Theorem 8.1.6,
                                           p 294, in [HP])

Setting the mode="verbose" option prints out the values of the parameters.

The first example below means that the binary [24,12,8]-code C has the property that the (support of the) codewords of weight 8 (resp., 12, 16) form a 5-design. Similarly for its dual code $C^*$ (of course $C=C^*$ in this case, so this info is extraneous). The test fails to produce 6-designs (ie, the hypotheses of the theorem fail to hold, not that the 6-designs definitely don’t exist). The command assmus_mattson_designs(C,5,mode=”verbose”) returns the same value but prints out more detailed information.

The second example below illustrates the blocks of the 5-(24, 8, 1) design (i.e., the S(5,8,24) Steiner system).

EXAMPLES:

sage: C = ExtendedBinaryGolayCode()             #  example 1
sage: C.assmus_mattson_designs(5)
['weights from C: ',
[8, 12, 16, 24],
'designs from C: ',
[[5, (24, 8, 1)], [5, (24, 12, 48)], [5, (24, 16, 78)], [5, (24, 24, 1)]],
'weights from C*: ',
[8, 12, 16],
'designs from C*: ',
[[5, (24, 8, 1)], [5, (24, 12, 48)], [5, (24, 16, 78)]]]
sage: C.assmus_mattson_designs(6)
0 
sage: X = range(24)                           #  example 2
sage: blocks = [c.support() for c in C if hamming_weight(c)==8]; len(blocks)  # long time computation
759

REFERENCE:

[HP] W. C. Huffman and V. Pless, Fundamentals of ECC, Cambridge Univ. Press, 2003.

automorphism_group_binary_code()¶

This only applies to linear binary codes and returns its (permutation) automorphism group. In other words, if the code $C$ has length $n$ then it returns the subgroup of the symmetric group $S_n$ :

$\{ g \in S_n\ |\ g(c) \in C, \forall c\in C\},$

where $S_n$ acts on $GF(2)^n$ by permuting coordinates.

EXAMPLES:

sage: C = HammingCode(3,GF(2))
sage: G = C.automorphism_group_binary_code(); G
Permutation Group with generators [(3,4)(5,6), (3,5)(4,6), (2,3)(5,7), (1,2)(5,6)]
sage: G.order()
168

basis()¶

binomial_moment(i)¶

Returns the i-th binomial moment of the $[n,k,d]_q$ -code $C$ :

$B_i(C) = \sum_{S, |S|=i} \frac{q^{k_S}-1}{q-1}$

where $k_S$ is the dimension of the shortened code $C_{J-S}$ , $J=[1,2,...,n]$ . (The normalized binomial moment is $b_i(C) = \binom(n,d+i)^{-1}B_{d+i}(C)$ .) In other words, $C_{J-S}$ is isomorphic to the subcode of C of codewords supported on S.

EXAMPLES:

sage: C = HammingCode(3,GF(2))
sage: C.binomial_moment(2)
0
sage: C.binomial_moment(4)    # long time
35

Warning

This is slow.

REFERENCE:

I. Duursma, “Combinatorics of the two-variable zeta function”, Finite fields and applications, 109-136, Lecture Notes in Comput. Sci., 2948, Springer, Berlin, 2004.

characteristic()¶

characteristic_polynomial()¶

Returns the characteristic polynomial of a linear code, as defined in van Lint’s text [vL].

EXAMPLES:

sage: C = ExtendedBinaryGolayCode()
sage: C.characteristic_polynomial()
-4/3*x^3 + 64*x^2 - 2816/3*x + 4096

REFERENCES:

van Lint, Introduction to coding theory, 3rd ed., Springer-Verlag GTM, 86, 1999.

check_mat()¶

Returns the check matrix of self.

EXAMPLES:

sage: C = HammingCode(3,GF(2))
sage: Cperp = C.dual_code()
sage: C; Cperp
Linear code of length 7, dimension 4 over Finite Field of size 2
Linear code of length 7, dimension 3 over Finite Field of size 2
sage: C.gen_mat()
[1 0 0 1 0 1 0]
[0 1 0 1 0 1 1]
[0 0 1 1 0 0 1]
[0 0 0 0 1 1 1]
sage: C.check_mat()
[1 0 0 1 1 0 1]
[0 1 0 1 0 1 1]
[0 0 1 1 1 1 0]
sage: Cperp.check_mat()
[1 0 0 1 0 1 0]
[0 1 0 1 0 1 1]
[0 0 1 1 0 0 1]
[0 0 0 0 1 1 1]
sage: Cperp.gen_mat()
[1 0 0 1 1 0 1]
[0 1 0 1 0 1 1]
[0 0 1 1 1 1 0]

chinen_polynomial()¶

Returns the Chinen zeta polynomial of the code.

EXAMPLES:

sage: C = HammingCode(3,GF(2))
sage: C.chinen_polynomial()       # long time
1/5*(2*sqrt(2)*t^3 + 2*sqrt(2)*t^2 + 2*t^2 + sqrt(2)*t + 2*t + 1)/(sqrt(2) + 1)
sage: C = TernaryGolayCode()
sage: C.chinen_polynomial()       # long time
1/7*(3*sqrt(3)*t^3 + 3*sqrt(3)*t^2 + 3*t^2 + sqrt(3)*t + 3*t + 1)/(sqrt(3) + 1)

This last output agrees with the corresponding example given in Chinen’s paper below.

REFERENCES:

Chinen, K. “An abundance of invariant polynomials satisfying the Riemann hypothesis”, April 2007 preprint.

covering_radius()¶

Wraps Guava’s CoveringRadius command.

The covering radius of a linear code $C$ is the smallest number $r$ with the property that each element $v$ of the ambient vector space of $C$ has at most a distance $r$ to the code $C$ . So for each vector $v$ there must be an element $c$ of $C$ with $d(v,c) \leq r$ . A binary linear code with reasonable small covering radius is often referred to as a covering code.

For example, if $C$ is a perfect code, the covering radius is equal to $t$ , the number of errors the code can correct, where $d = 2t+1$ , with $d$ the minimum distance of $C$ .

EXAMPLES:

sage: C = HammingCode(5,GF(2))
sage: C.covering_radius()  # requires optional GAP package Guava
1

decode(right, method='syndrome')¶

Decodes the received vector right to an element $c$ in this code.

Optional methods are “guava”, “nearest neighbor” or “syndrome”. The method="guava" wraps GUAVA’s Decodeword. Hamming codes have a special decoding algorithm; otherwise, "syndrome" decoding is used.

INPUT:

right - Vector of length the length of this code
method - Method, one of "syndrome", "nearest neighbor", and "guava" (default: "syndrome")

OUTPUT:

The codeword in this code closest to right.

EXAMPLES:

sage: C = HammingCode(3,GF(2))
sage: MS = MatrixSpace(GF(2),1,7)
sage: F = GF(2); a = F.gen()
sage: v1 = [a,a,F(0),a,a,F(0),a]
sage: C.decode(v1)
(1, 0, 0, 1, 1, 0, 1)
sage: C.decode(v1,method="nearest neighbor")
(1, 0, 0, 1, 1, 0, 1)
sage: C.decode(v1,method="guava")  # requires optional GAP package Guava
(1, 0, 0, 1, 1, 0, 1)
sage: v2 = matrix([[a,a,F(0),a,a,F(0),a]])
sage: C.decode(v2)
(1, 0, 0, 1, 1, 0, 1)
sage: v3 = vector([a,a,F(0),a,a,F(0),a])
sage: c = C.decode(v3); c
(1, 0, 0, 1, 1, 0, 1)
sage: c in C
True
sage: C = HammingCode(2,GF(5))
sage: v = vector(GF(5),[1,0,0,2,1,0])
sage: C.decode(v) 
(2, 0, 0, 2, 1, 0)
sage: F = GF(4,"a")
sage: C = HammingCode(2,F)
sage: v = vector(F, [1,0,0,a,1])
sage: C.decode(v)
(1, 0, 0, 1, 1)
sage: C.decode(v, method="nearest neighbor")
(1, 0, 0, 1, 1)
sage: C.decode(v, method="guava")  # requires optional GAP package Guava
(1, 0, 0, 1, 1)

Does not work for very long codes since the syndrome table grows too large.

dimension()¶

Returns the dimension of this code.

EXAMPLES:

sage: G = matrix(GF(2),[[1,0,0],[1,1,0]])
sage: C = LinearCode(G)
sage: C.dimension()
2

direct_sum(other)¶

Returns the code given by the direct sum of the codes self and other, which must be linear codes defined over the same base ring.

EXAMPLES:

sage: C1 = HammingCode(3,GF(2))
sage: C2 = C1.direct_sum(C1); C2
Linear code of length 14, dimension 8 over Finite Field of size 2
sage: C3 = C1.direct_sum(C2); C3
Linear code of length 21, dimension 12 over Finite Field of size 2

divisor()¶

Returns the divisor of a code, which is the smallest integer $d_0 > 0$ such that each $A_i > 0$ iff $i$ is divisible by $d_0$ .

EXAMPLES:

sage: C = ExtendedBinaryGolayCode()
sage: C.divisor()   # Type II self-dual
4
sage: C = QuadraticResidueCodeEvenPair(17,GF(2))[0]
sage: C.divisor() 
2

dual_code()¶

This computes the dual code $Cd$ of the code $C$ ,

$Cd = \{ v \in V\ |\ v\cdot c = 0,\ \forall c \in C \}.$

Does not call GAP.

EXAMPLES:

sage: C = HammingCode(3,GF(2))
sage: C.dual_code()
Linear code of length 7, dimension 3 over Finite Field of size 2
sage: C = HammingCode(3,GF(4,'a'))
sage: C.dual_code()
Linear code of length 21, dimension 3 over Finite Field in a of size 2^2

extended_code()¶

If self is a linear code of length $n$ defined over $F$ then this returns the code of length $n+1$ where the last digit $c_n$ satisfies the check condition $c_0+...+c_n=0$ . If self is an $[n,k,d]$ binary code then the extended code $C^{\vee}$ is an $[n+1,k,d^{\vee}]$ code, where $d^=d$ (if d is even) and $d^{\vee}=d+1$ (if $d$ is odd).

EXAMPLES:

sage: C = HammingCode(3,GF(4,'a'))
sage: C
Linear code of length 21, dimension 18 over Finite Field in a of size 2^2
sage: Cx = C.extended_code()
sage: Cx
Linear code of length 22, dimension 18 over Finite Field in a of size 2^2

galois_closure(F0)¶

If self is a linear code defined over $F$ and $F_0$ is a subfield with Galois group $G = Gal(F/F_0)$ then this returns the $G$ -module $C^-$ containing $C$ .

EXAMPLES:

sage: C = HammingCode(3,GF(4,'a'))
sage: Cc = C.galois_closure(GF(2))
sage: C; Cc
Linear code of length 21, dimension 18 over Finite Field in a of size 2^2
Linear code of length 21, dimension 20 over Finite Field in a of size 2^2
sage: c = C.basis()[1]
sage: V = VectorSpace(GF(4,'a'),21)
sage: c2 = V([x^2 for x in c.list()])
sage: c2 in C
False
sage: c2 in Cc
True

gen_mat()¶

Return a generator matrix of this code.

EXAMPLES:

sage: C1 = HammingCode(3,GF(2))
sage: C1.gen_mat()
[1 0 0 1 0 1 0]
[0 1 0 1 0 1 1]
[0 0 1 1 0 0 1]
[0 0 0 0 1 1 1]
sage: C2 = HammingCode(2,GF(4,"a"))
sage: C2.gen_mat()
[    1     0     0     1     1]
[    0     1     0     1 a + 1]
[    0     0     1     1     a]

gen_mat_systematic()¶

Return a systematic generator matrix of the code.

A generator matrix of a code is called systematic if it contains a set of columns forming an identity matrix.

EXAMPLES:

sage: G = matrix(GF(3),2,[1,-1,1,-1,1,1])
sage: code = LinearCode(G)
sage: code.gen_mat()
[1 2 1]
[2 1 1]
sage: code.gen_mat_systematic()
[1 2 0]
[0 0 1]

gens()¶

Returns the generators of this code as a list of vectors.

EXAMPLES:

sage: C = HammingCode(3,GF(2))
sage: C.gens()
[(1, 0, 0, 1, 0, 1, 0), (0, 1, 0, 1, 0, 1, 1), (0, 0, 1, 1, 0, 0, 1), (0, 0, 0, 0, 1, 1, 1)]

genus()¶

Returns the “Duursma genus” of the code, $\gamma_C = n+1-k-d$ .

EXAMPLES:

sage: C1 = HammingCode(3,GF(2)); C1
Linear code of length 7, dimension 4 over Finite Field of size 2
sage: C1.genus()
1
sage: C2 = HammingCode(2,GF(4,"a")); C2
Linear code of length 5, dimension 3 over Finite Field in a of size 2^2
sage: C2.genus()
0

Since all Hamming codes have minimum distance 3, these computations agree with the definition, $n+1-k-d$ .

information_set()¶

Return an information set of the code.

A set of column positions of a generator matrix of a code is called an information set if the corresponding columns form a square matrix of full rank.

OUTPUT:

Information set of a systematic generator matrix of the code.

EXAMPLES:

sage: G = matrix(GF(3),2,[1,-1,0,-1,1,1])
sage: code = LinearCode(G)
sage: code.gen_mat_systematic()
[1 2 0]
[0 0 1]
sage: code.information_set()
[0, 2]

is_galois_closed()¶

Checks if self is equal to its Galois closure.

EXAMPLES:

sage: C = HammingCode(3,GF(4,"a"))
sage: C.is_galois_closed()
False

is_permutation_automorphism(g)¶

Returns $1$ if $g$ is an element of $S_n$ ( $n$ = length of self) and if $g$ is an automorphism of self.

EXAMPLES:

sage: C = HammingCode(3,GF(3))
sage: g = SymmetricGroup(13).random_element()
sage: C.is_permutation_automorphism(g)
0
sage: MS = MatrixSpace(GF(2),4,8)
sage: G  = MS([[1,0,0,0,1,1,1,0],[0,1,1,1,0,0,0,0],[0,0,0,0,0,0,0,1],[0,0,0,0,0,1,0,0]])
sage: C  = LinearCode(G)
sage: S8 = SymmetricGroup(8)
sage: g = S8("(2,3)")
sage: C.is_permutation_automorphism(g)
1 
sage: g = S8("(1,2,3,4)")
sage: C.is_permutation_automorphism(g)
0

is_permutation_equivalent(other, method=None)¶

Returns True if self and other are permutation equivalent codes and False otherwise.

The method="verbose" option also returns a permutation (if True) sending self to other.

Uses Robert Miller’s double coset partition refinement work.

EXAMPLES:

sage: P.<x> = PolynomialRing(GF(2),"x")
sage: g = x^3+x+1
sage: C1 = CyclicCodeFromGeneratingPolynomial(7,g); C1
Linear code of length 7, dimension 4 over Finite Field of size 2
sage: C2 = HammingCode(3,GF(2)); C2
Linear code of length 7, dimension 4 over Finite Field of size 2
sage: C1.is_permutation_equivalent(C2)
True
sage: C1.is_permutation_equivalent(C2,method="verbose")
(True, (4,6,5,7))
sage: C1 = RandomLinearCode(10,5,GF(2))
sage: C2 = RandomLinearCode(10,5,GF(3))
sage: C1.is_permutation_equivalent(C2)
False

is_self_dual()¶

Returns True if the code is self-dual (in the usual Hamming inner product) and False otherwise.

EXAMPLES:

sage: C = ExtendedBinaryGolayCode()
sage: C.is_self_dual()
True
sage: C = HammingCode(3,GF(2))
sage: C.is_self_dual()
False

is_self_orthogonal()¶

Returns True if this code is self-orthogonal and False otherwise.

A code is self-orthogonal if it is a subcode of its dual.

EXAMPLES:

sage: C = ExtendedBinaryGolayCode()
sage: C.is_self_orthogonal()
True
sage: C = HammingCode(3,GF(2))
sage: C.is_self_orthogonal()
False
sage: C = QuasiQuadraticResidueCode(11)  # requires optional GAP package Guava
sage: C.is_self_orthogonal()             # requires optional GAP package Guava
True

is_subcode(other)¶

Returns True if self is a subcode of other.

EXAMPLES:

sage: C1 = HammingCode(3,GF(2))
sage: G1 = C1.gen_mat()
sage: G2 = G1.matrix_from_rows([0,1,2])
sage: C2 = LinearCode(G2)
sage: C2.is_subcode(C1)
True
sage: C1.is_subcode(C2)
False
sage: C3 = C1.extended_code()
sage: C1.is_subcode(C3)
False
sage: C4 = C1.punctured([1])
sage: C4.is_subcode(C1)
False
sage: C5 = C1.shortened([1])
sage: C5.is_subcode(C1)
False
sage: C1 = HammingCode(3,GF(9,"z"))
sage: G1 = C1.gen_mat()
sage: G2 = G1.matrix_from_rows([0,1,2])
sage: C2 = LinearCode(G2)
sage: C2.is_subcode(C1)
True

length()¶

Returns the length of this code.

EXAMPLES:

sage: C = HammingCode(3,GF(2))
sage: C.length()
7

list()¶

Return a list of all elements of this linear code.

EXAMPLES:

sage: C = HammingCode(3,GF(2))
sage: Clist = C.list()
sage: Clist[5]; Clist[5] in C
(1, 0, 1, 0, 0, 1, 1)
True

minimum_distance(method=None)¶

Returns the minimum distance of this linear code.

By default, this uses a GAP kernel function (in C and not part of Guava) written by Steve Linton. If method="guava" is set and $q$ is 2 or 3 then this uses a very fast program written in C written by CJ Tjhal. (This is much faster, except in some small examples.)

Raises a ValueError in case there is no non-zero vector in this linear code.

INPUT:

method - Method to be used, None or "guava" (default: None)

OUTPUT:

Integer, minimum distance of this code

EXAMPLES:

sage: MS = MatrixSpace(GF(3),4,7)
sage: G = MS([[1,1,1,0,0,0,0], [1,0,0,1,1,0,0], [0,1,0,1,0,1,0], [1,1,0,1,0,0,1]])
sage: C = LinearCode(G)
sage: C.minimum_distance()
3
sage: C.minimum_distance(method="guava")  # requires optional GAP package Guava
3
sage: C = HammingCode(2,GF(4,"a")); C
Linear code of length 5, dimension 3 over Finite Field in a of size 2^2
sage: C.minimum_distance()
3

This shows that trac ticket #6486 has been resolved:

sage: G = matrix(GF(2),[[0,0,0]])
sage: C = LinearCode(G)
sage: C.minimum_distance()
...
ValueError: this linear code contains no non-zero vector

module_composition_factors(gp)¶

Prints the GAP record of the Meataxe composition factors module in Meataxe notation. This uses GAP but not Guava.

EXAMPLES:

sage: MS = MatrixSpace(GF(2),4,8)
sage: G  = MS([[1,0,0,0,1,1,1,0],[0,1,1,1,0,0,0,0],[0,0,0,0,0,0,0,1],[0,0,0,0,0,1,0,0]])
sage: C  = LinearCode(G)
sage: gp = C.automorphism_group_binary_code()   

Now type “C.module_composition_factors(gp)” to get the record printed.

permutation_automorphism_group(method='partition')¶

If $C$ is an $[n,k,d]$ code over $F$ , this function computes the subgroup $Aut(C) \subset S_n$ of all permutation automorphisms of $C$ . The binary case always uses the (default) partition refinement method of Robert Miller.

INPUT:

method - If "gap" then GAP’s MatrixAutomorphism function (written by Thomas Breuer) is used. The implementation combines an idea of mine with an improvement suggested by Cary Huffman. If "gap+verbose" then code-theoretic data is printed out at several stages of the computation. If "partition" then the (default) partition refinement method of Robert Miller is used.

OUTPUT:

Permutation automorphism group

EXAMPLES:

sage: MS = MatrixSpace(GF(2),4,8)
sage: G  = MS([[1,0,0,0,1,1,1,0],[0,1,1,1,0,0,0,0],[0,0,0,0,0,0,0,1],[0,0,0,0,0,1,0,0]])
sage: C  = LinearCode(G)
sage: C
Linear code of length 8, dimension 4 over Finite Field of size 2
sage: G = C.permutation_automorphism_group()  
sage: G.order()                               
144

A less easy example involves showing that the permutation automorphism group of the extended ternary Golay code is the Mathieu group $M_{11}$ .

sage: C = ExtendedTernaryGolayCode()
sage: M11 = MathieuGroup(11)
sage: M11.order()
7920
sage: G = C.permutation_automorphism_group()  # this should take < 5 seconds  
sage: G.is_isomorphic(M11)                    # this should take < 5 seconds  
True

In the binary case, uses sage.coding.binary_code:

sage: C = ExtendedBinaryGolayCode()
sage: G = C.permutation_automorphism_group()
sage: G.order()
244823040

In the non-binary case:

sage: C = HammingCode(2,GF(3)); C
Linear code of length 4, dimension 2 over Finite Field of size 3
sage: C.permutation_automorphism_group(method="partition")
Permutation Group with generators [(1,2,3)]
sage: C = HammingCode(2,GF(4,"z")); C
Linear code of length 5, dimension 3 over Finite Field in z of size 2^2
sage: C.permutation_automorphism_group(method="partition")
Permutation Group with generators [(1,2)(3,4), (1,3)(2,4)]
sage: C.permutation_automorphism_group(method="gap")  # requires optional GAP package Guava
Permutation Group with generators [(1,2)(3,4), (1,3)(2,4)]
sage: C = TernaryGolayCode()
sage: C.permutation_automorphism_group(method="gap")  # requires optional GAP package Guava
Permutation Group with generators [(3,4)(5,7)(6,9)(8,11), (3,5,8)(4,11,7)(6,9,10), (2,3)(4,6)(5,8)(7,10), (1,2)(4,11)(5,8)(9,10)]

However, the option method="gap+verbose", will print out:

Minimum distance: 5 Weight distribution: [1, 0, 0, 0, 0, 132, 132,
0, 330, 110, 0, 24]

Using the 132 codewords of weight 5 Supergroup size: 39916800

in addition to the output of C.permutation_automorphism_group(method="gap").

permuted_code(p)¶

Returns the permuted code, which is equivalent to self via the column permutation p.

EXAMPLES:

sage: C = HammingCode(3,GF(2))
sage: G = C.automorphism_group_binary_code(); G
Permutation Group with generators [(3,4)(5,6), (3,5)(4,6), (2,3)(5,7), (1,2)(5,6)]
sage: g = G("(2,3)(5,7)")
sage: Cg = C.permuted_code(g)
sage: Cg
Linear code of length 7, dimension 4 over Finite Field of size 2
sage: C == Cg
True

punctured(L)¶

Returns the code punctured at the positions $L$ , $L \subset \{1,2,...,n\}$ . If this code $C$ is of length $n$ in GF(q) then the code $C^L$ obtained from $C$ by puncturing at the positions in $L$ is the code of length $n-L$ consisting of codewords of $C$ which have their $i-th$ coordinate deleted if $i \in L$ and left alone if $i\notin L$ :

$C^L = \{(c_{i_1},...,c_{i_N})\ |\ (c_1,...,c_n)\in C\},$

where $\{1,2,...,n\}-T = \{i_1,...,i_N\}$ . In particular, if $L=\{j\}$ then $C^L$ is simply the code obtainen from $C$ by deleting the $j-th$ coordinate of each codeword. The code $C^L$ is called the punctured code at $L$ . The dimension of $C^L$ can decrease if $|L|>d-1$ .

INPUT:

L - Subset of $\{1,...,n\}$ , where $n$ is the length of self

OUTPUT:

Linear code, the punctured code described above

EXAMPLES:

sage: C = HammingCode(3,GF(2))
sage: C.punctured([1,2])
Linear code of length 5, dimension 4 over Finite Field of size 2

random_element()¶

Returns a random codeword.

OUTPUT:

Random element of the vector space of this code

EXAMPLES:

sage: C = HammingCode(3,GF(4,'a'))
sage: Cc = C.galois_closure(GF(2))
sage: c = C.gen_mat()[1]
sage: V = VectorSpace(GF(4,'a'),21)
sage: c2 = V([x^2 for x in c.list()])
sage: c2 in C
False
sage: c2 in Cc
True

redundancy_matrix(C)¶

If C is a linear [n,k,d] code then this function returns a $k imes (n-k)$ matrix A such that G = (I,A) generates a code (in standard form) equivalent to C. If C is already in standard form and G = (I,A) is its generator matrix then this function simply returns that A.

OUTPUT:

Matrix, the redundancy matrix

EXAMPLES:

sage: C = HammingCode(3,GF(2))
sage: C.gen_mat()
[1 0 0 1 0 1 0]
[0 1 0 1 0 1 1]
[0 0 1 1 0 0 1]
[0 0 0 0 1 1 1]
sage: C.redundancy_matrix()
[1 1 0]
[1 1 1]
[1 0 1]
[0 1 1]
sage: C.standard_form()[0].gen_mat()
[1 0 0 0 1 1 0]
[0 1 0 0 1 1 1]
[0 0 1 0 1 0 1]
[0 0 0 1 0 1 1]
sage: C = HammingCode(2,GF(3))
sage: C.gen_mat()
[1 0 2 2]
[0 1 2 1]
sage: C.redundancy_matrix()
[2 2]
[2 1]

sd_duursma_data(C, i)¶

Returns the Duursma data $v$ and $m$ of this formally s.d. code $C$ and the type number $i$ in (1,2,3,4). Does not check if this code is actually sd.

INPUT:

i - Type number

OUTPUT:

Pair (v, m) as in Duursma [D]

REFERENCES:

[D]	(1, 2, 3) I. Duursma, “Extremal weight enumerators and ultraspherical polynomials”

sd_duursma_q(C, i, d0)¶

INPUT:

C - sd code; does not check if $C$ is actually an sd code
i - Type number, one of 1,2,3,4
d0 - Divisor, the smallest integer such that each $A_i > 0$ iff $i$ is divisible by $d0$

OUTPUT:

Coefficients $q_0, q_1, ...$ of $q(T)$ as in Duursma [D]

REFERENCES:

[D] - I. Duursma, “Extremal weight enumerators and ultraspherical polynomials”

sd_zeta_polynomial(C, typ=1)¶

Returns the Duursma zeta function of a self-dual code using the construction in [D].

INPUT:

typ - Integer, type of this s.d. code; one of 1,2,3, or 4 (default: 1)

OUTPUT:

Polynomial

EXAMPLES:

sage: C1 = HammingCode(3,GF(2))
sage: C2 = C1.extended_code(); C2
Linear code of length 8, dimension 4 over Finite Field of size 2
sage: C2.is_self_dual()
True
sage: C2.sd_zeta_polynomial()
2/5*T^2 + 2/5*T + 1/5
sage: C2.zeta_polynomial()
2/5*T^2 + 2/5*T + 1/5
sage: P = C2.sd_zeta_polynomial(); P(1)
1
sage: F.<z> = GF(4,"z")
sage: MS = MatrixSpace(F, 3, 6)
sage: G = MS([[1,0,0,1,z,z],[0,1,0,z,1,z],[0,0,1,z,z,1]])
sage: C = LinearCode(G)  # the "hexacode"
sage: C.sd_zeta_polynomial(4)
1

It is a general fact about Duursma zeta polynomials that $P(1) = 1$ .

REFERENCES:

[D] I. Duursma, “Extremal weight enumerators and ultraspherical polynomials”

shortened(L)¶

Returns the code shortened at the positions L, where $L \subset \{1,2,...,n\}$ .

Consider the subcode $C(L)$ consisting of all codewords $c\in C$ which satisfy $c_i=0$ for all $i\in L$ . The punctured code $C(L)^L$ is called the shortened code on $L$ and is denoted $C_L$ . The code constructed is actually only isomorphic to the shortened code defined in this way.

By Theorem 1.5.7 in [HP], $C_L$ is $((C^\perp)^L)^\perp$ . This is used in the construction below.

INPUT:

L - Subset of $\{1,...,n\}$ , where $n$ is the length of this code

OUTPUT:

Linear code, the shortened code described above

EXAMPLES:

sage: C = HammingCode(3,GF(2))
sage: C.shortened([1,2])
Linear code of length 5, dimension 2 over Finite Field of size 2

spectrum(method=None)¶

Returns the spectrum of self as a list.

The default method uses a GAP kernel function (in C) written by Steve Linton.

INPUT:

method - None, "gap", "leon", or "binary"; defaults to "gap" except in the binary case. If "gap" then uses the GAP function, if "leon" then uses Jeffrey Leon’s software via Guava, and if "binary" then uses Sage native Cython code
List, the spectrum

The optional method ("leon") may create a stack smashing error and a traceback but should return the correct answer. It appears to run much faster than the GAP method in some small examples and much slower than the GAP method in other larger examples.

EXAMPLES:

sage: MS = MatrixSpace(GF(2),4,7)
sage: G = MS([[1,1,1,0,0,0,0],[1,0,0,1,1,0,0],[0,1,0,1,0,1,0],[1,1,0,1,0,0,1]])
sage: C = LinearCode(G)
sage: C.spectrum()
[1, 0, 0, 7, 7, 0, 0, 1]
sage: F.<z> = GF(2^2,"z")
sage: C = HammingCode(2, F); C
Linear code of length 5, dimension 3 over Finite Field in z of size 2^2
sage: C.spectrum()
[1, 0, 0, 30, 15, 18]
sage: C = HammingCode(3,GF(2)); C
Linear code of length 7, dimension 4 over Finite Field of size 2
sage: C.spectrum(method="leon")   # requires optional GAP package Guava
[1, 0, 0, 7, 7, 0, 0, 1]
sage: C.spectrum(method="gap")
[1, 0, 0, 7, 7, 0, 0, 1]
sage: C.spectrum(method="binary")
[1, 0, 0, 7, 7, 0, 0, 1]
sage: C = HammingCode(3,GF(3)); C
Linear code of length 13, dimension 10 over Finite Field of size 3
sage: C.spectrum() == C.spectrum(method="leon")   # requires optional GAP package Guava
True
sage: C = HammingCode(2,GF(5)); C
Linear code of length 6, dimension 4 over Finite Field of size 5
sage: C.spectrum() == C.spectrum(method="leon")   # requires optional GAP package Guava
True
sage: C = HammingCode(2,GF(7)); C
Linear code of length 8, dimension 6 over Finite Field of size 7
sage: C.spectrum() == C.spectrum(method="leon")   # requires optional GAP package Guava
True

standard_form()¶

Returns the standard form of this linear code.

An $[n,k]$ linear code with generator matrix $G$ in standard form is the row-reduced echelon form of $G$ is $(I,A)$ , where $I$ denotes the $k \times k$ identity matrix and $A$ is a $k \times (n-k)$ block. This method returns a pair $(C,p)$ where $C$ is a code permutation equivalent to self and $p$ in $S_n$ , with $n$ the length of $C$ , is the permutation sending self to $C$ . This does not call GAP.

Thanks to Frank Luebeck for (the GAP version of) this code.

EXAMPLES:

sage: C = HammingCode(3,GF(2))
sage: C.gen_mat()
[1 0 0 1 0 1 0]
[0 1 0 1 0 1 1]
[0 0 1 1 0 0 1]
[0 0 0 0 1 1 1]
sage: Cs,p = C.standard_form()
sage: p
(4,5)
sage: Cs
Linear code of length 7, dimension 4 over Finite Field of size 2
sage: Cs.gen_mat()
[1 0 0 0 1 1 0]
[0 1 0 0 1 1 1]
[0 0 1 0 1 0 1]
[0 0 0 1 0 1 1]
sage: MS = MatrixSpace(GF(3),3,7)
sage: G = MS([[1,0,0,0,1,1,0],[0,1,0,1,0,1,0],[0,0,0,0,0,0,1]])
sage: C = LinearCode(G)
sage: G; C.standard_form()[0].gen_mat()
[1 0 0 0 1 1 0]
[0 1 0 1 0 1 0]
[0 0 0 0 0 0 1]
[1 0 0 0 1 1 0]
[0 1 0 1 0 1 0]
[0 0 1 0 0 0 0]
sage: C.standard_form()[1]
(3,7)

support()¶

Returns the set of indices $j$ where $A_j$ is nonzero, where spectrum(self) = $[A_0,A_1,...,A_n]$ .

OUTPUT:

List of integers

EXAMPLES:

sage: C = HammingCode(3,GF(2))
sage: C.spectrum()
[1, 0, 0, 7, 7, 0, 0, 1] 
sage: C.support()
[0, 3, 4, 7]

weight_distribution(method=None)¶

Returns the spectrum of self as a list.

The default method uses a GAP kernel function (in C) written by Steve Linton.

INPUT:

method - None, "gap", "leon", or "binary"; defaults to "gap" except in the binary case. If "gap" then uses the GAP function, if "leon" then uses Jeffrey Leon’s software via Guava, and if "binary" then uses Sage native Cython code
List, the spectrum

The optional method ("leon") may create a stack smashing error and a traceback but should return the correct answer. It appears to run much faster than the GAP method in some small examples and much slower than the GAP method in other larger examples.

EXAMPLES:

sage: MS = MatrixSpace(GF(2),4,7)
sage: G = MS([[1,1,1,0,0,0,0],[1,0,0,1,1,0,0],[0,1,0,1,0,1,0],[1,1,0,1,0,0,1]])
sage: C = LinearCode(G)
sage: C.spectrum()
[1, 0, 0, 7, 7, 0, 0, 1]
sage: F.<z> = GF(2^2,"z")
sage: C = HammingCode(2, F); C
Linear code of length 5, dimension 3 over Finite Field in z of size 2^2
sage: C.spectrum()
[1, 0, 0, 30, 15, 18]
sage: C = HammingCode(3,GF(2)); C
Linear code of length 7, dimension 4 over Finite Field of size 2
sage: C.spectrum(method="leon")   # requires optional GAP package Guava
[1, 0, 0, 7, 7, 0, 0, 1]
sage: C.spectrum(method="gap")
[1, 0, 0, 7, 7, 0, 0, 1]
sage: C.spectrum(method="binary")
[1, 0, 0, 7, 7, 0, 0, 1]
sage: C = HammingCode(3,GF(3)); C
Linear code of length 13, dimension 10 over Finite Field of size 3
sage: C.spectrum() == C.spectrum(method="leon")   # requires optional GAP package Guava
True
sage: C = HammingCode(2,GF(5)); C
Linear code of length 6, dimension 4 over Finite Field of size 5
sage: C.spectrum() == C.spectrum(method="leon")   # requires optional GAP package Guava
True
sage: C = HammingCode(2,GF(7)); C
Linear code of length 8, dimension 6 over Finite Field of size 7
sage: C.spectrum() == C.spectrum(method="leon")   # requires optional GAP package Guava
True

weight_enumerator(names='xy')¶

Returns the weight enumerator of the code.

INPUT:

names - String of length 2, containing two variable names (default: "xy")

OUTPUT:

Polynomial over $\QQ$

EXAMPLES:

sage: C = HammingCode(3,GF(2))
sage: C.weight_enumerator()
x^7 + 7*x^4*y^3 + 7*x^3*y^4 + y^7
sage: C.weight_enumerator(names="st")
s^7 + 7*s^4*t^3 + 7*s^3*t^4 + t^7

zeta_function(name='T')¶

Returns the Duursma zeta function of the code.

INPUT:

name - String, variable name (default: "T")

OUTPUT:

Element of $\QQ(T)$

EXAMPLES:

sage: C = HammingCode(3,GF(2))
sage: C.zeta_function() 
(2/5*T^2 + 2/5*T + 1/5)/(2*T^2 - 3*T + 1)

zeta_polynomial(name='T')¶

Returns the Duursma zeta polynomial of this code.

Assumes that the minimum distances of this code and its dual are greater than 1. Prints a warning to stdout otherwise.

INPUT:

name - String, variable name (default: "T")

OUTPUT:

Polynomial over $\QQ$

EXAMPLES:

sage: C = HammingCode(3,GF(2))
sage: C.zeta_polynomial()
2/5*T^2 + 2/5*T + 1/5
sage: C = best_known_linear_code(6,3,GF(2))  # requires optional GAP package Guava            
sage: C.minimum_distance()                   # requires optional GAP package Guava       
3
sage: C.zeta_polynomial()                    # requires optional GAP package Guava              
2/5*T^2 + 2/5*T + 1/5
sage: C = HammingCode(4,GF(2))
sage: C.zeta_polynomial()
16/429*T^6 + 16/143*T^5 + 80/429*T^4 + 32/143*T^3 + 30/143*T^2 + 2/13*T + 1/13
sage: F.<z> = GF(4,"z")
sage: MS = MatrixSpace(F, 3, 6)
sage: G = MS([[1,0,0,1,z,z],[0,1,0,z,1,z],[0,0,1,z,z,1]])
sage: C = LinearCode(G)  # the "hexacode"
sage: C.zeta_polynomial()
1

REFERENCES:

I. Duursma, “From weight enumerators to zeta functions”, in Discrete Applied Mathematics, vol. 111, no. 1-2, pp. 55-73, 2001.

sage.coding.linear_code.LinearCodeFromVectorSpace(self)¶: Simply converts a vector subspace $V$ of $GF(q)^n$ into a $LinearCode$ .

sage.coding.linear_code.best_known_linear_code(n, k, F)¶

Returns the best known (as of 11 May 2006) linear code of length n, dimension k over field F. The function uses the tables described in bounds_minimum_distance to construct this code.

This does not require an internet connection.

EXAMPLES:

sage: best_known_linear_code(10,5,GF(2))    # long time and requires optional GAP package Guava
Linear code of length 10, dimension 5 over Finite Field of size 2
sage: gap.eval("C:=BestKnownLinearCode(10,5,GF(2))")     # long time and requires optional GAP package Guava
'a linear [10,5,4]2..4 shortened code'

This means that best possible binary linear code of length 10 and dimension 5 is a code with minimum distance 4 and covering radius somewhere between 2 and 4. Use minimum_distance_why(10,5,GF(2)) or print bounds_minimum_distance(10,5,GF(2)) for further details.

sage.coding.linear_code.best_known_linear_code_www(n, k, F, verbose=False)¶

Explains the construction of the best known linear code over GF(q) with length n and dimension k, courtesy of the www page http://www.codetables.de/.

INPUT:

n - Integer, the length of the code
k - Integer, the dimension of the code
F - Finite field, of order 2, 3, 4, 5, 7, 8, or 9
verbose - Bool (default: False)

OUTPUT:

Text about why the bounds are as given

EXAMPLES:

sage: L = best_known_linear_code_www(72, 36, GF(2)) # requires internet, optional
sage: print L                                       # requires internet, optional  
Construction of a linear code
[72,36,15] over GF(2):
[1]:  [73, 36, 16] Cyclic Linear Code over GF(2)
     CyclicCode of length 73 with generating polynomial x^37 + x^36 + x^34 +
x^33 + x^32 + x^27 + x^25 + x^24 + x^22 + x^21 + x^19 + x^18 + x^15 + x^11 +
x^10 + x^8 + x^7 + x^5 + x^3 + 1
[2]:  [72, 36, 15] Linear Code over GF(2)
     Puncturing of [1] at 1
last modified: 2002-03-20

This function raises an IOError if an error occurs downloading data or parsing it. It raises a ValueError if the q input is invalid.

AUTHORS:

Steven Sivek (2005-11-14)
David Joyner (2008-03)

sage.coding.linear_code.bounds_minimum_distance(n, k, F)¶

Calculates a lower and upper bound for the minimum distance of an optimal linear code with word length n and dimension k over the field F.

The function returns a record with the two bounds and an explanation for each bound. The function Display can be used to show the explanations.

The values for the lower and upper bound are obtained from a table constructed by Cen Tjhai for GUAVA, derived from the table of Brouwer. (See http://www.win.tue.nl/ aeb/voorlincod.html or use the Sage function minimum_distance_why for the most recent data.) These tables contain lower and upper bounds for $q=2$ (when n <= 257), $q=3$ (when n <= 243), $q=4$ (n <= 256). (Current as of 11 May 2006.) For codes over other fields and for larger word lengths, trivial bounds are used.

This does not require an internet connection. The format of the output is a little non-intuitive. Try bounds_minimum_distance(10,5,GF(2)) for an example.

This function requires optional GAP package (Guava).

sage.coding.linear_code.code2leon(C)¶

Writes a file in Sage’s temp directory representing the code C, returning the absolute path to the file. This is the Sage translation of the GuavaToLeon command in Guava’s codefun.gi file.

INPUT:

C - a linear code (over GF(p), p < 11)

OUTPUT:

Absolute path to the file written

EXAMPLES:

sage: C = HammingCode(3,GF(2)); C
Linear code of length 7, dimension 4 over Finite Field of size 2
sage: file_loc = sage.coding.linear_code.code2leon(C)
sage: f = open(file_loc); print f.read()
LIBRARY code;
code=seq(2,4,7,seq(
1,0,0,1,0,1,0,
0,1,0,1,0,1,1,
0,0,1,1,0,0,1,
0,0,0,0,1,1,1
));
FINISH;
sage: f.close()

sage.coding.linear_code.hamming_weight(v)¶

Returns the Hamming weight of the vector v, which is the number of non-zero entries.

INPUT:

v - Vector

OUTPUT:

Integer, the Hamming weight of v

EXAMPLES:

sage: hamming_weight(vector(GF(2),[0,0,1]))
1
sage: hamming_weight(vector(GF(2),[0,0,0]))
0

sage.coding.linear_code.min_wt_vec_gap(Gmat, n, k, F, method=None)¶

Returns a minimum weight vector of the code generated by Gmat.

Uses C programs written by Steve Linton in the kernel of GAP, so is fairly fast. The option method="guava" requires Guava. The default method requires GAP but not Guava.

INPUT:

Gmat - String representing a GAP generator matrix G of a linear code
n - Length of the code generated by G
k - Dimension of the code generated by G
F - Base field

OUTPUT:

Minimum weight vector of the code generated by Gmat

REMARKS:

The code in the default case allows one (for free) to also compute the message vector $m$ such that $m\*G = v$ , and the (minimum) distance, as a triple. however, this output is not implemented.
The binary case can presumably be done much faster using Robert Miller’s code (see the docstring for the spectrum method). This is also not (yet) implemented.

EXAMPLES:

sage: Gstr = "Z(2)*[[1,1,1,0,0,0,0], [1,0,0,1,1,0,0], [0,1,0,1,0,1,0], [1,1,0,1,0,0,1]]"
sage: sage.coding.linear_code.min_wt_vec_gap(Gstr,7,4,GF(2)) 
(0, 1, 0, 1, 0, 1, 0)

This output is different but still a minimum weight vector:

sage: sage.coding.linear_code.min_wt_vec_gap(Gstr,7,4,GF(2),method="guava")    # requires optional GAP package Guava
(0, 0, 1, 0, 1, 1, 0)

Here Gstr is a generator matrix of the Hamming [7,4,3] binary code.

AUTHORS:

David Joyner (11-2005)

sage.coding.linear_code.self_orthogonal_binary_codes(n, k, b=2, parent=None, BC=None, equal=False, in_test=None)¶

Returns a Python iterator which generates a complete set of representatives of all permutation equivalence classes of self-orthogonal binary linear codes of length in [1..n] and dimension in [1..k].

INPUT:

n - Integer, maximal length
k - Integer, maximal dimension
b - Integer, requires that the generators all have weight divisible by b (if b=2, all self-orthogonal codes are generated, and if b=4, all doubly even codes are generated). Must be an even positive integer.
parent - Used in recursion (default: None)
BC - Used in recursion (default: None)
equal - If True generates only [n, k] codes (default: False)
in_test - Used in recursion (default: None)

EXAMPLES:

Generate all self-orthogonal codes of length up to 7 and dimension up to 3:

sage: for B in self_orthogonal_binary_codes(7,3):
...    print B
...
Linear code of length 2, dimension 1 over Finite Field of size 2
Linear code of length 4, dimension 2 over Finite Field of size 2
Linear code of length 6, dimension 3 over Finite Field of size 2
Linear code of length 4, dimension 1 over Finite Field of size 2
Linear code of length 6, dimension 2 over Finite Field of size 2
Linear code of length 6, dimension 2 over Finite Field of size 2
Linear code of length 7, dimension 3 over Finite Field of size 2
Linear code of length 6, dimension 1 over Finite Field of size 2

Generate all doubly-even codes of length up to 7 and dimension up to 3:

sage: for B in self_orthogonal_binary_codes(7,3,4):
...    print B; print B.gen_mat()
...
Linear code of length 4, dimension 1 over Finite Field of size 2
[1 1 1 1]
Linear code of length 6, dimension 2 over Finite Field of size 2
[1 1 1 1 0 0]
[0 1 0 1 1 1]
Linear code of length 7, dimension 3 over Finite Field of size 2
[1 0 1 1 0 1 0]
[0 1 0 1 1 1 0]
[0 0 1 0 1 1 1]

Generate all doubly-even codes of length up to 7 and dimension up to 2:

sage: for B in self_orthogonal_binary_codes(7,2,4):
...    print B; print B.gen_mat()
Linear code of length 4, dimension 1 over Finite Field of size 2
[1 1 1 1]
Linear code of length 6, dimension 2 over Finite Field of size 2
[1 1 1 1 0 0]
[0 1 0 1 1 1]

Generate all self-orthogonal codes of length equal to 8 and dimension equal to 4:

sage: for B in self_orthogonal_binary_codes(8, 4, equal=True):
...     print B; print B.gen_mat()
Linear code of length 8, dimension 4 over Finite Field of size 2
[1 0 0 1 0 0 0 0]
[0 1 0 0 1 0 0 0]
[0 0 1 0 0 1 0 0]
[0 0 0 0 0 0 1 1]
Linear code of length 8, dimension 4 over Finite Field of size 2
[1 0 0 1 1 0 1 0]
[0 1 0 1 1 1 0 0]
[0 0 1 0 1 1 1 0]
[0 0 0 1 0 1 1 1]

Since all the codes will be self-orthogonal, b must be divisible by 2:

sage: list(self_orthogonal_binary_codes(8, 4, 1, equal=True))
...
ValueError: b (1) must be a positive even integer.

sage.coding.linear_code.wtdist_gap(Gmat, n, F)¶

INPUT:

Gmat - String representing a GAP generator matrix G of a linear code
n - Integer greater than 1, representing the number of columns of G (i.e., the length of the linear code)
F - Finite field (in Sage), base field the code

OUTPUT:

Spectrum of the associated code

EXAMPLES:

sage: Gstr = 'Z(2)*[[1,1,1,0,0,0,0], [1,0,0,1,1,0,0], [0,1,0,1,0,1,0], [1,1,0,1,0,0,1]]'
sage: F = GF(2)
sage: sage.coding.linear_code.wtdist_gap(Gstr, 7, F)
[1, 0, 0, 7, 7, 0, 0, 1]

Here Gstr is a generator matrix of the Hamming [7,4,3] binary code.

ALGORITHM:

Uses C programs written by Steve Linton in the kernel of GAP, so is fairly fast.

AUTHORS:

David Joyner (2005-11)

Linear Codes¶

Previous topic

Next topic

This Page

Navigation

Linear Codes¶

Previous topic

Next topic

This Page

Quick search

Navigation