Constructions

Contents

General Linear Codes

LinearCode<R, n | L> : Rng, RngIntElt, List -> Code
Create a code as a subspace of the R-space 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 R, 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.
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.
LinearCode(A) : ModMatRngElt -> Code
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.
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 CodeRng_TernaryGolayCode (H168E1)

The octacode O8 over Z4 [Wan97, Ex. 1.3] can be defined as follows: 

> Z4 := IntegerRing(4);
> O8 := LinearCode<Z4, 8 |
>     [1,0,0,0,3,1,2,1],
>     [0,1,0,0,1,2,3,1],
>     [0,0,1,0,3,3,3,2],
>     [0,0,0,1,2,3,1,1]>;
> O8;
[8, 4, 4] Linear Code over IntegerRing(4)
Generator matrix:
[1 0 0 0 3 1 2 1]
[0 1 0 0 1 2 3 1]
[0 0 1 0 3 3 3 2]
[0 0 0 1 2 3 1 1]
Alternatively, if we want to see the code as a subspace of R(8), where R=Z4, we could proceed as follows: 

> O8 := LinearCode(sub<RSpace(Z4, 8) |
>     [1,0,0,0,3,1,2,1],
>     [0,1,0,0,1,2,3,1],
>     [0,0,1,0,3,3,3,2],
>     [0,0,0,1,2,3,1,1]>);

Example CodeRng_CodeFromMatrix (H168E2)

We define a code by constructing a matrix over GR(4, 3), and using its rowspace to generate the code: 

> R<w> := GaloisRing(4,3);
> S := [1, 1, 0, w^2, w, w + 2, 2*w^2, 2*w^2 + w + 3];
> G := Matrix(R, 2, 4, S);
> G;
[            1             1             0           w^2]
[            w         w + 2         2*w^2 2*w^2 + w + 3]
> C := LinearCode(G);
> C;
(4, 512, 3) Linear Code over GaloisRing(2, 2, 3)
Generator matrix:
[          1           1           0         w^2]
[          0           2       2*w^2 2*w^2 + 2*w]
> #C;
512

Example CodeRng_PermutationCode (H168E3)

We define G to be a permutation group of degree 7 and construct the code C as the Z4-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)
> Z4 := IntegerRing(4);
> V := RSpace(Z4, 7);
> u := V ! [1, 0, 0, 1, 0, 1, 1];
> C := PermutationCode(u, G);
> C;
[7, 6, 2] Linear Code over IntegerRing(4)
Generator matrix:
[1 0 0 1 0 1 1]
[0 1 0 1 1 1 0]
[0 0 1 0 1 1 1]
[0 0 0 2 0 0 2]
[0 0 0 0 2 0 2]
[0 0 0 0 0 2 2]

Simple Linear Codes

ZeroCode(R, n) : Rng, RngIntElt -> Code
Given a ring R and positive integer n, return the (n, 0, n) code consisting of only the zero code word. By convention the minimum weight of the zero code is n).
RepetitionCode(R, n) : Rng, RngIntElt -> Code
Given a ring R and positive integer n, return the length n code with minimum Hamming weight n, generated by the all-ones vector.
ZeroSumCode(R, n) : Rng, RngIntElt -> Code
Given a ring R and positive integer n, return the length n code over R such that for all codewords (c1, c2, ... , cn) we have ∑i ci =0 .

UniverseCode(R, n) : Rng, RngIntElt -> Code
Given a ring R and positive integer n, return the length n code with minimum Hamming weight 1, consisting of all possible codewords.
RandomLinearCode(R, n, k) : Rng, RngIntElt, RngIntElt -> Code
Given a finite ring R and positive integers n and k, such that 0 < k ≤n, the function returns a random linear code of length n over R with k generators.

Example CodeRng_simple-finite-ring (H168E4)

The repetition and zero sum codes are dual over all rings. 

> R := Integers(9);
> C1 := RepetitionCode(R, 5);
> C1;
(5, 9, 5) Linear Code over IntegerRing(9)
Generator matrix:
[1 1 1 1 1]
> C2 := ZeroSumCode(R, 5);
> C2;
(5, 6561, 2) Linear Code over IntegerRing(9)
Generator matrix:
[1 0 0 0 8]
[0 1 0 0 8]
[0 0 1 0 8]
[0 0 0 1 8]
> C1 eq Dual(C2);
true

General Cyclic Codes

Cyclic codes form an important family of linear codes over all rings. A cyclic code is one which is generated by all of the cyclic shifts of a given codeword: (c0, c1, ..., cn - 1, cn), (cn, c0, ..., cn - 2, cn - 1), ..., (c1, c2, ..., cn, c0)

Using the correspondence (c0, c1, ..., cn) iff c0 + c1x + ... + cnxn, the cyclic codes of length n over the ring R are in one-to-one correspondence with the principal ideals of R[x]/(xn - 1)R[x].

CyclicCode(u) : ModTupRngElt -> Code
Given a vector u belonging to the R-space R(n), construct the length n cyclic code generated by the right cyclic shifts of the vector u.
CyclicCode(n, g) : RngIntElt, RngUPolElt -> Code
Let R be a ring. Given a positive integer n and a univariate polynomial g(x) ∈R[x], construct the length n cyclic code generated by g(x).
CyclotomicFactors(R, n) : Rng, RngIntElt -> [RngUPolElt]
Given a Galois ring R (which is possibly an integer residue ring with a prime power modulus), and a positive integer n which is coprime to the characteristic of R, return a factorisation of xn - 1 over R.

Note that since factorisation is not necessarily unique over R, the factorisation returned is the one obtained by first factoring over the residue field of R and then performing Hensel lifting.

Example CodeRng_CyclicCode (H168E5)

We construct some cyclic codes over Z4 by factorizing xn - 1 over Z4 for n=7, 23 and using some of the irreducible factors found. 

> Z4 := IntegerRing(4);
> P<x> := PolynomialRing(Z4);
> n := 7; L := CyclotomicFactors(Z4, n); L;
[
    x + 3,
    x^3 + 2*x^2 + x + 3,
    x^3 + 3*x^2 + 2*x + 3
]
> CyclicCode(n, L[1]);
[7, 6, 2] Cyclic Code over IntegerRing(4)
Generator matrix:
[1 0 0 0 0 0 3]
[0 1 0 0 0 0 3]
[0 0 1 0 0 0 3]
[0 0 0 1 0 0 3]
[0 0 0 0 1 0 3]
[0 0 0 0 0 1 3]
> CyclicCode(n, L[2]);
[7, 4, 3] Cyclic Code over IntegerRing(4)
Generator matrix:
[1 0 0 0 3 1 2]
[0 1 0 0 2 1 1]
[0 0 1 0 1 1 3]
[0 0 0 1 3 2 3]
> CyclicCode(n, L[3]);
[7, 4, 3] Cyclic Code over IntegerRing(4)
Generator matrix:
[1 0 0 0 3 2 3]
[0 1 0 0 3 1 1]
[0 0 1 0 1 1 2]
[0 0 0 1 2 1 3]
> n := 23; L := CyclotomicFactors(Z4, n); L;
[
    x + 3,
    x^11 + 2*x^10 + 3*x^9 + 3*x^7 + 3*x^6 + 3*x^5 + 2*x^4 + x + 3,
    x^11 + 3*x^10 + 2*x^7 + x^6 + x^5 + x^4 + x^2 + 2*x + 3
]
> CyclicCode(n, L[2]);
[23, 12] Cyclic Code over IntegerRing(4)
Generator matrix:
[1 0 0 0 0 0 0 0 0 0 0 0 3 1 0 0 2 3 3 3 0 3 2]
[0 1 0 0 0 0 0 0 0 0 0 0 2 1 1 0 0 0 1 1 3 2 3]
[0 0 1 0 0 0 0 0 0 0 0 0 3 3 1 1 2 3 3 0 1 2 0]
[0 0 0 1 0 0 0 0 0 0 0 0 0 3 3 1 1 2 3 3 0 1 2]
[0 0 0 0 1 0 0 0 0 0 0 0 2 2 3 3 1 3 0 1 3 2 1]
[0 0 0 0 0 1 0 0 0 0 0 0 1 1 2 3 1 2 0 1 1 0 0]
[0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 2 3 1 2 0 1 1 0]
[0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 2 3 1 2 0 1 1]
[0 0 0 0 0 0 0 0 1 0 0 0 1 3 0 1 3 3 0 2 2 1 3]
[0 0 0 0 0 0 0 0 0 1 0 0 3 2 3 0 3 2 2 3 2 1 3]
[0 0 0 0 0 0 0 0 0 0 1 0 3 0 2 3 2 2 1 1 3 1 3]
[0 0 0 0 0 0 0 0 0 0 0 1 3 0 0 2 1 1 1 0 1 2 3]

Example CodeRng_cyclic-galois-ring (H168E6)

We create a cyclic code of length 5 over GR(4, 2). 

> R<w> := GR(4,2);
> P<x> := PolynomialRing(R);
> g := CyclotomicFactors(R, 5)[2];
> g;
x^2 + (3*w + 2)*x + 1
> C := CyclicCode(5, g);
> C;
(5, 4096, 3) Cyclic Code over GaloisRing(2, 2, 2)
Generator matrix:
[      1       0       0       1 3*w + 2]
[      0       1       0   w + 2   w + 2]
[      0       0       1 3*w + 2       1]
[Next][Prev] [Right] [Left] [Up] [Index] [Root]


Version: V2.29 of Fri Nov 28 15:14:01 AEDT 2025
Search: