Create a code as a subspace of V = R(n) which is generated by the elements specified by the list L, where L is a list of one or more items of the following types:
- (a)
- An element of V.
- (b)
- A set or sequence of elements of V.
- (c)
- A sequence of n elements of K, defining an element of V.
- (d)
- A set or sequence of sequences of type (c).
- (e)
- A subspace of V.
- (f)
- A set or sequence of subspaces of V.
> K := FiniteField(3); > C := LinearCode<K, 11 | > [1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1], [0, 1, 0, 0, 0, 0, 0, 1, 2, 2, 1], > [0, 0, 1, 0, 0, 0, 1, 0, 1, 2, 2], [0, 0, 0, 1, 0, 0, 2, 1, 0, 1, 2], > [0, 0, 0, 0, 1, 0, 2, 2, 1, 0, 1], [0, 0, 0, 0, 0, 1, 1, 2, 2, 1, 0]>;Alternatively, if we want to see the code as a subspace of K(11), we would proceed as follows:
> K := FiniteField(3); > K11 := VectorSpace(K, 11); > C := LinearCode(sub<K11 | > [1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1], [0, 1, 0, 0, 0, 0, 0, 1, 2, 2, 1], > [0, 0, 1, 0, 0, 0, 1, 0, 1, 2, 2], [0, 0, 0, 1, 0, 0, 2, 1, 0, 1, 2], > [0, 0, 0, 0, 1, 0, 2, 2, 1, 0, 1], [0, 0, 0, 0, 0, 1, 1, 2, 2, 1, 0]>);
Let V be the R-space R(n) and suppose that U is a subspace of V. The effect of this function is to define the linear code C corresponding to the subspace U. Suppose the code C being constructed has dimension k. The evaluation of this constructor results in the creation of the following objects:
- (a)
- The generator matrix G for C, created as a k x n matrix belonging to the R-matrix space, R(k x n).
- (b)
- The parity check matrix H for C, created as an (n - k) x n matrix belonging to the R-matrix space, R(n - k) x n).
Given a k x n matrix A over the ring R, construct the linear code generated by the rows of A. Note that it is not assumed that the rank of A is k. The effect of this constructor is otherwise identical to that described above.
> M := KMatrixSpace(FiniteField(5), 2, 4); > G := M ! [1,1,1,2, 3,2,1,4]; > G; [1 1 1 2] [3 2 1 4] > C := LinearCode(G); > C; [4, 2, 2] Linear Code over GF(5) Generator matrix: [1 0 4 0] [0 1 2 2]
Given a finite permutation group G of degree n, and a vector u belonging to the n-dimensional vector space V over the ring R, construct the code C corresponding to the subspace of V spanned by the set of vectors obtained by applying the permutations of G to the vector u.
> G := PSL(3, 2);
> G;
Permutation group G of degree 7
(1, 4)(6, 7)
(1, 3, 2)(4, 7, 5)
> V := VectorSpace(GF(2), 7);
> u := V ! [1, 0, 0, 1, 0, 1, 1];
> C := PermutationCode(u, G);
> C;
[7, 3, 4] Linear Code over GF(2)
Generator matrix:
[1 0 0 1 0 1 1]
[0 1 0 1 1 1 0]
[0 0 1 0 1 1 1]
Given a ring R and positive integer n, return the [n, 0, n] code consisting of only the zero code word, (where the minimum weight is by convention equal to n).
Given a ring R and positive integer n, return the [n, 1, n] code over K generated by the all-ones vector.
Given a ring R and positive integer n, return the [n, n - 1, 2] code over R such that for all codewords (c1, c2, ... , cn) we have ∑i ci =0 .
Given a ring R and positive integer n, return the [n, n, 1] code consisting of all possible codewords.
Given a positive integer n, return the [n, n - 1, 2] code over GF(2) such that all vectors have even weight. This is equivalent to the zero sum code over GF(2).
Given a linear code C over GF(2), return the subcode of C containing the vectors of even weight.
Given a finite field K and positive integers n and k, such that 0 < k ≤n, the function returns a random linear code of length n and dimension k over the field K. The method employed is to successively choose random vectors from K(n) until generators for a k-dimensional subspace have been found.
Construct the Cordaro--Wagner code of length n, This is the 2-dimensional repetition code over GF(2) of length n and having the largest possible minimum weight.
> K := GF(2); > U := UniverseCode(K, 6); > U; [6, 6, 1] Linear Code over GF(2) > Z := ZeroCode(K, 6); > Z; [6, 0, 6] Linear Code over GF(2) > R := RandomLinearCode(K, 6, 3); > (Z subset R) and (R subset U); true
In this section we describe how to construct three very important families of codes: cyclic codes, Hamming codes and Reed-Muller codes. We choose to present these very important families at this stage since they are easily understood and they give us a nice collection of codes for use in examples.
Many more constructions will be described in subsequent sections. In particular, variations and generalizations of the cyclic code construction presented here will be given.
Let K be a finite field. Given a positive integer n and a univariate polynomial g(x) ∈K[x] of degree n - k such that g(x) | xn - 1, construct the [n, k] cyclic code generated by g(x).
> P<x> := PolynomialRing(FiniteField(2));
> F := Factorization(x^23 - 1);
> F;
[
<x + 1, 1>,
<x^11 + x^9 + x^7 + x^6 + x^5 + x + 1, 1>,
<x^11 + x^10 + x^6 + x^5 + x^4 + x^2 + 1, 1>
]
> CyclicCode(23, F[2][1]);
[23, 12, 7] Cyclic Code over GF(2)
Generator matrix:
[1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1]
[0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 0 0]
[0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 0]
[0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1]
[0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 1 1 0 0]
[0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 1 1 0]
[0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 1 1]
[0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 1 1 1 0 0 0 1 1]
[0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1]
[0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1]
[0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 0 1]
Given a positive integer r, and a finite field K of cardinality q, construct the r-th order Hamming code over K of cardinality q. This code has length n = (qr - 1)/(q - 1).
> H := HammingCode(FiniteField(2), 3); > H; [7, 4, 3] Hamming code (r = 3) over GF(2) Generator matrix: [1 0 0 0 0 1 1] [0 1 0 0 1 1 0] [0 0 1 0 1 0 1] [0 0 0 1 1 1 1] > ParityCheckMatrix(H); [1 0 1 0 1 1 0] [0 1 1 0 0 1 1] [0 0 0 1 1 1 1]
Given a positive integer r, construct the [2r - 1, r, 2r - 1] binary simplex code, which is the dual of a Hamming code.
Given positive integers r and m, where 0 ≤r ≤m, construct the r-th order binary Reed--Muller code of length n = 2m.
> R := ReedMullerCode(1, 4);
> R;
[16, 5, 8] Reed-Muller Code (r = 1, m = 4) over GF(2)
Generator matrix:
[1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1]
[0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
[0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1]
[0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1]
[0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1]
> #{ <v, w>: v, w in R | IsZero(InnerProduct(v, w)) };
1024