Module linear_code
source code
Linear Codes
VERSION: 0.11
Let $ F$ be a finite field (we denote the finite field with $q$ elements
$GF(q)$ by $\FF_q$). A subspace of $ F^n$ (with the standard basis)
is called a {\it linear code} of length $ n$. If its
dimension is denoted $k$ then we typically store a basis
of $C$ as a $k\times n$ matrix (the rows are the basis vectors)
called the {\it generator matrix} of $C$.
The rows of the {\it parity check matrix} of $C$ are a basis
for the code,
\[
C^* = \{ v \in GF(q)^n\ |\ v\cdot c = 0,\ for \ all\ c \in C \},
\]
called the {\it dual space} of $C$.
If $ F=\FF_2$ then $C$ is called a {\it binary code}.
If $ F = \FF_q$ then $C$ is called a {\it $ q$-ary code}.
The elements of a code $C$ are called {\it codewords}.
The symmetric group $S_n$ acts on $F^n$ by permuting coordinates.
If an element $p\in S_n$ sends a code $C$ of length $n$ to itself
(in other words, every codeword of $C$ is sent to some other codeword
of $C$) then $p$ is called a {\it permutation automorphism} of $C$.
The (permutation) automorphism group is denoted $Aut(C)$.
This file contains
\begin{enumerate}
\item
LinearCode class definition; LinearCodeFromVectorspace conversion function,
\item
The spectrum (weight distribution), minimum distance
programs (calling Steve Linton's C programs), characteristic_function,
and several implementations of the Duursma zeta function
(sd_zeta_polynomial, zeta_polynomial, zeta_function, chinen_polynomial,
for example),
\item
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,
\item
gen_mat, list, check_mat, decode, dual_code, extended_code, shortened, punctured,
genus, binomial_moment, and divisor methods for LinearCode,
\item
Boolean-valued functions such as "==", is_self_dual, is_self_orthogonal,
is_subcode, is_permutation_automorphism,
\item
permutation methods: automorphism_group_binary_code,
is_permutation_automorphism, (permutation_automorphism_group is deprecated),
permuted_code, standard_form, module_composition_factors,
\item
design-theoretic methods:
assmus_mattson_designs (implementing Assmus-Mattson Theorem),
\item
code constructions, such as HammingCode and ToricCode, are in a separate
\code{code_constructions.py} module; in the separate \code{guava.py} module,
you will find constructions, such as RandomLinearCodeGuava and
BinaryReedMullerCode, wrapped from the corresponding GUAVA codes.
\end{enumerate}
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:
\begin{enumerate}
\item More wrappers
\item GRS codes and special decoders.
\item $P^1$ Goppa codes and group actions on $P^1$ RR space codes.
\end{enumerate}
REFERENCES:
[HP] W. C. Huffman and V. Pless, {\bf Fundamentals of error-correcting codes},
Cambridge Univ. Press, 2003.
[Gu] GUAVA manual, http://www.gap-system.org/Packages/guava.html
AUTHOR:
-- 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
-- DJ (2006-07): added documentation, group-theoretical methods, ToricCode
-- DJ (2006-08): hopeful latex fixes to documention, 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?)
-- DJ (2006-08): hopeful latex fixes to documention,
added CyclicCode, best_known_linear_code, bounds_minimum_distance,
assmus_mattson_designs (implementing Assmus-Mattson Theorem).
-- DJ (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
-- DJ (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.
-- DJ (2007-11): added zeta_polynomial, weight_enumerator,
chinen_polynomial; improved best_known_code;
made some pythonic revisions;
added is_equivalent (for binary codes)
-- dj (2008-01): fixed bug in decode reported by harald schilly,
(with M Hansen) added some doctests.
-- dj (2008-02): translated standard_form, dual_code to Python.
-- dj (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.
-- dj (2008-03): fixed bugs in spectrum and zeta_polynomial (which misbehaved over
non-prime base rings.
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
|
|
LinearCode
A class for linear codes over a finite field or finite ring.
|
|
|
|
|
|
wtdist(Gmat,
F)
INPUT:
Gmat -- a string representing a GAP generator matrix G of a
linear code. |
source code
|
|
|
|
min_wt_vec(Gmat,
F)
Uses C programs written by Steve Linton in the kernel of GAP, so
is fairly fast. |
source 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
\url{http://www.codetables.de/}. |
source code
|
|
|
|
bounds_minimum_distance(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. |
source code
|
|
|
|
self_orthogonal_binary_codes(n,
k,
b=2,
parent=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...,
BC=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...,
equal=False,
in_test=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...)
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]. |
source code
|
|
|
|
LinearCodeFromVectorSpace(self)
Simply converts a vector subspace V of $GF(q)^n$ into a LinearCode. |
source code
|
|
|
|
ZZ = ['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1... |
INPUT:
Gmat -- a string representing a GAP generator matrix G of a
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(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)
|
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.
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(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)
|
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
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.
|
best_known_linear_code_www(n,
k,
F,
verbose=False)
| source code
|
Explains the construction of the best known linear code over
GF(q) with length n and dimension k, courtesy of the www page
\url{http://www.codetables.de/}.
INPUT:
n -- integer, the length of the code
k -- integer, the dimension of the code
F -- finite field, whose field order must be in
[2, 3, 4, 5, 7, 8, 9]
verbose -- bool (default=False), print verbose message
OUTPUT:
str -- text about why the bounds are as given
EXAMPLES:
sage: L = best_known_linear_code_www(72, 36, GF(2)) # requires internet, optional
sage: print L # requires internet, optional
Construction of a linear code
[72,36,15] over GF(2):
[1]: [73, 36, 16] Cyclic Linear Code over GF(2)
CyclicCode of length 73 with generating polynomial x^37 + x^36 + x^34 +
x^33 + x^32 + x^27 + x^25 + x^24 + x^22 + x^21 + x^19 + x^18 + x^15 + x^11 +
x^10 + x^8 + x^7 + x^5 + x^3 + 1
[2]: [72, 36, 15] Linear Code over GF(2)
Puncturing of [1] at 1
last modified: 2002-03-20
This function raises an IOError if an error occurs downloading
data or parsing it. It raises a ValueError if the q input is
invalid.
AUTHOR: (2005-11-14) Steven Sivek, (2008-03) modified by David Joyner
|
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.
|
self_orthogonal_binary_codes(n,
k,
b=2,
parent=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...,
BC=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...,
equal=False,
in_test=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...)
| source code
|
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 -- maximal length
k -- maximal dimension
b -- require that the generators all have weight divisible by b (if b=2, all
self-orthogonal codes are generated, and if b=4, all doubly even codes
are generated). Must be an even positive integer.
parent -- dafault None, used in recursion
BC -- dafault None, used in recursion
equal -- default False, if True generates only [n, k] codes
in_test -- default None, used in recursion
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))
Traceback (most recent call last):
...
ValueError: b (1) must be a positive even integer.
|
ZZ
- Value:
['4ti2-20061025',
'R-2.6.0',
'atlas-3.7.37',
'atlas-3.8.1',
'atlas-3.8.1.p1',
'atlas-3.8.1.p3',
'atlas-3.8.p11',
'atlas-3.8.p6',
...
|
|