6.1 Codes

A linear code of length $ n$ is a finite dimensional subspace of $ GF(q)^n$ . Sage can compute with linear error-correcting codes to a limited extent. It basically has some wrappers to GAP and GUAVA 2.8 commands (GUAVA 2.8 does not include any of Leon's C code which was included in previous versions of GUAVA). GUAVA 2.8 is included with Sage's install of GAP 4.4.7 and later.

Sage can compute Hamming codes

sage: C = HammingCode(3,GF(3))   
sage: C
Linear code of length 13, dimension 10 over Finite Field of size 3
sage: C.minimum_distance()     
3
sage: C.gen_mat()
    [1 0 0 0 0 0 0 0 2 0 0 2 1]
    [0 1 0 0 0 0 0 0 2 0 0 2 0]
    [0 0 1 0 0 0 0 0 2 0 0 2 2]
    [0 0 0 1 0 0 0 0 2 0 0 1 0]
    [0 0 0 0 1 0 0 0 2 0 0 1 2]
    [0 0 0 0 0 1 0 0 2 0 0 1 1]
    [0 0 0 0 0 0 1 0 2 0 0 0 2]
    [0 0 0 0 0 0 0 1 2 0 0 0 1]
    [0 0 0 0 0 0 0 0 0 1 0 2 2]
    [0 0 0 0 0 0 0 0 0 0 1 2 1]

the four Golay codes

sage: C = ExtendedTernaryGolayCode() 
sage: C
Linear code of length 12, dimension 6 over Finite Field of size 3
sage: C.minimum_distance()               
6
sage: C.gen_mat()               
[1 0 0 0 0 0 2 0 1 2 1 2]
[0 1 0 0 0 0 1 2 2 2 1 0]
[0 0 1 0 0 0 1 1 1 0 1 1]
[0 0 0 1 0 0 1 1 0 2 2 2]
[0 0 0 0 1 0 2 1 2 2 0 1]
[0 0 0 0 0 1 0 2 1 2 2 1]

as well as binary Reed-Muller codes, quadratic residue codes, quasi-quadratic residue codes, ``random'' linear codes, and a code generated by a matrix of full rank (using, as usual, the rows as the basis).

For a given code, $ C$ , Sage can return a generator matrix, a check matrix, and the dual code:

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: 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

For $ C$ and a vector $ v\in GF(q)^n$ , Sage can try to decode $ v$ (i.e., find the codeword $ c\in C$ closest to $ v$ in the Hamming metric) using syndrome decoding. As of yet, no special decoding methods have been implemented.

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)

To plot the (histogram of) the weight distribution of a code, one can use the matplotlib package included with Sage:

sage: C = HammingCode(4,GF(2))
sage: C
 Linear code of length 15, dimension 11 over Finite Field of size 2
sage: w = C.weight_distribution(); w
 [1, 0, 0, 35, 105, 168, 280, 435, 435, 280, 168, 105, 35, 0, 0, 1]
sage: J = range(len(w))
sage: W = IndexedSequence([ZZ(w[i]) for i in J],J)
sage: P = W.plot_histogram()

Now type show(P) to view this.

There are several coding theory functions we are skipping entirely. Please see the Sage reference manual or the file coding/linear_codes.py for examples.

Sage can also compute algebraic-geometric codes, called AG codes, via the Singular interface §15.2.1. One may also use the AG codes implemented in GUAVA via the Sage interface to GAP gap_console(). See the GUAVA manual for more details.

See About this document... for information on suggesting changes.