Module: sage.coding.linear_code
Linear Codes
VERSION: 0.11
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
code_constructions.py
module; in the separate guava.py
module,
you will find constructions, such as RandomLinearCodeGuava and
BinaryReedMullerCode, wrapped from the corresponding GUAVA codes.
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: [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
Author Log:
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
Module-level Functions
self) |
Simply converts a vector subspace V of
into a LinearCode.
n, k, F) |
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.
sage: best_known_linear_code(10,5,GF(2)) # long time Linear code of length 10, dimension 5 over Finite Field of size 2 sage: gap.eval("C:=BestKnownLinearCode(10,5,GF(2))") # long time '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.
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:
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.
Author: (2005-11-14) Steven Sivek, (2008-03) modified by David Joyner
n, k, F) |
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.
v) |
Gmat, F) |
Uses C programs written by Steve Linton in the kernel of GAP, so is fairly fast.
Input: Same as wtdist.
Output: Returns a minimum weight vector v of the code generated by Gmat ## , the"message" vector m such that m*G = v, and the (minimum) distance, as a triple.
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(Gstr,GF(2)) (0, 0, 1, 0, 1, 1, 0)
Here Gstr is a generator matrix of the Hamming [7,4,3] binary code.
Author: David Joyner (11-2005)
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:
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)) Traceback (most recent call last): ... ValueError: b (1) must be a positive even integer.
Gmat, F) |
Input:
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(Gstr, 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.
Author: David Joyner (2005-11)
Class: LinearCode
Input:
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
Author: David Joyner (11-2005)
self, gen_mat) |
Functions: ambient_space,
assmus_mattson_designs,
automorphism_group_binary_code,
basis,
binomial_moment,
characteristic,
characteristic_polynomial,
check_mat,
chinen_polynomial,
decode,
dimension,
direct_sum,
divisor,
dual_code,
extended_code,
galois_closure,
gen_mat,
gens,
genus,
is_galois_closed,
is_permutation_automorphism,
is_self_dual,
is_self_orthogonal,
is_subcode,
length,
list,
minimum_distance,
module_composition_factors,
permutation_automorphism_group,
permuted_code,
punctured,
random_element,
redundancy_matrix,
sd_duursma_data,
sd_duursma_q,
sd_zeta_polynomial,
shortened,
spectrum,
standard_form,
support,
weight_distribution,
weight_enumerator,
zeta_function,
zeta_polynomial
self, 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
(1) If
and
holds a simple t-design.
(2) If
and
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
lambda blocks the block design is called a
design (or simply a
-design when the
parameters are not specfied). 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 C* (of course C=C* in this case, so this info is extraneous). The test fails to produce 6-designs (ie, the hypotheses of the theorem fail to hold, not that the 6-designs definitely don't exist). The command assmus_mattson_designs(C,5,mode="verbose") returns the same value but prints out more detailed information.
The second example below illustrates the blocks of the 5-(24, 8, 1) design (ie, the S(5,8,24) Steiner system).
sage: C = ExtendedBinaryGolayCode() # example 1 sage: C.assmus_mattson_designs(5) ['weights from C: ', [8, 12, 16, 24], 'designs from C: ', [[5, (24, 8, 1)], [5, (24, 12, 48)], [5, (24, 16, 78)], [5, (24, 24, 1)]], 'weights from C*: ', [8, 12, 16], 'designs from C*: ', [[5, (24, 8, 1)], [5, (24, 12, 48)], [5, (24, 16, 78)]]] sage: C.assmus_mattson_designs(6) 0 sage: X = range(24) # example 2 sage: blocks = [c.support() for c in C if hamming_weight(c)==8]; len(blocks) # long time computation 759
REFERENCE: [HP] W. C. Huffman and V. Pless, Fundamentals of ECC, Cambridge Univ. Press, 2003.
self) |
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
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
self, i) |
Returns the i-th binomial moment of the
-code
:
where
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: I. Duursma, "Combinatorics of the two-variable zeta function", Finite fields and applications, 109-136, Lecture Notes in Comput. Sci., 2948, Springer, Berlin, 2004.
self) |
Returns the characteristic polynomial of a linear code, as defined in van Lint's text [vL].
sage: C = ExtendedBinaryGolayCode() sage: C.characteristic_polynomial() -4/3*x^3 + 64*x^2 - 2816/3*x + 4096
REFERENCES: van Lint, Introduction to coding theory, 3rd ed., Springer-Verlag GTM, 86, 1999.
self) |
Returns the check matrix of self.
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]
self) |
Returns the Chinen zeta polynomial of the code.
sage: C = HammingCode(3,GF(2)) sage: C.chinen_polynomial() # long time (2*sqrt(2)*t^3/5 + 2*sqrt(2)*t^2/5 + 2*t^2/5 + sqrt(2)*t/5 + 2*t/5 + 1/5)/(sqrt(2) + 1) sage: C = TernaryGolayCode() sage: C.chinen_polynomial() # long time (3*sqrt(3)*t^3/7 + 3*sqrt(3)*t^2/7 + 3*t^2/7 + sqrt(3)*t/7 + 3*t/7 + 1/7)/(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.
self, right) |
Wraps GUAVA's Decodeword. Hamming codes have a special decoding algorithm. Otherwise, syndrome decoding is used.
Input: right must be a vector of length = length(self)
Output: The codeword c in C closest to r.
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: 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: v4 = [[a,a,F(0),a,a,F(0),a]] sage: C.decode(v4) (1, 0, 0, 1, 1, 0, 1) 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)
Does not work for very long codes since the syndrome table grows too large.
self, other) |
C1, C2 must be linear codes defined over the same base ring. Returns the (usual vector space) direct sum of the codes.
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
self) |
Returns the divisor of a code (the divisor is the smallest
integer
such that each
iff
is divisible by
).
sage: C = ExtendedBinaryGolayCode() sage: C.divisor() # Type II self-dual 4 sage: C = QuadraticResidueCodeEvenPair(17,GF(2))[0] sage: C.divisor() 2
self) |
This computes the dual code Cd of the code C,
Does not call GAP.
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
self) |
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).
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
self, F0) |
If self is a linear code defined over
and
is a subfield
with Galois group
then this returns the
-module
containing
.
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
self) |
Returns the generator matrix of the code.
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]
self) |
Returns the "Duursma genus" of the code, gamma_C = n+1-k-d.
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.
self) |
Checks if
is equal to its Galois closure.
self, g) |
Returns
if
is an element of
(
= length of
self) and if
is an automorphism of self.
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
self) |
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.
sage: C = ExtendedBinaryGolayCode() sage: C.is_self_dual() True sage: C = HammingCode(3,GF(2)) sage: C.is_self_dual() False
C) |
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.
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) sage: C.is_self_orthogonal() True
self, other) |
Returns true if the first is a subcode of the second.
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
self) |
Return list of all elements of this linear code.
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
self) |
Uses a GAP kernel function (in C) written by Steve Linton.
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
self, gp) |
Prints the GAP record of the Meataxe composition factors module in Meataxe notation.
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.
self, [mode=None]) |
If
is an
code over
, this function computes
the subgroup
of all permutation
automorphisms of
. If mode="verbose" then
code-theoretic data is printed out at several stages
of the computation.
Combines an idea of mine with an improvement suggested by Cary Huffman.
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
self, p) |
Returns the permuted code - the code
which is equivalent
to self via the column permutation
.
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
self, L) |
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
sage: C = HammingCode(3,GF(2)) sage: C.punctured([1,2]) Linear code of length 5, dimension 4 over Finite Field of size 2
self) |
Returns a random codeword.
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
C) |
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.
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]
C, i) |
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]
REFERENCES: [D] I. Duursma, "Extremal weight enumerators and ultraspherical polynomials"
C, i, d0) |
Input:
RETURN:
The coefficients
of
as in Duursama [D].
REFERENCES: [D] I. Duursma, "Extremal weight enumerators and ultraspherical polynomials"
C, [typ=1]) |
Returns the Duursma zeta function of a self-dual code using the construction in [D].
Input:
sage: C1 = HammingCode(3,GF(2)) sage: C2 = C1.extended_code(); C2 Linear code of length 8, dimension 4 over Finite Field of size 2 sage: C2.is_self_dual() True sage: C2.sd_zeta_polynomial() 2/5*T^2 + 2/5*T + 1/5 sage: C2.zeta_polynomial() 2/5*T^2 + 2/5*T + 1/5 sage: P = C2.sd_zeta_polynomial(); P(1) 1 sage: F.<z> = GF(4,"z") sage: MS = MatrixSpace(F, 3, 6) sage: G = MS([[1,0,0,1,z,z],[0,1,0,z,1,z],[0,0,1,z,z,1]]) sage: C = LinearCode(G) # the "hexacode" sage: C.sd_zeta_polynomial(4) 1
It is a general fact about Duursma zeta polynomials that P(1) = 1.
REFERENCES: [D] I. Duursma, "Extremal weight enumerators and ultraspherical polynomials"
self, L) |
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.
sage: C = HammingCode(3,GF(2)) sage: C.shortened([1,2]) Linear code of length 5, dimension 2 over Finite Field of size 2
self) |
Uses a GAP kernel function (in C) written by Steve Linton.
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]
self) |
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.
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)
self) |
Returns the set of indices
where
is nonzero,
where spectrum(self) =
.
sage: C = HammingCode(3,GF(2)) sage: C.spectrum() [1, 0, 0, 7, 7, 0, 0, 1] sage: C.support() [0, 3, 4, 7]
self) |
Uses a GAP kernel function (in C) written by Steve Linton.
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]
self, [names=xy]) |
Returns the weight enumerator of the code.
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
self, [name=T]) |
Returns the Duursma zeta function of the code.
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)
self, [name=T]) |
Returns the Duursma zeta polynomial of the code C.
Assumes C.minimum_distance()
> 1 and minimum_distance
.
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)) sage: C.minimum_distance() 3 sage: C.zeta_polynomial() 2/5*T^2 + 2/5*T + 1/5 sage: C = HammingCode(4,GF(2)) sage: C.zeta_polynomial() 16/429*T^6 + 16/143*T^5 + 80/429*T^4 + 32/143*T^3 + 30/143*T^2 + 2/13*T + 1/13 sage: F.<z> = GF(4,"z") sage: MS = MatrixSpace(F, 3, 6) sage: G = MS([[1,0,0,1,z,z],[0,1,0,z,1,z],[0,0,1,z,z,1]]) sage: C = LinearCode(G) # the "hexacode" sage: C.zeta_polynomial() 1
REFERENCES:
I. Duursma, "From weight enumerators to zeta functions", in Discrete Applied Mathematics, vol. 111, no. 1-2, pp. 55-73, 2001.
Special Functions: __cmp__,
__contains__,
__eq__,
__init__,
__iter__,
_repr_
self, right) |
Checks if self == right.
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
self) |
Return an iterator over the elements of this linear code.
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]]