Sage and Coding Theory¶
Author: David Joyner and Robert Miller (2008), edited by Ralf Stephan
This brief paper surveys recent work in Sage on implementing algorithms to compute with linear block codes.
Included in Sage is the group theory package GAP [GAP] and GUAVA [GUAVA], GAP’s coding theory package. All of GUAVA’s functions can be accessed within Sage.
General coding theory functions¶
Many of the following coding theory functions are pure Python and do not call GUAVA:
LinearCode
class definition;LinearCodeFromVectorspace
conversion function.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]
This function also enables you to create your own code functions. The following function implements the hexacode.
def Hexacode(): """ This function returns the [6,3,4] hexacode over GF(4). It is an extremal (Hermitian) self-dual Type IV code. EXAMPLES: sage: C = Hexacode() # known bug sage: C.minimum_distance() # known bug 4 """ F = GF(4,"z") z = F.gen() MS = MatrixSpace(F, 3, 6) G = MS([[1, 0, 0, 1, z, z ],\ [0, 1, 0, z, 1, z ],\ [0, 0, 1, z, z, 1 ]]) return LinearCode(G)
The
spectrum
(weight distribution),minimum_distance
programs (calling Steve Linton’s C programs in GAP),characteristic_function
(as in [vanLint]), and several implementations of the Duursma zeta function (zeta_polynomial
,zeta_function
,chinen_polynomial
, for example),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)) # known bug sage: C.minimum_distance() # known bug 3 sage: C.zeta_polynomial() # known bug 2/5*T^2 + 2/5*T + 1/5
gen_mat
,check_mat
,decode
,dual_code
,extended_code
,binomial_moment
for LinearCode.The i-th binomial moment of the
-code
is
where
is the dimension of the shortened code
,
.
EXAMPLES:
sage: C = codes.HammingCode(3,GF(2)) sage: C.binomial_moment(2) 0 sage: C.binomial_moment(3) # known bug 0 sage: C.binomial_moment(4) # long time 35 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) # known bug (1, 0, 0, 1, 1, 0, 1)
Decoding, at the moment, merely uses syndrome decoding via GUAVA.
Boolean-valued functions such as “==”,
is_self_dual
,is_self_orthogonal
,is_permutation_automorphism
,permutation methods:
automorphism_group_binary_code
,is_permutation_automorphism
,standard_form
,module_composition_factors
.This latter function simply calls up the MeatAxe record from GAP.
EXAMPLES:
sage: C = codes.HammingCode(3,GF(2)) sage: G = C.automorphism_group_binary_code(); G # known bug Permutation Group with generators [(2,3)(5,7), (2,5)(3,7), (2,3,7,5)(4,6), (2,4)(6,7), (1,2)(3,4)] sage: G.order() # known bug 168 sage: C = codes.HammingCode(3,GF(2)) sage: C.generator_matrix() # known bug [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() # known bug [1 1 0] [1 1 1] [1 0 1] [0 1 1] sage: C.standard_form()[0].generator_matrix() # known bug [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(2),4,8) sage: G = MS([[1,0,0,0,1,1,1,0],[0,1,1,1,0,0,0,0], # known bug ....: [0,0,0,0,0,0,0,1],[0,0,0,0,0,1,0,0]]) # known bug sage: C = codes.LinearCode(G) # known bug sage: gp = C.automorphism_group_binary_code() # known bug sage: C.module_composition_factors(gp) # known bug [ rec( field := GF(2), isMTXModule := true, dimension := 1, generators := [ [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ] ], smashMeataxe := rec( algebraElement := [ [ [ 5, 3 ], [ 5, 3 ] ], [ Z(2)^0, Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0, Z(2)^0, Z(2)^0 ] ], algebraElementMatrix := [ [ 0*Z(2) ] ], characteristicPolynomial := x_1, charpolFactors := x_1, nullspaceVector := [ Z(2)^0 ], ndimFlag := 1 ), IsIrreducible := true ), rec( field := GF(2), isMTXModule := true, dimension := 1, generators := [ [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ] ], smashMeataxe := rec( algebraElement := [ [ [ 5, 2 ], [ 1, 2 ] ], [ 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2) ] ], algebraElementMatrix := [ [ 0*Z(2) ] ], characteristicPolynomial := x_1, charpolFactors := x_1, nullspaceVector := [ Z(2)^0 ], ndimFlag := 1 ), IsIrreducible := true ), rec( field := GF(2), isMTXModule := true, dimension := 1, generators := [ [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ] ], smashMeataxe := rec( algebraElement := [ [ [ 4, 2 ], [ 7, 4 ] ], [ 0*Z(2), Z(2)^0, Z(2)^0, 0*Z(2), Z(2)^0, Z(2)^0, Z(2)^0, Z(2)^0 ] ], algebraElementMatrix := [ [ 0*Z(2) ] ], characteristicPolynomial := x_1, charpolFactors := x_1, nullspaceVector := [ Z(2)^0 ], ndimFlag := 1 ), IsIrreducible := true ), rec( field := GF(2), isMTXModule := true, dimension := 1, generators := [ [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ], [ [ Z(2)^0 ] ] ], smashMeataxe := rec( algebraElement := [ [ [ 4, 6 ], [ 1, 6 ] ], [ 0*Z(2), Z(2)^0, Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0, Z(2)^0 ] ], algebraElementMatrix := [ [ Z(2)^0 ] ], characteristicPolynomial := x_1+Z(2)^0, charpolFactors := x_1+Z(2)^0, nullspaceVector := [ Z(2)^0 ], ndimFlag := 1 ), IsIrreducible := true ) ]
design-theoretic methods:
assmus_mattson_designs
(implementing the Assmus-Mattson Theorem).Theorem 1. (Assmus and Mattson Theorem. par. 8.4, page 303 of [HP]) Let
be the weight distribution of the codewords in a binary linear
code
, and let [1]
be the weight distribution 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
-design.
Some of the terms in the above theorem are recalled below (see for details). 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
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 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,
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
(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
-code
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
-
design (i.e., the
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 hamming_weight(c)==8] # known bug sage: len(blocks) # known bug 759
- If
The method automorphism_group_binary_code
is actually an interface
to an extremely fast implementation written by the second author. It
uses an open-source implementation of permutation backtracking, written
by Robert Miller and developed into a Sage module called NICE. This
package is described more fully in [Miller1].
A permutation of the fixed basis gives rise to a
permutation of the vectors, or words, in
, sending
to
. The (permutation) automorphism
group of the code
is the set of permutations of the indices
that bijectively map
to itself. Sage uses a partition
refinement algorithm to compute the automorphism group of any binary
code. In future work, this will be extended to other base rings.
Native constructions¶
Sage contains GUAVA but most of GUAVA’s functions have not been implemented in Python, so they must be called via the GAP interface. (See the GUAVA manual: https://code.google.com/p/guava-libraries/ for details on the syntax of GUAVA.)
In addition, here are some of the special codes implemented natively in Python:
BCHCode
- A ‘Bose-Chaudhuri-Hockenghem code’ (or BCH code, for short) is the largest possible cyclic code of lengthover field
, whose generator polynomial has zeros (contained in)
, where
is a primitive
root of unity in the splitting field
,
is an integer
and
is the multiplicative order of
modulo
.
SEEALSO: Wikipedia article BCH_code
EXAMPLES:
sage: FF.<a> = GF(3^2,"a") sage: x = PolynomialRing(FF,"x").gen() sage: L = [b.minpoly() for b in [a,a^2,a^3]]; g = LCM(L) sage: f = x^(8)-1 sage: g.divides(f) True sage: C = codes.CyclicCode(8,g); C Linear code of length 8, dimension 4 over Finite Field of size 3 sage: C.minimum_distance() 4 sage: C = codes.BCHCode(8,3,GF(3),1); C Linear code of length 8, dimension 4 over Finite Field of size 3 sage: C.minimum_distance() 4 sage: C = codes.BCHCode(8,5,GF(3)); C Linear code of length 8, dimension 3 over Finite Field of size 3 sage: C.minimum_distance() 5
BinaryGolayCode
,ExtendedBinaryGolayCode
,TernaryGolayCode
, - the well-known “extremal” Golay codes: Wikipedia article Golay_codeEXAMPLES:
sage: C = codes.ExtendedBinaryGolayCode() sage: C Linear code of length 24, dimension 12 over Finite Field of size 2 sage: C.minimum_distance() 8 sage: C.is_self_dual() True sage: C = codes.TernaryGolayCode() sage: C Linear code of length 11, dimension 6 over Finite Field of size 3 sage: C.minimum_distance() 5
Cyclic codes -
CyclicCodeFromGeneratingPolynomial
(=CyclicCode
),CyclicCodeFromCheckPolynomial
: Wikipedia article Cyclic_codeEXAMPLES:
sage: P.<x> = PolynomialRing(GF(3),"x") sage: g = x-1 sage: C = codes.CyclicCodeFromGeneratingPolynomial(4,g); C Linear code of length 4, dimension 3 over Finite Field of size 3 sage: P.<x> = PolynomialRing(GF(4,"a"),"x") sage: g = x^3+1 sage: C = codes.CyclicCodeFromGeneratingPolynomial(9,g); C Linear code of length 9, dimension 6 over Finite Field in a of size 2^2 sage: P.<x> = PolynomialRing(GF(2),"x") sage: g = x^3+x+1 sage: C = codes.CyclicCodeFromGeneratingPolynomial(7,g); C Linear code of length 7, dimension 4 over Finite Field of size 2 sage: C.generator_matrix() [1 1 0 1 0 0 0] [0 1 1 0 1 0 0] [0 0 1 1 0 1 0] [0 0 0 1 1 0 1] sage: g = x+1 sage: C = codes.CyclicCodeFromGeneratingPolynomial(4,g); C Linear code of length 4, dimension 3 over Finite Field of size 2 sage: C.generator_matrix() [1 1 0 0] [0 1 1 0] [0 0 1 1] sage: P.<x> = PolynomialRing(GF(3),"x") sage: C = codes.CyclicCodeFromCheckPolynomial(4,x + 1); C Linear code of length 4, dimension 1 over Finite Field of size 3 sage: C = codes.CyclicCodeFromCheckPolynomial(4,x^3 + x^2 + x + 1); C Linear code of length 4, dimension 3 over Finite Field of size 3 sage: C.generator_matrix() [2 1 0 0] [0 2 1 0] [0 0 2 1]
DuadicCodeEvenPair
,DuadicCodeOddPair
- Constructs the “even” (resp. “odd”) pair of duadic codes associated to a “splitting”,
of
. This is a special type of cyclic code whose generator is determined by
,
. See chapter 6 in [HP].
EXAMPLES:
sage: from sage.coding.code_constructions import is_a_splitting sage: n = 11; q = 3 sage: C = Zmod(n).cyclotomic_cosets(q); C [[0], [1, 3, 4, 5, 9], [2, 6, 7, 8, 10]] sage: S1 = C[1] sage: S2 = C[2] sage: is_a_splitting(S1,S2,11) True sage: codes.DuadicCodeOddPair(GF(q),S1,S2) (Linear code of length 11, dimension 6 over Finite Field of size 3, Linear code of length 11, dimension 6 over Finite Field of size 3)
This is consistent with Theorem 6.1.3 in [HP].
HammingCode
- the well-known Hamming code.The
Hamming code over
is an
code with length
, dimension
and minimum distance
. The parity check matrix of a Hamming code has rows consisting of all nonzero vectors of length r in its columns, modulo a scalar factor so no parallel columns arise. A Hamming code is a single error-correcting code.
SEEALSO: Wikipedia article Hamming_code
EXAMPLES:
sage: codes.HammingCode(3,GF(2)) Linear code of length 7, dimension 4 over Finite Field of size 2 sage: C = codes.HammingCode(3,GF(3)); C Linear code of length 13, dimension 10 over Finite Field of size 3 sage: C.minimum_distance() 3 sage: C = codes.HammingCode(3,GF(4,'a')); C Linear code of length 21, dimension 18 over Finite Field in a of size 2^2
LinearCodeFromCheckMatrix
- for specifing the code using the check matrix instead of the generator matrix.A linear
-code
is uniquely determined by its generator matrix
and check matrix
. These objects and morphisms fit into the following short exact sequence,
Here, “short exact” means (a) the arrow
is injective, i.e.,
is a full-rank
matrix, (b) the arrow
is surjective, and (c)
.
EXAMPLES:
sage: C = codes.HammingCode(3,GF(2)) sage: H = C.parity_check_matrix(); H # known bug [1 0 0 1 1 0 1] [0 1 0 1 0 1 1] [0 0 1 1 1 1 0] sage: codes.LinearCodeFromCheckMatrix(H) == C # known bug True sage: C = codes.HammingCode(2,GF(3)) sage: H = C.parity_check_matrix(); H # known bug [1 0 2 2] [0 1 2 1] sage: codes.LinearCodeFromCheckMatrix(H) == C # known bug True sage: C = codes.RandomLinearCode(10,5,GF(4,"a")) sage: H = C.parity_check_matrix() sage: codes.LinearCodeFromCheckMatrix(H) == C # known bug True
QuadraticResidueCodeEvenPair
,QuadraticResidueCodeOddPair
: Quadratic residue codes of a given odd prime length and base ring either don’t exist at all or occur as 4-tuples - a pair of “odd-like” codes and a pair of “even-like” codes. Ifis prime then (Theorem 6.6.2 in [HP]) a QR code exists over
if and only if
is a quadratic residue
. Here they are constructed as “even-like” (resp., “odd-like”) duadic codes associated the splitting
, where
is the set of non-zero quadratic residues and
is the non-residues.
QuadraticResidueCode
(a special case) andExtendedQuadraticResidueCode
are included as well.EXAMPLES:
sage: codes.QuadraticResidueCodeEvenPair(17,GF(13)) (Linear code of length 17, dimension 8 over Finite Field of size 13, Linear code of length 17, dimension 8 over Finite Field of size 13) sage: codes.QuadraticResidueCodeEvenPair(17,GF(2)) (Linear code of length 17, dimension 8 over Finite Field of size 2, Linear code of length 17, dimension 8 over Finite Field of size 2) sage: codes.QuadraticResidueCodeEvenPair(13,GF(9,"z")) (Linear code of length 13, dimension 6 over Finite Field in z of size 3^2, Linear code of length 13, dimension 6 over Finite Field in z of size 3^2) sage: C1 = codes.QuadraticResidueCodeEvenPair(7,GF(2))[0] sage: C1.is_self_orthogonal() True sage: C2 = codes.QuadraticResidueCodeEvenPair(7,GF(2))[1] sage: C2.is_self_orthogonal() True sage: C3 = codes.QuadraticResidueCodeOddPair(17,GF(2))[0] sage: C4 = codes.QuadraticResidueCodeEvenPair(17,GF(2))[1] sage: C3 == C4.dual_code() True
This is consistent with Theorem 6.6.9 and Exercise 365 in [HP].
RandomLinearCode
- Repeatedly applies Sage’srandom_element
applied to the ambientMatrixSpace
of the generator matrix until a full rank matrix is found.ReedSolomonCode
- Also called a “generalized Reed-Solomon code” (the “narrow” RS codes codes are also cyclic codes; they are part of GUAVA but have not been ported over to natice Python/Sage yet). Given a finite fieldof order
, let
and
be chosen such that
. Pick
distinct elements of
, denoted
. Then, the codewords are obtained by evaluating every polynomial in
of degree less than
at each
:
is a
code. (In particular,
is MDS [2].)
INPUT:
n
: the lengthk
: the dimensionF
: the base ringpts
: (optional) list ofpoints in
(if omitted then Sage picks
of them in the order given to the elements of
)
EXAMPLES:
sage: C = codes.ReedSolomonCode(6,4,GF(7)); C Linear code of length 6, dimension 4 over Finite Field of size 7 sage: C.minimum_distance() 3 sage: F.<a> = GF(3^2,"a") sage: pts = [0,1,a,a^2,2*a,2*a+1] sage: len(Set(pts)) == 6 # to make sure there are no duplicates True sage: C = codes.ReedSolomonCode(6,4,F,pts); C Linear code of length 6, dimension 4 over Finite Field in a of size 3^2 sage: C.minimum_distance() 3
ToricCode
- Letdenote a list of lattice points in
and let
denote a listing of all points in
. Put
and let
denote the dimension of the vector space of functions
. The associated toric code
is the evaluation code which is the image of the evaluation map
, where
is the multi-index notation.
EXAMPLES:
sage: C = codes.ToricCode([[0,0],[1,0],[2,0],[0,1],[1,1]],GF(7)) sage: C Linear code of length 36, dimension 5 over Finite Field of size 7 sage: C.minimum_distance() 24 sage: P = [ [0,0],[1,1],[1,2],[1,3],[1,4],[2,1],[2,2],[2,3],[3,1],[3,2],[4,1]] sage: C = codes.ToricCode(P, GF(8,"a")) sage: C Linear code of length 49, dimension 11 over Finite Field in a of size 2^3
This is in fact a
code over
. If you type next
C.minimum_distance()
and wait overnight (!), you will get 28.WalshCode
- a binary linearcode related to Hadamard matrices. Wikipedia article Walsh_code
EXAMPLES:
sage: C = codes.WalshCode(4); C Linear code of length 16, dimension 4 over Finite Field of size 2 sage: C.minimum_distance() 8
Bounds¶
Regarding bounds on coding theory parameters, this module implements:
best_known_linear_code_www
(interface with codetables.de since A. Brouwer’s online tables have been disabled). Explains the construction of the best known linear code overwith length
and dimension
, 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, whose field order must be in [2, 3, 4, 5, 7, 8, 9]verbose
- bool (default=False), print verbose mesSage
EXAMPLES:
sage: L = codes.best_known_linear_code_www(72, 36, GF(2)) # known bug sage: print L # known bug 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
bounds_minimum_distance
which call tables in GUAVA (updated May 2006) created by Cen Tjhai instead of the online internet tables. It simply returns the GAP record for that code:sage: print bounds_minimum_distance(10,5,GF(2)) # known bug rec( n := 10, k := 5, q := 2, references := 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 ] ] ], lowerBound := 4, lowerBoundExplanation := [ "Lb(10,5)=4, by shortening of:", "Lb(16,11)=4, by the u|u+v construction applied to C1 [8,7,2] and C2 [8,4,4]: ", "Lb(8,7)=2, dual of the repetition code", "Lb(8,4)=4, by the u|u+v construction applied to C1 [4,3,2] and C2 [4,1,4]: ", "Lb(4,3)=2, dual of the repetition code", "Lb(4,1)=4, repetition code" ], upperBound := 4, upperBoundExplanation := [ "Ub(10,5)=4, by the Griesmer bound" ] )
codesize_upper_bound(n,d,q)
, for the best known (as of May, 2006) upper boundfor the size of a code of length
, minimum distance
over a field of size
.
EXAMPLES:
sage: codesize_upper_bound(10, 3, 2) # known bug 85
This means that there is a
binary (non-linear) code. Since
, this is a better code that a
binary (linear) code, assuming one exists. Let’s use
best_known_linear_code_www
to find out:sage: L = best_known_linear_code_www(10, 6, GF(2)) # known bug sage: print L # known bug Construction of a linear code [10,6,3] over GF(2): [1]: [4, 1, 4] Cyclic Linear Code over GF(2) RepetitionCode of length 4 [2]: [4, 3, 2] Cyclic Linear Code over GF(2) Dual of the RepetitionCode of length 4 [3]: [8, 4, 4] Quasicyclic of degree 2 Linear Code over GF(2) PlotkinSum of [2] and [1] [4]: [8, 7, 2] Cyclic Linear Code over GF(2) Dual of the RepetitionCode of length 8 [5]: [16, 11, 4] Linear Code over GF(2) PlotkinSum of [4] and [3] [6]: [15, 11, 3] Linear Code over GF(2) Puncturing of [5] at 1 [7]: [10, 6, 3] Linear Code over GF(2) Shortening of [6] at { 11 .. 15 } last modified: 2001-01-30
Not only does a
binary linear code exist, the value
is the minimum distance is best known for
,
.
dimension_upper_bound(n,d,q)
, an upper boundfor the dimension of a linear code of length
, minimum distance
over a field of size
.
EXAMPLES:
sage: dimension_upper_bound(10, 3, 2) 6
This was established in the example above.
gilbert_lower_bound(n,q,d)
, a lower bound for number of elements in the largest code of minimum distancein
.
gv_info_rate(n,delta,q)
, namely, where GLB is the Gilbert lower bound above and
delta
.
Let
which measures the information rate of the code, and
which measures the error correcting ability of the code. Let
denote the set of all
such that there exists a sequence
,
, of
-codes for which
and
.
The following theorem describes information-theoretical limits on how “good” a linear code can be.
Theorem 2 (Manin [SS], chapter 1). There exists a continuous decreasing function
such that
is strictly decreasing on
,
,
- if
then
,
.
Not a single value of
is known for
! It is not known whether or not the maximum value of the bound,
is attained by a sequence of linear codes. It is not known whether or not
is differentiable for
, nor is it known if
is convex on
. However, the following estimate is known.
Theorem 3 (Gilbert-Varshamov, [SS] chapter 1). We have
In other words, for each fixed
, there exists an
-code
(which may depend on
) with
The curve
is called the Gilbert-Varshamov curve.
gv_bound_asymp(delta,q)
, asymptotic analog of the Gilbert lower bound.Sage : f = lambda x: gv_bound_asymp(x,2) Sage : plot(f,0,1/2)
plotkin_upper_bound(n,q,d)
plotkin_bound_asymp(delta,q)
, asymptotic analog of the Plotkin upper bound.
griesmer_upper_bound(n,q,d)
, the Griesmer upper bound.elias_upper_bound(n,q,d)
, the Elias upper bound.elias_bound_asymp(delta,q)
, asymptotic analog of the Elias upper bound.
hamming_upper_bound(n,q,d)
, the Hamming upper bound.hamming_bound_asymp(delta,q)
, asymptotic analog of the Hamming upper bound.
singleton_upper_bound(n,q,d)
, the Singleton upper bound.singleton_bound_asymp(delta,q)
, asymptotic analog of the Singleton upper bound.
mrrw1_bound_asymp(delta,q)
, “first” asymptotic McEliese-Rumsey-Rodemich-Welsh upper bound for the information rate .
Here are all the bounds together:
sage: f1 = lambda x: gv_bound_asymp(x,2)
sage: P1 = plot(f1,0,1/2,linestyle=":")
sage: f2 = lambda x: plotkin_bound_asymp(x,2)
sage: P2 = plot(f2,0,1/2,linestyle="--")
sage: f3 = lambda x: elias_bound_asymp(x,2)
sage: P3 = plot(f3,0,1/2,rgbcolor=(1,0,0))
sage: f4 = lambda x: singleton_bound_asymp(x,2)
sage: P4 = plot(f4,0,1/2,linestyle="-.")
sage: f5 = lambda x: mrrw1_bound_asymp(x,2)
sage: P5 = plot(f5,0,1/2,linestyle="steps")
sage: f6 = lambda x: hamming_bound_asymp(x,2)
sage: P6 = plot(f6,0,1/2,rgbcolor=(0,1,0))
sage: show(P1+P2+P3+P4+P5+P6)
Self-dual codes¶
Sage also includes a database of all self-dual binary codes of length
(and some of length
). The main function is
self_dual_codes_binary
, which is a case-by-case list of entries,
each represented by a Python dictionary.
Format of each entry: a Python dictionary with keys order autgp
,
spectrum
, code
, Comment
, Type
, where
code
- a self-dual codeof length
, dimension
, over
,
order autgp
- order of the permutation automorphism group of,
Type
- the type of(which can be “I” or “II”, in the binary case),
spectrum
- the spectrum,
Comment
- possibly an empty string.
In fact, in Table 9.10 of , the number of inequivalent
self-dual binary codes of length
is given:
![]() |
2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 | 20 | 22 | 24 | 26 | 28 | 30 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
![]() |
1 | 1 | 1 | 2 | 2 | 3 | 4 | 7 | 9 | 16 | 25 | 55 | 103 | 261 | 731 |
According to an entry in Sloane’s Online Encyclopedia of Integer Sequences, http://oeis.org/A003179, the next 2 entries are: 3295, 24147.
EXAMPLES:
sage: C = self_dual_codes_binary(10)["10"]
sage: C["0"]["code"] == C["0"]["code"].dual_code()
True
sage: C["1"]["code"] == C["1"]["code"].dual_code()
True
sage: len(C.keys()) # number of inequiv sd codes of length 10
2
sage: C = self_dual_codes_binary(12)["12"]
sage: C["0"]["code"] == C["0"]["code"].dual_code()
True
sage: C["1"]["code"] == C["1"]["code"].dual_code()
True
sage: C["2"]["code"] == C["2"]["code"].dual_code()
True
These Sage commands simply show that the two inequivalent self-dual binary codes of length 10, and the two inequivalent self-dual binary codes of length 12, are indeed self dual.
A lot of work on the classification of doubly even self-orthogonal codes using Sage can be found at http://www.rlmiller.org/de_codes/.
The number of permutation equivalence classes of all doubly even
-codes is shown in the table at
http://www.rlmiller.org/de_codes/, and the list of codes so far
discovered is linked from the list entries. Each link on that webpage
points to a Sage object file, which when loaded (e.g.,
Sage : L = load('24_12_de_codes.sobj')
) is a list of matrices in
standard form. The algorithm is described in .
REFERENCES:
[GAP] | The GAP Group, GAP - Groups, Algorithms, and Programming, Version 4.4.10; 2007. http://www.gap-system.org. |
[GUAVA] | GUAVA, a coding theory package for GAP, http://sage.math.washington.edu/home/wdj/guava/. |
[HP] | (1, 2, 3, 4, 5, 6) W. C. Huffman and V. Pless, Fundamentals of error-correcting codes, Cambridge Univ. Press, 2003. |
[vanLint] | J. van Lint, Introduction to coding theory, 3rd ed., Springer-Verlag GTM, 86, 1999. |
[Miller1] | Robert Miller, Graph automorphism computation, March 2007. |
[Miller2] | —, Doubly even codes, http://www.rlmiller.org/talks/June_Meeting.pdf, June 2007. |
[Sage] | The Sage Group, Sage : Mathematical software, version 3.0. http://www.sagemath.org/. |
[SS] | (1, 2) S. Shokranian and M.A. Shokrollahi, Coding theory and bilinear complexity, Scientific Series of the International Bureau, KFA Juelich, Vol. 21, 1994. |
[1] | For typographical reasons, the output of the program
assmus_mattson_designs uses C* instead of ![]() |
[2] | A code ![]() ![]() |