Construction of Codes#

Construction of General Linear Codes#

LinearCode<R, n | L>: FldFin, RngIntElt, List -> Code#

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\).

Example: Ternary Golay Code (ex-4d7dd8)#

We define the ternary Golay code as a six-dimensional subspace of the vector space \(K^{(11)}\), where \(K\) is \({\bf F}_{3}\). The ternary Golay code could be defined in a single statement as follows:

> 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]>;

Run in calculator

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]>);

Run in calculator

LinearCode(U): ModTupRng -> Code#

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\ \times\ n\) matrix belonging to the \(R\)-matrix space, \(R^{(k\ \times\ n)}\).
(b): The parity check matrix \(H\) for \(C\), created as an \((n-k)\ \times\ n\) matrix belonging to the \(R\)-matrix space, \(R^{(n-k)\ \times\ n)}\).

LinearCode(A): ModMatRngElt -> Code#: Given a \(k\ \times\ 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.

Example: Code From Matrix (ex-854c75)#

We define a code by constructing a matrix in a \(K\)-matrix space and using its row space to generate the code:

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

Run in calculator

PermutationCode(u, G): ModTupRngElt, GrpPerm -> Code#: 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\).

Example: Permutation Code (ex-db1b6e)#

We define \(G\) to be a permutation group of degree 7 and construct the code \(C\) as the \(F_2\)-code generated by applying the permutations of \(G\) to a certain vector:

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

Run in calculator

Some Trivial Linear Codes#

ZeroCode(R, n): FldFin, RngIntElt -> Code#: 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\)).

RepetitionCode(R, n): FldFin, RngIntElt -> Code#: Given a ring \(R\) and positive integer \(n\), return the \([n,1,n]\) code over \(K\) generated by the all-ones vector.

ZeroSumCode(R, n): FldFin, RngIntElt -> Code#: Given a ring \(R\) and positive integer \(n\), return the \([n,n-1,2]\) code over \(R\) such that for all codewords \((c_1,c_2,\ldots ,c_n)\) we have \(\sum_{i} c_i =0\).

UniverseCode(R, n): FldFin, RngIntElt -> Code#: Given a ring \(R\) and positive integer \(n\), return the \([n,n,1]\) code consisting of all possible codewords.

EvenWeightCode(n): RngIntElt -> Code#: Given a positive integer \(n\), return the \([n,n-1,2]\) code over \({\bf F}_{2}\) such that all vectors have even weight. This is equivalent to the zero sum code over \({\bf F}_{2}\).

EvenWeightSubcode(C): Code -> Code#: Given a linear code \(C\) over \({\bf F}_{2}\), return the subcode of \(C\) containing the vectors of even weight.

RandomLinearCode(K, n, k): FldFin, RngIntElt, RngIntElt -> Code#: Given a finite field \(K\) and positive integers \(n\) and \(k\), such that \(0 < k \le 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.

CordaroWagnerCode(n): RngIntElt -> Code#: Construct the Cordaro–Wagner code of length \(n\), This is the \(2\)-dimensional repetition code over \({\bf F}_{2}\) of length \(n\) and having the largest possible minimum weight.

Example: Simple Code Chain (ex-552322)#

Over any specific finite field \(K\), the zero code of length \(n\) is contained in every code of length \(n\), and similarly every code of length \(n\) is contained in the universe code of length \(n\). This is illustrated over \(GF(2)\) for length \(6\) codes with an arbitrary code of length \(6\) dimension \(3\).

> 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

Run in calculator

Some Basic Families of Codes#

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.

CyclicCode(n, g): RngIntElt, RngUPolElt -> Code#: Let \(K\) be a finite field. Given a positive integer \(n\) and a univariate polynomial \(g(x) \in K[x]\) of degree \(n-k\) such that \(g(x) \mid x^n - 1\), construct the \([n, k]\) cyclic code generated by \(g(x)\).

Example: Cyclic Code (ex-667d8b)#

We construct the length \(23\) Golay code over \(GF(2)\) as a cyclic code by factorizing the polynomial \(x^{23} - 1\) over \(GF(2)\) and constructing the cyclic code generated by one of the factors of degree \(11\).

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

Run in calculator

HammingCode(K, r): FldFin, RngIntElt -> Code#: 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 = (q^r - 1)/(q - 1).\]

Example: Hamming Code (ex-496ba8)#

We construct the third order Hamming code over GF(2) together with its parity check matrix.

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

Run in calculator

SimplexCode(r): RngIntElt -> Code#: Given a positive integer \(r\), construct the \([2^r-1,r,2^{r-1}]\) binary simplex code, which is the dual of a Hamming code.

ReedMullerCode(r, m): RngIntElt, RngIntElt -> Code#: Given positive integers \(r\) and \(m\), where \(0 \leq r \leq m\), construct the \(r\)-th order binary Reed–Muller code of length \(n = 2^m\).

Example: Reed Muller Code (ex-86fc03)#

We construct the first order Reed–Muller code of length 16 and count the number of pairs of vectors whose components are orthogonal.

> 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

Run in calculator