Definition of a Code

[Next] [Prev] [Right] [Left] [Up] [Index] [Root]

Subsections

Construction of General Linear Codes

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

Create a code as a subspace of V = K^((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:

An element of V.
A set or sequence of elements of V.
A sequence of n elements of K, defining an element of V.
A set or sequence of sequences of type (c).
A subspace of V.
A set or sequence of subspaces of V.

LinearCode(U) : ModTupFld -> Code

Let V be the K-space K^((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:

The K-matrix space Hom(U, V), where U is the k-dimensional vector space of n-tuples over K.
The K-matrix space Hom(V, U), where U is as in (a).
The generator matrix G for C, created as an element of Hom(U, V).
The parity check matrix H for C, created as an element of Hom(V, U).

LinearCode(A) : ModMatFldElt -> Code

Given a matrix A belonging to Hom(U, V), where U is a k-dimensional K-space and V is an n-dimensional K-space, construct the linear code generated by the rows of A. Note that we do not assume that the rank of A is k. The effect of this constructor is otherwise identical to that described above.

PermutationCode(u, G) : ModTupFldElt, 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 field K, 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 `Code_TernaryGolayCode (H40E1)`

We define the ternary Golay code as a six-dimensional subspace of the vector space K^((11)), where K is GF(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]>;

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

Even more succinctly, we can construct the code 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]>;

Example `Code_CodeFromMatrix (H40E2)`

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];
> print G;
[1 1 1 2]
[3 2 1 4]
> C := LinearCode(G);
> print C;
[4, 2, 2] Linear Code over GF(5)
Generator matrix:
[1 0 4 0]
[0 1 2 2]

Example `Code_PermutationCode (H40E3)`

We set G to be a permutation group of degree 7 and set C to be the code over the finite field with 2 elements generated by applying the permutations of G to a certain vector:

> G := PSL(3, 2);
> print 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);
> print 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]

Construction of Standard Linear Codes

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

ReedMullerCode(r, m) : RngIntElt, RngIntElt -> Code

Given a positive integers r and m, where 0 <= r <= m, construct the r-th order binary Reed-Muller code of length n = 2^m.

Example `Code_HammingCode (H40E4)`

We construct the third order Hamming code over GF(2) and check that its parity check matrix is as expected.

> H := HammingCode(FiniteField(2), 3);
> print 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]
> print ParityCheckMatrix(H);
[1 0 1 0 1 1 0]
[0 1 1 0 0 1 1]
[0 0 0 1 1 1 1]

Example `Code_ReedMullerCode (H40E5)`

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

> R := ReedMullerCode(1, 4);
> print 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]
> print #{ <v, w>: v, w in R | IsZero(InnerProduct(v, w)) };
1024

Construction of General Cyclic Codes

CyclicCode(u) : ModTupFldElt -> Code

Given a vector u belonging to the K-space K^((n)), construct the [n, k] cyclic code generated by the right cyclic shifts of the vector u.

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) | x^n - 1, construct the [n, k] cyclic code generated by g(x).

Example `Code_CyclicCode (H40E6)`

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

Construction of BCH Codes and their Generalizations

AlternantCode(A, Y, r, S) :

AlternantCode(A, Y, r) : [ FldFinElt ], [ FldFinElt ], RngIntElt -> Code

Let A = [alpha_1, ..., alpha_n] be a sequence of n distinct elements taken from the degree m extension K of the finite field S, and let Y = [y_1, ..., y_n] be a sequence of n non-zero elements from K. Let r be a positive integer. Given such A, Y, r, and S, this function constructs the alternant code A(A, Y) over S. This is an [n, k >= n - mr, d >= r + 1] code. If S is omitted, S is taken to be the prime subfield of K.

BCHCode(K, n, d, b) : FldFin, RngIntElt, RngIntElt, RngIntElt -> Code

BCHCode(K, n, d) : FldFin, RngIntElt, RngIntElt -> Code

Let K be the field GF(q) and let alpha be a primitive n-th root of unity in the degree m extension of K (i.e. the field GF(q^m)) where n satisfies the condition gcd(n, q) = 1. Given a positive integer d, and an integer b >= 1, this function constructs the BCH code of designated distance d having generator polynomial g(x) = lcm{ m_1(x), ..., m_(d - 1)} where m_i(x) is the minimum polynomial of alpha^(b + i - 1), for i = 1, ..., d - 1. If the parameter b is omitted, its value is taken to be one. The BCH code is an [n, k >= n - m(d - 1), D >= d] code over K.

GoppaCode(L, G) : [ FldFinElt ], RngUPolElt -> Code

Let K be the field GF(q), let G(z) = G be a polynomial defined over the degree m extension field F of K (i.e. the field GF(q^m)) and let L = [alpha_1, ..., alpha_n] be a sequence of elements of F such that G(alpha_i) != 0 for all alpha_i in L. This function constructs the Goppa code Gamma(L, G) over K. If the degree of G(z) is r, this is an [n, k >= n - mr, d >= r + 1] code.

GRSCode(A, V, k) : [ FldFinElt ], [ FldFinElt ], RngIntElt -> Code

Let A = [alpha_1, ..., alpha_n] be a sequence of n distinct elements taken from the finite field K, and let V = [v_1, ..., v_n] be a sequence of n non-zero elements from K. Let k be a non-negative integer. Given such A, V, and k, this function constructs the generalized Reed-Solomon code GRS_k(A, V) over K. This is an [n, K <= k] code.

Example `Code_AlternantCode (H40E7)`

We construct an alternant code over GF(2) based on sequences of elements in the extension field GF(2^4) of GF(2). The parameter r is taken to be 4, so the minimum weight 6 is greater than r + 1.

> q := 2^4;
> K<w> := GF(q);
> A := [w ^ i : i in [0 .. q - 2]];
> Y := [K ! 1 : i in [0 .. q - 2]];
> r := 4;
> C := AlternantCode(A, Y, r);
> print C;
[15, 6, 6] Alternant code over GF(2)
Generator matrix:
[1 0 0 0 0 0 1 1 0 0 1 1 1 0 0]
[0 1 0 0 0 0 0 1 1 0 0 1 1 1 0]
[0 0 1 0 0 0 0 0 1 1 0 0 1 1 1]
[0 0 0 1 0 0 1 1 0 1 0 1 1 1 1]
[0 0 0 0 1 0 1 0 1 0 0 1 0 1 1]
[0 0 0 0 0 1 1 0 0 1 1 1 0 0 1]

Example `Code_BCHCode (H40E8)`

We construct a BCH code of length 13 over GF(3) and designated minimum distance 3.

> C := BCHCode(GF(3), 13, 3);   
> print C;
[13, 7, 4] BCH code (d = 3, b = 1) over GF(3)
Generator matrix:
[1 0 0 0 0 0 0 1 2 1 2 2 2]
[0 1 0 0 0 0 0 1 0 0 0 1 1]
[0 0 1 0 0 0 0 2 2 2 1 1 2]
[0 0 0 1 0 0 0 1 1 0 1 0 0]
[0 0 0 0 1 0 0 0 1 1 0 1 0]
[0 0 0 0 0 1 0 0 0 1 1 0 1]
[0 0 0 0 0 0 1 2 1 2 2 2 1]

Example `Code_GoppaCode (H40E9)`

We construct a Goppa code of length 31 over GF(2) with generator polynomial G(z) = z^3 + z + 1.

> q := 2^5;
> K<w> := FiniteField(q);
> P<z> := PolynomialRing(K);
> G := z^3 + z + 1;
> L := [w^i : i in [0 .. q - 2]];
> C := GoppaCode(L, G);
> print C;
[31, 16, 7] Goppa code (r = 3) over GF(2)
Generator matrix:
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 0 1 1 0 0 0 0 1]
[0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 0 0 1 0 1 1 0 1]
[0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 1]
[0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 1 0 1 0 1 0 1 1]
[0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 1 1 1 1 1]
[0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 1 0 1 0]
[0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 1 1 1 0 1 0]
[0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 1 0 0 1 1]
[0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 0]
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 1 0 1 0]
[0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 1 1 1 0 1 1 1 1]
[0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1]
[0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 1 0 0 1 1 1 1]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 1 0 1 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 1 1 0 0 1]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 1 1 1 1]

Example `Code_GRSCode (H40E10)`

We construct a generalized Reed-Solomon code over GF(2) based on sequences of elements in the extension field GF(2^3) of GF(2). The parameter k is taken to be 3, so the dimension 3 is at most k.

> q := 2^3;
> K<w> := GF(q);
> A := [w ^ i : i in [0 .. q - 2]];
> V := [K ! 1 : i in [0 .. q - 2]];
> k := 3;
> C := GRSCode(A, V, k);
> print C;
[7, 3, 5] GRS code over GF(2^3)
Generator matrix:
[  1   0   0 w^3   w   1 w^3]
[  0   1   0 w^6 w^6   1 w^2]
[  0   0   1 w^5 w^4   1 w^4]

Construction of Quadratic Residue Codes

QRCode(K, n) : FldFin, RngIntElt -> Code

Given a field K of cardinality q and an odd prime n such that q is a quadratic residue modulo n, construct the quadratic residue code of length n over K with generator polynomial g_0(x) = the product over the quadratic residues in L of (x - alpha^r), where alpha is a primitive n-th root of unity in an extension field L of K.

GolayCode(K, extend) : FldFin, BoolElt -> Code

If the field K is GF(2), construct the binary Golay code. If the field K is GF(3), construct the ternary Golay code. If the boolean argument extend is true, construct the extended code.

Example `Code_QuadraticResidueCode (H40E11)`

We construct a quadratic residue code of length 23 over GF(3).

> print QRCode(GF(3), 23);
[23, 12, 8] Quadratic Residue code over GF(3)
Generator matrix:
[1 0 0 0 0 0 0 0 0 0 0 0 2 2 2 1 1 0 2 0 2 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 2 2 2 1 1 0 2 0 2 0]
[0 0 1 0 0 0 0 0 0 0 0 0 0 0 2 2 2 1 1 0 2 0 2]
[0 0 0 1 0 0 0 0 0 0 0 0 2 2 2 0 0 2 0 1 2 2 0]
[0 0 0 0 1 0 0 0 0 0 0 0 0 2 2 2 0 0 2 0 1 2 2]
[0 0 0 0 0 1 0 0 0 0 0 0 2 2 1 0 0 0 2 2 2 1 2]
[0 0 0 0 0 0 1 0 0 0 0 0 2 1 1 2 1 0 2 2 1 2 1]
[0 0 0 0 0 0 0 1 0 0 0 0 1 0 2 0 1 1 1 2 0 1 2]
[0 0 0 0 0 0 0 0 1 0 0 0 2 0 2 0 1 1 0 1 1 0 1]
[0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 2 1 2 0 2 1 0]
[0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 2 1 2 0 2 1]
[0 0 0 0 0 0 0 0 0 0 0 1 1 1 2 2 0 1 0 1 0 0 2]

[Next] [Prev] [Right] [Left] [Up] [Index] [Root]