VERSION: 1.2
Let be a finite field (we denote the finite field with
elements by
).
A subspace of
(with the standard basis) is called a
linear code of length
. If its dimension is denoted
then we typically store a basis of
as a
matrix (the rows are the basis vectors) called
the generator matrix of
. The rows of the parity check
matrix of
are a basis for the code,
called the dual space of .
If then
is called a binary
code. If
then
is called a
-ary code. The elements of a code
are
called codewords.
The symmetric group acts on
by
permuting coordinates. If an element
sends a
code
of length
to itself (in other words,
every codeword of
is sent to some other codeword of
) then
is called a permutation automorphism
of
. The (permutation) automorphism group is denoted
.
This file contains
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:
REFERENCES:
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)
errors in some docstrings.
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
A class for linear codes over a finite field or finite ring. Each
instance is a linear code determined by a generator matrix
(i.e., a k x n matrix of (full) rank
,
over a finite field
.
INPUT:
OUTPUT: The linear code of length over
having
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:
Checks if self == right.
EXAMPLES:
sage: C1 = HammingCode(3,GF(2))
sage: C2 = HammingCode(3,GF(2))
sage: C1 == C2
True
sage: C2 = C1.extended_code()
sage: C3 = C2.punctured([7])
sage: C1 == C3
True
Return an iterator over the elements of this linear code.
EXAMPLES:
sage: C = HammingCode(3,GF(2))
sage: [list(c) for c in C if hamming_weight(c) < 4]
[[0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 1, 0, 1, 0], [1, 1, 0, 0, 0, 0, 1], [0, 0, 1, 1, 0, 0, 1], [0, 1, 1, 0, 0, 1, 0], [0, 0, 0, 0, 1, 1, 1], [0, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 1, 0, 0]]
Assmus and Mattson Theorem (section 8.4, page 303 of [HP]): Let
be the weights of the codewords in
a binary linear
code
, and let
be the weights of the
codewords in its dual
code
. Fix a
,
, and let
Assume .
A block design is a pair , where
is a
non-empty finite set of
elements called points, and
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
points.
design without repeated
blocks is called a simple block design. If every subset of points
of size
is contained in exactly
blocks the block
design is called a
design (or simply a
-design when the parameters are not specified). When
then the block design is called a
Steiner system.
In the Assmus and Mattson Theorem (1), is the set
of coordinate locations and
is the set of supports of the
codewords of
of weight
. Therefore, the
parameters of the
-design for
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 (of course
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 (ie, 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:
This only applies to linear binary codes and returns its
(permutation) automorphism group. In other words, if the code C has
length then it returns the subgroup of the symmetric
group
:
where acts on
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
Returns the i-th binomial moment of the -code
:
where is the dimension of the shortened code
,
. (The normalized
binomial moment is
.) In other
words,
is the 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(3) # long time
0
sage: C.binomial_moment(4) # long time
35
,. warning:
This is slow.
REFERENCE:
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:
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]
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:
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 . 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
Decodes a received vector v (=right) to an element c in the code C (=self). 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). The default is “syndrome”.
INPUT:
OUTPUT: The codeword c in C closest to v.
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.
C1, C2 must be linear codes defined over the same base ring. Returns the (usual vector space) direct sum of the codes.
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
Returns the divisor of a code (the divisor is the smallest integer
such that each
iff
is
divisible by
).
EXAMPLES:
sage: C = ExtendedBinaryGolayCode()
sage: C.divisor() # Type II self-dual
4
sage: C = QuadraticResidueCodeEvenPair(17,GF(2))[0]
sage: C.divisor()
2
This computes the dual code Cd of the code 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
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
satisfies the check condition
. If self is
an
binary code then the extended code
is an
code, where
(if d is even) and
(if
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
If self is a linear code defined over and
is a subfield with Galois group
then this returns the
-module
containing
.
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
Returns the generator matrix of the 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]
Returns the “Duursma genus” of the code, .
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.
Checks if is equal to its Galois closure.
Returns if
is an element of
(
= length of self) and if
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
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
A code C is self-dual if C == C.dual_code() is True.
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
A code C is self-orthogonal if C is a subcode of C.dual_code().
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_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
Returns true if the first is a subcode of the second.
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
Return 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
By default, this uses a GAP kernel function (in C and not part of Guava) written by Steve Linton. If method=”guava” 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).
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
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.
If is an
code over
, this
function computes the subgroup
of all
permutation automorphisms of
. The binary case always
uses the (default) partition refinement method of Robert Miller.
Options: If method=”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 method=”gap+verbose” then code-theoretic data is printed out at several stages of the computation. If method=”partition” then the (default) partition refinement method of Robert Miller is used.
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 .
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”).
Returns the permuted code - the code which is
equivalent to self via the column permutation
.
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
Returns the code punctured at the positions L,
. If C is a code of length n in
GF(q) then the code
obtained from C by puncturing at
the positions in L is the code of length n-L consisting of
codewords of
which have their
coordinate
deleted if
and left alone if
:
where . In particular,
if
then
is simply the code obtained
from
by deleting the
coordinate of each
codeword. The code
is called the punctured code at
. The dimension of
can decrease if
.
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
Returns a random codeword.
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
If C is a linear [n,k,d] code then this function returns a kx(n-k) matrix A such that G = (I,A) generates a code (in standard form) equiv to C. If C is already in standard form and G = (I,A) is its gen mat then this function simply returns that A.
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]
INPUT: The formally s.d. code C and the type number (1,2,3,4) (does not check if C is actually sd)
RETURN: The data v,m as in Duursama [D]
EXAMPLES:
REFERENCES:
INPUT:
RETURN: The coefficients of
as in Duursama [D].
EXAMPLES:
REFERENCES:
Returns the Duursma zeta function of a self-dual code using the construction in [D].
INPUT:
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:
Returns the code shortened at the positions L,
. Consider the subcode
consisting of all codewords
which
satisfy
for all
. The punctured
code
is called the shortened code on
and is denoted
. The code constructed is actually
only isomorphic to the shortened code defined in this way.
By Theorem 1.5.7 in [HP], is
. This is used in the construction
below.
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
The default method (gap) uses a GAP kernel function (in C) written by Steve Linton.
METHOD:
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
An linear code with generator matrix
is
in standard form is the row-reduced echelon form of
is
, where
denotes the
identity matrix and
is a
block. This method returns a pair
where
is a code permutation equivalent to self and
in
(
= length of
) is the
permutation sending self to
. 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)
Returns the set of indices where
is
nonzero, where spectrum(self) =
.
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]
The default method (gap) uses a GAP kernel function (in C) written by Steve Linton.
METHOD:
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
Returns the weight enumerator of the code.
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
Returns the Duursma zeta function of the code.
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)
Returns the Duursma zeta polynomial of the code C.
Assumes C.minimum_distance() 1 and
minimum_distance .
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:
best_known_linear_code 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.
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:
OUTPUT:
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:
The function bounds_minimum_distance calculates a lower and upper bound for the minimum distance of an optimal linear code with word length n, dimension k over 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 (n <= 257), 3 (n <= 243), 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 print bounds_minimum_distance(10,5,GF(2)) for example.
This function requires optional GAP package (Guava).
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:
OUTPUT:
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()
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.
OUTPUT: Returns a minimum weight vector v of the code generated by Gmat ##.
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:
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:
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.
INPUT:
matrix G of a linear code.
n - an integer > 1 representing the number of columns of G (i.e., the length of the linear code).
F - a (Sage) finite field - the base field of the code.
OUTPUT: Returns the 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: