Linear Codes¶
VERSION: 1.2
Let be a finite field. Here, we will 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, with rows the basis
vectors. It is 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.
Let ,
be linear codes of length
and dimension
. There are
several notions of equivalence for linear codes:
and
are
- permutational equivalent, if there is some permutation
such that
for all
.
- linear equivalent, if there is some permutation
and a vector
of units of length
such that
for all
.
- semilinear equivalent, if there is some permutation
, a vector
of units of length
and a field automorphism
such that
for all
.
These are group actions. If one of these group elements sends
the linear code to itself, then we will call it an automorphism.
Depending on the group action we will call those groups:
- permuation automorphism group
- monomial automorphism group (every linear Hamming isometry is a monomial transformation of the ambient space, for
)
- automorphism group (every semilinear Hamming isometry is a semimonomial transformation of the ambient space, for
)
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,
- generator_matrix, generator_matrix_systematic, information_set, list, parity_check_matrix, 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: is_permutation_automorphism, permutation_automorphism_group, 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 separateguava.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.
Goppa codes and group actions on
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 generator_matrix_systematic, information_set, and magma interface for linear codes.
- Niles Johnson (2010-08): trac ticket ##3893:
random_element()
should pass on*args
and**kwds
. - Thomas Feulner (2012-11): trac ticket #13723: deprecation of
hamming_weight()
- Thomas Feulner (2013-10): added methods to compute a canonical representative and the automorphism group
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.
AbstractLinearCode
(base_field, length)¶ Bases:
sage.modules.module.Module
Abstract class for linear codes.
This class contains all methods that can be used on Linear Codes and on Linear Codes families. So, every Linear Code-related class should inherit from this abstract class.
This class provides:
length
, the length of the code- numerous methods that will work for any linear code (including families)
To implement a linear code, you need to:
- inherit from AbstractLinearCode
- call AbstractLinearCode
__init__
method in the subclass constructor. Example:super(SubclassName, self).__init__(base_field, length)
. By doing that, your subclass will have itslength
parameter initialized and will be properly set as a member of the category framework. You need of course to complete the constructor by adding any additional parameter needed to describe properly the code defined in the subclass. - reimplement
generator_matrix()
method
As AbstractLinearCode is not designed to be implemented, it does not have any representation methods. You should implement
_repr_
and_latex_
methods in the sublclass.Note
AbstractLinearCode embeds some generic implementations of helper methods like
__cmp__
or__eq__
. As they are designed to fit for every linear code, they mostly use the generator matrix and thus can be long for certain families of code. In that case, overriding these methods is encouraged.-
ambient_space
()¶ Returns the ambient vector space of
.
EXAMPLES:
sage: C = codes.HammingCode(3,GF(2)) sage: C.ambient_space() Vector space of dimension 7 over Finite Field of size 2
-
assmus_mattson_designs
(t, mode=None)¶ 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
.
- If
and
then
holds a simple t-design.
- If
and
then
holds a simple t-design.
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 (i.e., the S(5,8,24) Steiner system).
EXAMPLES:
sage: C = codes.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 c.hamming_weight()==8]; len(blocks) # long time computation 759
REFERENCE:
- [HP] W. C. Huffman and V. Pless, Fundamentals of ECC, Cambridge Univ. Press, 2003.
- If
-
automorphism_group_gens
(equivalence='semilinear')¶ Return generators of the automorphism group of
self
.INPUT:
equivalence
(optional) – which defines the acting group, eitherpermutational
linear
semilinear
OUTPUT:
- generators of the automorphism group of
self
- the order of the automorphism group of
self
EXAMPLES:
sage: C = codes.HammingCode(3,GF(4,"z")); sage: C.automorphism_group_gens() ([((1, 1, 1, z, z + 1, z + 1, z + 1, z, z, 1, 1, 1, z, z, z + 1, z, z, z + 1, z + 1, z + 1, 1); (1,6,12,17)(2,16,4,5,11,8,14,13)(3,21,19,10,20,18,15,9), Ring endomorphism of Finite Field in z of size 2^2 Defn: z |--> z + 1), ((1, 1, 1, z, z + 1, 1, 1, z, z, z + 1, z, z, z + 1, z + 1, z + 1, 1, z + 1, z, z, 1, 1); (1,6,9,13,15,18)(2,21)(3,16,7)(4,5,11,10,12,14)(17,19), Ring endomorphism of Finite Field in z of size 2^2 Defn: z |--> z), ((z, z, z, z, z, z, z, z, z, z, z, z, z, z, z, z, z, z, z, z, z); (), Ring endomorphism of Finite Field in z of size 2^2 Defn: z |--> z)], 362880) sage: C.automorphism_group_gens(equivalence="linear") ([((z, z, 1, 1, z + 1, z, z + 1, z, z, z + 1, 1, 1, 1, z + 1, z, z, z + 1, z + 1, 1, 1, z); (1,5,10,9,4,14,11,16,18,20,6,19,12,15,3,8,2,17,7,13,21), Ring endomorphism of Finite Field in z of size 2^2 Defn: z |--> z), ((z + 1, 1, z, 1, 1, z + 1, z + 1, z, 1, z, z + 1, z, z + 1, z + 1, z, 1, 1, z + 1, z + 1, z + 1, z); (1,17,10)(2,15,13)(4,11,21)(5,18,12)(6,14,19)(7,8,16), Ring endomorphism of Finite Field in z of size 2^2 Defn: z |--> z), ((z + 1, z + 1, z + 1, z + 1, z + 1, z + 1, z + 1, z + 1, z + 1, z + 1, z + 1, z + 1, z + 1, z + 1, z + 1, z + 1, z + 1, z + 1, z + 1, z + 1, z + 1); (), Ring endomorphism of Finite Field in z of size 2^2 Defn: z |--> z)], 181440) sage: C.automorphism_group_gens(equivalence="permutational") ([((1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1); (1,11)(3,10)(4,9)(5,7)(12,21)(14,20)(15,19)(16,17), Ring endomorphism of Finite Field in z of size 2^2 Defn: z |--> z), ((1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1); (2,18)(3,19)(4,10)(5,16)(8,13)(9,14)(11,21)(15,20), Ring endomorphism of Finite Field in z of size 2^2 Defn: z |--> z), ((1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1); (1,19)(3,17)(4,21)(5,20)(7,14)(9,12)(10,16)(11,15), Ring endomorphism of Finite Field in z of size 2^2 Defn: z |--> z), ((1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1); (2,13)(3,14)(4,20)(5,11)(8,18)(9,19)(10,15)(16,21), Ring endomorphism of Finite Field in z of size 2^2 Defn: z |--> z)], 64)
-
base_field
()¶ Return the base field of
self
.EXAMPLES:
sage: G = Matrix(GF(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: C = LinearCode(G) sage: C.base_field() Finite Field of size 2
-
basis
()¶ Returns a basis of
.
EXAMPLES:
sage: C = codes.HammingCode(3, GF(2)) sage: C.basis() [(1, 0, 0, 0, 0, 1, 1), (0, 1, 0, 0, 1, 0, 1), (0, 0, 1, 0, 1, 1, 0), (0, 0, 0, 1, 1, 1, 1)]
-
binomial_moment
(i)¶ 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 isomorphic to the subcode of C of codewords supported on S.
EXAMPLES:
sage: C = codes.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.
-
canonical_representative
(equivalence='semilinear')¶ Compute a canonical orbit representative under the action of the semimonomial transformation group.
See
sage.coding.codecan.autgroup_can_label
for more details, for example if you would like to compute a canonical form under some more restrictive notion of equivalence, i.e. if you would like to restrict the permutation group to a Young subgroup.INPUT:
equivalence
(optional) – which defines the acting group, eitherpermutational
linear
semilinear
OUTPUT:
- a canonical representative of
self
- a semimonomial transformation mapping
self
onto its representative
EXAMPLES:
sage: F.<z> = GF(4) sage: C = codes.HammingCode(3,F) sage: CanRep, transp = C.canonical_representative()
Check that the transporter element is correct:
sage: LinearCode(transp*C.generator_matrix()) == CanRep True
Check if an equivalent code has the same canonical representative:
sage: f = F.hom([z**2]) sage: C_iso = LinearCode(C.generator_matrix().apply_map(f)) sage: CanRep_iso, _ = C_iso.canonical_representative() sage: CanRep_iso == CanRep True
Since applying the Frobenius automorphism could be extended to an automorphism of
, the following must also yield
True
:sage: CanRep1, _ = C.canonical_representative("linear") sage: CanRep2, _ = C_iso.canonical_representative("linear") sage: CanRep2 == CanRep1 True
-
cardinality
()¶ Return the size of this code.
EXAMPLES:
sage: C = codes.HammingCode(3, GF(2)) sage: C.cardinality() 16 sage: len(C) 16
-
characteristic
()¶ Returns the characteristic of the base ring of
.
EXAMPLES:
sage: C = codes.HammingCode(3,GF(2)) sage: C.characteristic() 2
-
characteristic_polynomial
()¶ Returns the characteristic polynomial of a linear code, as defined in van Lint’s text [vL].
EXAMPLES:
sage: C = codes.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
(*args, **kwds)¶ Deprecated: Use
parity_check_matrix()
instead. See trac ticket #17973 for details.
-
chinen_polynomial
()¶ Returns the Chinen zeta polynomial of the code.
EXAMPLES:
sage: C = codes.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 = codes.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
is the smallest number
with the property that each element
of the ambient vector space of
has at most a distance
to the code
. So for each vector
there must be an element
of
with
. A binary linear code with reasonable small covering radius is often referred to as a covering code.
For example, if
is a perfect code, the covering radius is equal to
, the number of errors the code can correct, where
, with
the minimum distance of
.
EXAMPLES:
sage: C = codes.HammingCode(5,GF(2)) sage: C.covering_radius() # optional - gap_packages (Guava package) 1
-
decode
(right, algorithm='syndrome')¶ Decodes the received vector
right
to an elementin this code.
Optional algorithms are “guava”, “nearest neighbor” or “syndrome”. The
algorithm="guava"
wraps GUAVA’sDecodeword
. Hamming codes have a special decoding algorithm; otherwise,"syndrome"
decoding is used.INPUT:
right
- Vector of length the length of this codealgorithm
- Algorithm to use, one of"syndrome"
,"nearest neighbor"
, and"guava"
(default:"syndrome"
)
OUTPUT:
- The codeword in this code closest to
right
.
EXAMPLES:
sage: C = codes.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, 1, 0, 1, 0, 0, 1) sage: C.decode(v1,algorithm="nearest neighbor") (1, 1, 0, 1, 0, 0, 1) sage: C.decode(v1,algorithm="guava") # optional - gap_packages (Guava package) (1, 1, 0, 1, 0, 0, 1) sage: v2 = matrix([[a,a,F(0),a,a,F(0),a]]) sage: C.decode(v2) (1, 1, 0, 1, 0, 0, 1) sage: v3 = vector([a,a,F(0),a,a,F(0),a]) sage: c = C.decode(v3); c (1, 1, 0, 1, 0, 0, 1) sage: c in C True sage: C = codes.HammingCode(2,GF(5)) sage: v = vector(GF(5),[1,0,0,2,1,0]) sage: C.decode(v) (1, 0, 0, 2, 2, 0) sage: F.<a> = GF(4) sage: C = codes.HammingCode(2,F) sage: v = vector(F, [1,0,0,a,1]) sage: C.decode(v) (a + 1, 0, 0, a, 1) sage: C.decode(v, algorithm="nearest neighbor") (a + 1, 0, 0, a, 1) sage: C.decode(v, algorithm="guava") # optional - gap_packages (Guava package) (a + 1, 0, 0, a, 1)
Does not work for very long codes since the syndrome table grows too large.
TESTS:
Test that the codeword returned is immutable (see trac ticket #16469):
sage: (C.decode(v)).is_immutable() True
-
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
andother
, which must be linear codes defined over the same base ring.EXAMPLES:
sage: C1 = codes.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
such that each
iff
is divisible by
.
EXAMPLES:
sage: C = codes.ExtendedBinaryGolayCode() sage: C.divisor() # Type II self-dual 4 sage: C = codes.QuadraticResidueCodeEvenPair(17,GF(2))[0] sage: C.divisor() 2
-
dual_code
()¶ This computes the dual code
of the code
,
Does not call GAP.
EXAMPLES:
sage: C = codes.HammingCode(3,GF(2)) sage: C.dual_code() Linear code of length 7, dimension 3 over Finite Field of size 2 sage: C = codes.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 lengthdefined over
then this returns the code of length
where the last digit
satisfies the check condition
. If
self
is anbinary code then the extended code
is an
code, where
(if d is even) and
(if
is odd).
EXAMPLES:
sage: C = codes.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 overand
is a subfield with Galois group
then this returns the
-module
containing
.
EXAMPLES:
sage: C = codes.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()[2] 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_systematic
(*args, **kwds)¶ Deprecated: Use
generator_matrix_systematic()
instead. See trac ticket #17973 for details.
-
generator_matrix
()¶
-
generator_matrix_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.generator_matrix() [1 2 1] [2 1 1] sage: code.generator_matrix_systematic() [1 2 0] [0 0 1]
-
gens
()¶ Returns the generators of this code as a list of vectors.
EXAMPLES:
sage: C = codes.HammingCode(3,GF(2)) sage: C.gens() [(1, 0, 0, 0, 0, 1, 1), (0, 1, 0, 0, 1, 0, 1), (0, 0, 1, 0, 1, 1, 0), (0, 0, 0, 1, 1, 1, 1)]
-
genus
()¶ Returns the “Duursma genus” of the code,
.
EXAMPLES:
sage: C1 = codes.HammingCode(3,GF(2)); C1 Linear code of length 7, dimension 4 over Finite Field of size 2 sage: C1.genus() 1 sage: C2 = codes.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,
.
-
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.generator_matrix_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 = codes.HammingCode(3,GF(4,"a")) sage: C.is_galois_closed() False
-
is_permutation_automorphism
(g)¶ Returns
if
is an element of
(
= length of self) and if
is an automorphism of self.
EXAMPLES:
sage: C = codes.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, algorithm=None)¶ Returns
True
ifself
andother
are permutation equivalent codes andFalse
otherwise.The
algorithm="verbose"
option also returns a permutation (ifTrue
) sendingself
toother
.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 = codes.CyclicCodeFromGeneratingPolynomial(7,g); C1 Linear code of length 7, dimension 4 over Finite Field of size 2 sage: C2 = codes.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,algorithm="verbose") (True, (3,4)(5,7,6)) sage: C1 = codes.RandomLinearCode(10,5,GF(2)) sage: C2 = codes.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) andFalse
otherwise.EXAMPLES:
sage: C = codes.ExtendedBinaryGolayCode() sage: C.is_self_dual() True sage: C = codes.HammingCode(3,GF(2)) sage: C.is_self_dual() False
-
is_self_orthogonal
()¶ Returns
True
if this code is self-orthogonal andFalse
otherwise.A code is self-orthogonal if it is a subcode of its dual.
EXAMPLES:
sage: C = codes.ExtendedBinaryGolayCode() sage: C.is_self_orthogonal() True sage: C = codes.HammingCode(3,GF(2)) sage: C.is_self_orthogonal() False sage: C = codes.QuasiQuadraticResidueCode(11) # optional - gap_packages (Guava package) sage: C.is_self_orthogonal() # optional - gap_packages (Guava package) True
-
is_subcode
(other)¶ Returns
True
ifself
is a subcode ofother
.EXAMPLES:
sage: C1 = codes.HammingCode(3,GF(2)) sage: G1 = C1.generator_matrix() 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 = codes.HammingCode(3,GF(9,"z")) sage: G1 = C1.generator_matrix() 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 = codes.HammingCode(3,GF(2)) sage: C.length() 7
-
list
()¶ Return a list of all elements of this linear code.
EXAMPLES:
sage: C = codes.HammingCode(3,GF(2)) sage: Clist = C.list() sage: Clist[5]; Clist[5] in C (1, 0, 1, 0, 1, 0, 1) True
-
minimum_distance
(algorithm=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
algorithm="guava"
is set andis 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.The minimum distance of the code is stored once it has been computed or provided during the initialization of
LinearCode
. Ifalgorithm
isNone
and the stored value of minimum distance is found, then the stored value will be returned without recomputing the minimum distance again.INPUT:
algorithm
- Method to be used,None
,"gap"
, 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
Once the minimum distance has been computed, it’s value is stored. Hence the following command will return the value instantly, without further computations.:
sage: C.minimum_distance() 3
If
algorithm
is provided, then the minimum distance will be recomputed even if there is a stored value from a previous run.:sage: C.minimum_distance(algorithm="gap") 3 sage: C.minimum_distance(algorithm="guava") # optional - gap_packages (Guava package) 3
Another example.:
sage: C = codes.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
TESTS:
sage: C = codes.HammingCode(2,GF(4,"a")) sage: C.minimum_distance(algorithm='something') Traceback (most recent call last): ... ValueError: The algorithm argument must be one of None, 'gap' or 'guava'; got 'something'
-
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.permutation_automorphism_group()
Now type “C.module_composition_factors(gp)” to get the record printed.
-
parity_check_matrix
()¶ Returns the parity check matrix of
self
.The parity check matrix of a linear code
corresponds to the generator matrix of the dual code of
.
EXAMPLES:
sage: C = codes.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.generator_matrix() [1 0 0 0 0 1 1] [0 1 0 0 1 0 1] [0 0 1 0 1 1 0] [0 0 0 1 1 1 1] sage: C.parity_check_matrix() [1 0 1 0 1 0 1] [0 1 1 0 0 1 1] [0 0 0 1 1 1 1] sage: Cperp.parity_check_matrix() [1 0 0 0 0 1 1] [0 1 0 0 1 0 1] [0 0 1 0 1 1 0] [0 0 0 1 1 1 1] sage: Cperp.generator_matrix() [1 0 1 0 1 0 1] [0 1 1 0 0 1 1] [0 0 0 1 1 1 1]
-
permutation_automorphism_group
(algorithm='partition')¶ If
is an
code over
, this function computes the subgroup
of all permutation automorphisms of
. The binary case always uses the (default) partition refinement algorithm of Robert Miller.
Note that if the base ring of
is
then this is the full automorphism group. Otherwise, you could use
automorphism_group_gens()
to compute generators of the full automorphism group.INPUT:
algorithm
- 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 algorithm of Robert Miller is used. Finally, if"codecan"
then the partition refinement algorithm of Thomas Feulner is used, which also computes a canonical representative ofself
(callcanonical_representative()
to access it).
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 sage: GG = C.permutation_automorphism_group("codecan") sage: GG == G True
A less easy example involves showing that the permutation automorphism group of the extended ternary Golay code is the Mathieu group
.
sage: C = codes.ExtendedTernaryGolayCode() sage: M11 = MathieuGroup(11) sage: M11.order() 7920 sage: G = C.permutation_automorphism_group() # long time (6s on sage.math, 2011) sage: G.is_isomorphic(M11) # long time True sage: GG = C.permutation_automorphism_group("codecan") # long time sage: GG == G # long time True
Other examples:
sage: C = codes.ExtendedBinaryGolayCode() sage: G = C.permutation_automorphism_group() sage: G.order() 244823040 sage: C = codes.HammingCode(5, GF(2)) sage: G = C.permutation_automorphism_group() sage: G.order() 9999360 sage: C = codes.HammingCode(2,GF(3)); C Linear code of length 4, dimension 2 over Finite Field of size 3 sage: C.permutation_automorphism_group(algorithm="partition") Permutation Group with generators [(1,3,4)] sage: C = codes.HammingCode(2,GF(4,"z")); C Linear code of length 5, dimension 3 over Finite Field in z of size 2^2 sage: G = C.permutation_automorphism_group(algorithm="partition"); G Permutation Group with generators [(1,3)(4,5), (1,4)(3,5)] sage: GG = C.permutation_automorphism_group(algorithm="codecan") # long time sage: GG == G # long time True sage: C.permutation_automorphism_group(algorithm="gap") # optional - gap_packages (Guava package) Permutation Group with generators [(1,3)(4,5), (1,4)(3,5)] sage: C = codes.TernaryGolayCode() sage: C.permutation_automorphism_group(algorithm="gap") # optional - gap_packages (Guava package) 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
algorithm="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(algorithm="gap")
.
-
permuted_code
(p)¶ Returns the permuted code, which is equivalent to
self
via the column permutationp
.EXAMPLES:
sage: C = codes.HammingCode(3,GF(2)) sage: G = C.permutation_automorphism_group(); G Permutation Group with generators [(4,5)(6,7), (4,6)(5,7), (2,3)(6,7), (2,4)(3,5), (1,2)(5,6)] sage: g = G("(2,3)(6,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
,
. If this code
is of length
in GF(q) then the code
obtained from
by puncturing at the positions in
is the code of length
consisting of codewords of
which have their
coordinate deleted if
and left alone if
:
where
. In particular, if
then
is simply the code obtainen from
by deleting the
coordinate of each codeword. The code
is called the punctured code at
. The dimension of
can decrease if
.
INPUT:
L
- Subset of, where
is the length of
self
OUTPUT:
- Linear code, the punctured code described above
EXAMPLES:
sage: C = codes.HammingCode(3,GF(2)) sage: C.punctured([1,2]) Linear code of length 5, dimension 4 over Finite Field of size 2
-
random_element
(*args, **kwds)¶ Returns a random codeword; passes other positional and keyword arguments to
random_element()
method of vector space.OUTPUT:
- Random element of the vector space of this code
EXAMPLES:
sage: C = codes.HammingCode(3,GF(4,'a')) sage: C.random_element() # random test (1, 0, 0, a + 1, 1, a, a, a + 1, a + 1, 1, 1, 0, a + 1, a, 0, a, a, 0, a, a, 1)
Passes extra positional or keyword arguments through:
sage: C.random_element(prob=.5, distribution='1/n') # random test (1, 0, a, 0, 0, 0, 0, a + 1, 0, 0, 0, 0, 0, 0, 0, 0, a + 1, a + 1, 1, 0, 0)
TESTS:
Test that the codeword returned is immutable (see trac ticket #16469):
sage: c = C.random_element() sage: c.is_immutable() True
-
redundancy_matrix
(C)¶ If C is a linear [n,k,d] code then this function returns a
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 = codes.HammingCode(3,GF(2)) sage: C.generator_matrix() [1 0 0 0 0 1 1] [0 1 0 0 1 0 1] [0 0 1 0 1 1 0] [0 0 0 1 1 1 1] sage: C.redundancy_matrix() [0 1 1] [1 0 1] [1 1 0] [1 1 1] sage: C.standard_form()[0].generator_matrix() [1 0 0 0 0 1 1] [0 1 0 0 1 0 1] [0 0 1 0 1 1 0] [0 0 0 1 1 1 1] sage: C = codes.HammingCode(2,GF(3)) sage: C.generator_matrix() [1 0 1 1] [0 1 1 2] sage: C.redundancy_matrix() [1 1] [1 2]
-
sd_duursma_data
(C, i)¶ Returns the Duursma data
and
of this formally s.d. code
and the type number
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” EXAMPLES:
sage: MS = MatrixSpace(GF(2),2,4) sage: G = MS([1,1,0,0,0,0,1,1]) sage: C = LinearCode(G) sage: C == C.dual_code() # checks that C is self dual True sage: for i in [1,2,3,4]: print C.sd_duursma_data(i) [2, -1] [2, -3] [2, -2] [2, -1]
-
sd_duursma_q
(C, i, d0)¶ INPUT:
C
- sd code; does not check ifis actually an sd code
i
- Type number, one of 1,2,3,4d0
- Divisor, the smallest integer such that eachiff
is divisible by
OUTPUT:
- Coefficients
of
as in Duursma [D]
REFERENCES:
- [D] - I. Duursma, “Extremal weight enumerators and ultraspherical polynomials”
EXAMPLES:
sage: C1 = codes.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_duursma_q(1,1) 2/5*T^2 + 2/5*T + 1/5 sage: C2.sd_duursma_q(3,1) 3/5*T^4 + 1/5*T^3 + 1/15*T^2 + 1/15*T + 1/15
-
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 = codes.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
.
REFERENCES:
- [D] I. Duursma, “Extremal weight enumerators and ultraspherical polynomials”
-
shortened
(L)¶ Returns the code shortened at the positions
L
, where.
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.
INPUT:
L
- Subset of, where
is the length of this code
OUTPUT:
- Linear code, the shortened code described above
EXAMPLES:
sage: C = codes.HammingCode(3,GF(2)) sage: C.shortened([1,2]) Linear code of length 5, dimension 2 over Finite Field of size 2
-
spectrum
(algorithm=None)¶ Returns the spectrum of
self
as a list.The default algorithm uses a GAP kernel function (in C) written by Steve Linton.
INPUT:
algorithm
-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 algorithm (
"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 algorithm in some small examples and much slower than the GAP algorithm 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 = codes.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 = codes.HammingCode(3,GF(2)); C Linear code of length 7, dimension 4 over Finite Field of size 2 sage: C.spectrum(algorithm="leon") # optional - gap_packages (Guava package) [1, 0, 0, 7, 7, 0, 0, 1] sage: C.spectrum(algorithm="gap") [1, 0, 0, 7, 7, 0, 0, 1] sage: C.spectrum(algorithm="binary") [1, 0, 0, 7, 7, 0, 0, 1] sage: C = codes.HammingCode(3,GF(3)); C Linear code of length 13, dimension 10 over Finite Field of size 3 sage: C.spectrum() == C.spectrum(algorithm="leon") # optional - gap_packages (Guava package) True sage: C = codes.HammingCode(2,GF(5)); C Linear code of length 6, dimension 4 over Finite Field of size 5 sage: C.spectrum() == C.spectrum(algorithm="leon") # optional - gap_packages (Guava package) True sage: C = codes.HammingCode(2,GF(7)); C Linear code of length 8, dimension 6 over Finite Field of size 7 sage: C.spectrum() == C.spectrum(algorithm="leon") # optional - gap_packages (Guava package) True
-
standard_form
()¶ Returns the standard form of this linear code.
An
linear code with generator matrix
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
andin
, with
the 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 = codes.HammingCode(3,GF(2)) sage: C.generator_matrix() [1 0 0 0 0 1 1] [0 1 0 0 1 0 1] [0 0 1 0 1 1 0] [0 0 0 1 1 1 1] sage: Cs,p = C.standard_form() sage: p () 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: Cs, p = C.standard_form() sage: p (3,7) sage: Cs.generator_matrix() [1 0 0 0 1 1 0] [0 1 0 1 0 1 0] [0 0 1 0 0 0 0]
-
support
()¶ Returns the set of indices
where
is nonzero, where spectrum(self) =
.
OUTPUT:
- List of integers
EXAMPLES:
sage: C = codes.HammingCode(3,GF(2)) sage: C.spectrum() [1, 0, 0, 7, 7, 0, 0, 1] sage: C.support() [0, 3, 4, 7]
-
syndrome
(r)¶ Returns the syndrome of
r
.The syndrome of
r
is the result ofwhere
is the parity check matrix of
self
. Ifr
belongs toself
, its syndrome equals to the zero vector.INPUT:
r
– a vector of the same length asself
OUTPUT:
- a column vector
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: r = vector(GF(2), (1,0,1,0,1,0,1)) sage: r in C True sage: C.syndrome(r) (0, 0, 0)
If
r
is not a codeword, its syndrome is not equal to zero:sage: r = vector(GF(2), (1,0,1,0,1,1,1)) sage: r in C False sage: C.syndrome(r) (0, 1, 1)
Syndrome computation works fine on bigger fields:
sage: C = codes.RandomLinearCode(12, 4, GF(59)) sage: r = C.random_element() sage: C.syndrome(r) (0, 0, 0, 0, 0, 0, 0, 0)
-
weight_distribution
(algorithm=None)¶ Returns the spectrum of
self
as a list.The default algorithm uses a GAP kernel function (in C) written by Steve Linton.
INPUT:
algorithm
-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 algorithm (
"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 algorithm in some small examples and much slower than the GAP algorithm 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 = codes.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 = codes.HammingCode(3,GF(2)); C Linear code of length 7, dimension 4 over Finite Field of size 2 sage: C.spectrum(algorithm="leon") # optional - gap_packages (Guava package) [1, 0, 0, 7, 7, 0, 0, 1] sage: C.spectrum(algorithm="gap") [1, 0, 0, 7, 7, 0, 0, 1] sage: C.spectrum(algorithm="binary") [1, 0, 0, 7, 7, 0, 0, 1] sage: C = codes.HammingCode(3,GF(3)); C Linear code of length 13, dimension 10 over Finite Field of size 3 sage: C.spectrum() == C.spectrum(algorithm="leon") # optional - gap_packages (Guava package) True sage: C = codes.HammingCode(2,GF(5)); C Linear code of length 6, dimension 4 over Finite Field of size 5 sage: C.spectrum() == C.spectrum(algorithm="leon") # optional - gap_packages (Guava package) True sage: C = codes.HammingCode(2,GF(7)); C Linear code of length 8, dimension 6 over Finite Field of size 7 sage: C.spectrum() == C.spectrum(algorithm="leon") # optional - gap_packages (Guava package) True
-
weight_enumerator
(names='xy', name2=None)¶ Returns the weight enumerator of the code.
INPUT:
names
- String of length 2, containing two variable names (default:"xy"
). Alternatively, it can be a variable name or a string, or a tuple of variable names or strings.name2
- string or symbolic variable (default:None
). Ifname2
is provided then it is assumed thatnames
contains only one variable.
OUTPUT:
- Polynomial over
EXAMPLES:
sage: C = codes.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 sage: (var1, var2) = var('var1, var2') sage: C.weight_enumerator((var1, var2)) var1^7 + 7*var1^4*var2^3 + 7*var1^3*var2^4 + var2^7 sage: C.weight_enumerator(var1, var2) var1^7 + 7*var1^4*var2^3 + 7*var1^3*var2^4 + var2^7
-
zero
()¶ Return the zero vector.
EXAMPLES:
sage: C = codes.HammingCode(3, GF(2)) sage: C.zero() (0, 0, 0, 0, 0, 0, 0) sage: C.sum(()) # indirect doctest (0, 0, 0, 0, 0, 0, 0) sage: C.sum((C.gens())) # indirect doctest (1, 1, 1, 1, 1, 1, 1)
-
zeta_function
(name='T')¶ Returns the Duursma zeta function of the code.
INPUT:
name
- String, variable name (default:"T"
)
OUTPUT:
- Element of
EXAMPLES:
sage: C = codes.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
EXAMPLES:
sage: C = codes.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)) # optional - gap_packages (Guava package) sage: C.minimum_distance() # optional - gap_packages (Guava package) 3 sage: C.zeta_polynomial() # optional - gap_packages (Guava package) 2/5*T^2 + 2/5*T + 1/5 sage: C = codes.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.
-
class
sage.coding.linear_code.
LinearCode
(generator_matrix, d=None)¶ Bases:
sage.coding.linear_code.AbstractLinearCode
Linear codes over a finite field or finite ring, represented using a generator matrix.
This class should be used for arbitrary and unstructured linear codes. This means that basic operations on the code, such as the computation of the minimum distance, will use generic, slow algorithms.
If you are looking for constructing a code from a more specific family, see if the family has been implemented by investigating codes.<tab>. These more specific classes use properties particular for that family to allow faster algorithms, and could also have family-specific methods.
See Wikipedia article Linear_code for more information on unstructured linear codes.
INPUT:
generator_matrix
– a generator matrix over a finite field (G
can be defined over a finite ring but the matrices over that ring must have certain attributes, such asrank
)d
– (optional, default:None
) the minimum distance of the code
Note
The veracity of the minimum distance
d
, if provided, is not checked.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]
The minimum distance of the code, if known, can be provided as an optional parameter.:
sage: C = LinearCode(G, d=3) sage: C.minimum_distance() 3
Another example.:
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)
-
gen_mat
(*args, **kwds)¶ Deprecated: Use
generator_matrix()
instead. See trac ticket #17973 for details.
-
generator_matrix
()¶ Return a generator matrix of this code.
EXAMPLES:
sage: G = matrix(GF(3),2,[1,-1,1,-1,1,1]) sage: code = LinearCode(G) sage: code.generator_matrix() [1 2 1] [2 1 1]
-
sage.coding.linear_code.
LinearCodeFromVectorSpace
(V, d=None)¶ Simply converts a vector subspace
of
into a
.
INPUT:
V
– The vector spaced
– (Optional, default:None
) the minimum distance of the code, if known. This is an optional parameter.
Note
The veracity of the minimum distance
d
, if provided, is not checked.EXAMPLES:
sage: V = VectorSpace(GF(2), 8) sage: L = V.subspace([[1,1,1,1,0,0,0,0],[0,0,0,0,1,1,1,1]]) sage: C = LinearCodeFromVectorSpace(L) sage: C.generator_matrix() [1 1 1 1 0 0 0 0] [0 0 0 0 1 1 1 1] sage: C.minimum_distance() 4
Here, we provide the minimum distance of the code.:
sage: C = LinearCodeFromVectorSpace(L, d=4) sage: C.minimum_distance() 4
-
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
, dimensionk
over fieldF
. The function uses the tables described inbounds_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; optional - gap_packages (Guava package) Linear code of length 10, dimension 5 over Finite Field of size 2 sage: gap.eval("C:=BestKnownLinearCode(10,5,GF(2))") # long time; optional - gap_packages (Guava package) '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))
orprint 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 codek
- Integer, the dimension of the codeF
- Finite field, of order 2, 3, 4, 5, 7, 8, or 9verbose
- Bool (default:False
)
OUTPUT:
- Text about why the bounds are as given
EXAMPLES:
sage: L = best_known_linear_code_www(72, 36, GF(2)) # optional - internet sage: print L # optional - internet 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 aValueError
if theq
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 dimensionk
over the fieldF
.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.codetables.de/ or use the Sage function
minimum_distance_why
for the most recent data.) These tables contain lower and upper bounds for(when
n <= 257
),(when
n <= 243
),(
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).
EXAMPLES:
sage: print bounds_minimum_distance(10,5,GF(2)) # optional - gap_packages (Guava package) rec( construction := [ <Operation "ShortenedCode">, [ [ <Operation "UUVCode">, [ [ <Operation "DualCode">, [ [ <Operation "RepetitionCode">, [ 8, 2 ] ] ] ], [ <Operation "UUVCode">, [ [ <Operation "DualCode">, [ [ <Operation "RepetitionCode">, [ 4, 2 ] ] ] ] , [ <Operation "RepetitionCode">, [ 4, 2 ] ] ] ] ] ], [ 1, 2, 3, 4, 5, 6 ] ] ], k := 5, lowerBound := 4, lowerBoundExplanation := ... n := 10, q := 2, references := rec( ), upperBound := 4, upperBoundExplanation := ... )
-
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 = codes.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,0,0,1,1, 0,1,0,0,1,0,1, 0,0,1,0,1,1,0, 0,0,0,1,1,1,1 )); FINISH; sage: f.close()
-
sage.coding.linear_code.
min_wt_vec_gap
(Gmat, n, k, F, algorithm=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
algorithm="guava"
requires Guava. The default algorithm 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
such that
, 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),algorithm="guava") # optional - gap_packages (Guava package) (0, 0, 1, 0, 1, 1, 0)
Here
Gstr
is a generator matrix of the Hamming [7,4,3] binary code.TESTS:
We check that trac ticket #18480 is fixed:
sage: codes.HammingCode(2, GF(2)).minimum_distance() 3
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 lengthk
- Integer, maximal dimensionb
- Integer, requires that the generators all have weight divisible byb
(ifb=2
, all self-orthogonal codes are generated, and ifb=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
- IfTrue
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.generator_matrix() ... 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.generator_matrix() 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.generator_matrix() 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)) Traceback (most recent call last): ... 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 coden
- 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)