[Next] [Prev] [Right] [Left] [Up] [Index] [Root]
Definition of a Code

Definition of a Code

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

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 (H58E1)

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

Example Code_CodeFromMatrix (H58E2)

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]

Example Code_PermutationCode (H58E3)

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

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 positive integers r and m, where 0 <= r <= m, construct the r-th order binary Reed-Muller code of length n = 2^m.
SimplexCode(r) : RngIntElt -> Code
Given a positive integer r, construct the [2^r - 1, r, 2^(r - 1)] simplex binary code.

Example Code_HammingCode (H58E4)

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

Example Code_ReedMullerCode (H58E5)

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

Construction of Simple Linear Codes

EvenWeightCode(n) : RngIntElt -> Code
Given a positive integer n return the [n, n - 1, 2] even-weight code over GF(2).
RandomLinearCode(K, n, k) : FldFin, RngIntElt, RngIntElt -> Code
Return a random linear code of length n and dimension k over the field K.
RepetitionCode(K, n) : FldFin, RngIntElt -> Code
Given a finite field K and positive integer n return the [n, 1, n] repetition code over K.
UniverseCode(K, n) : FldFin, RngIntElt -> Code
Given a finite field K and positive integer n return the [n, n, 1] universe code over K.
ZeroCode(K, n) : FldFin, RngIntElt -> Code
Given a finite field K and positive integer n return the [n, 0, n] zero code over K.
ZeroSumCode(K, n) : FldFin, RngIntElt -> Code
Given a finite field K and positive integer n return the [n, n - 1, 2] zero-sum code over K.

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).
CyclicCode(n, R, K) : RngIntElt, [ FldFinElt ], FldFin -> Code
CyclicCode(n, R, K) : RngIntElt, { FldFinElt }, FldFin -> Code
Given a positive integer n and a set or sequence R of primitive n-th roots of unity from a field L, together with a subfield K of L, construct the cyclic code C over K of length n such that the generator polynomial for C is the polynomial of least degree having the elements of R as roots.

Example Code_CyclicCode (H58E6)

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]

Construction of BCH Codes and their Generalizations

AlternantCode(A, Y, r, S) : [ FldFinElt ], [ FldFinElt ], RngIntElt, FldFin -> Code
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.
ChienChoyCode(P, G, n, S) : RngUPolElt, RngUPolElt, RngIntElt, FldFin -> Code
Let P and G be polynomials over a finite field F, let n be an integer greater than 1, and let S be a subfield of F. Suppose also that n is coprime to the cardinality of S, F is the splitting field of x^n - 1 over S, P and G are both coprime to x^n - 1 and both have degree less than n. This function constructs the Chien-Choy generalised BCH code with parameters P, G, n over S.
FireCode(h, s, n) : RngUPolElt, RngIntElt, RngIntElt -> Code
Let K be the field GF(q). Given a polynomial h in K[X], a nonnegative integer s, and a positive integer n, this function constructs a Fire code of length n with generator polynomial h(X^s - 1).
GabidulinCode(A, W, Z, t) : [ FldFinElt ], [ FldFinElt ], [ FldFinElt ], RngIntElt -> Code
Given sequences A = [a_1, ...a_n], W = [w_1, ...w_s], and Z=[z_1, ... z_k], such that the n + s elements of A and W are distinct and the elements of Z are non-zero, together with a positive integer t, construct the Gabidulin MDS code of parameters A, W, Z, t.
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.
GeneralizedSrivastavaCode(A, W, Z, t, S) : [ FldFinElt ], [ FldFinElt ], [ FldFinElt ], RngIntElt, FldFin -> Code
Given sequences A = [alpha_1, ..., alpha_n], W = [w_1, ..., w_s], and Z = [z_1, ... z_k] of elements from the extension field K of the finite field S, such that the elements of A and Z are non-zero and the n + s elements of A and W are distinct, together with a positive integer t, construct the generalized Srivastava code of parameters A, W, Z, t, over S.
ReedSolomonCode(K, d, b) : FldFin, RngIntElt, RngIntElt -> Code
ReedSolomonCode(K, d) : FldFin, RngIntElt -> Code
Given a field K of cardinality q and a positive integer d, together with an integer b >= 0, construct the Reed-Solomon code of length n = q - 1 over K and designated distance d. If an integer b is given, the primitive element alpha is first raised to the b-th power. This is just the same as calling the function BCHCode with arguments K, n, d, and b.
ReedSolomonCode(n, d) : RngIntElt, RngIntElt -> Code
ReedSolomonCode(n, d, b) : RngIntElt, RngIntElt, RngIntElt -> Code
Given positive integers n and d, together with an integer b >= 0, such that n = q - 1 for some prime power q, construct the Reed-Solomon code of length n over the default finite field GF(q) with designated distance d. If an integer b is given, the primitive element alpha is first raised to the b-th power. This is just the same as calling the function BCHCode with arguments GF(q), n, d, and b, where q is n - 1.
SrivastavaCode(A, W, mu, S) : [ FldFinElt ], [ FldFinElt ], RngIntElt, FldFin -> Code
Given sequences A = [alpha_1, ..., alpha_n], W = [w_1, ..., w_s] of elements from the extension field K of the finite field S, such that the elements of A are non-zero and the n + s elements of A and W are distinct, together with an integer mu, construct the Srivastava code of parameters A, W, mu, over S.

Example Code_AlternantCode (H58E7)

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);
> 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 (H58E8)

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

> C := BCHCode(GF(3), 13, 3);   
> 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 (H58E9)

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);
> 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 (H58E10)

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);
> 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 (H58E11)

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

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