Construction of Codes

Subsections

• Construction of General Linear Codes
• Construction of Simple Linear Codes
• Construction of General Cyclic Codes

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

• An element of V.
• A set or sequence of elements of V.
• A sequence of n elements of R, 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) : 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 (H98E1)

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

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

> Z4 := IntegerRing(4);
> G := Matrix(Z4, 2, 4, [1,1,1,2, 3,3,1,4]);
> G;
[1 1 1 2]
[3 3 1 0]
> C := LinearCode(G);  
> C;
[4, 2, 2] Linear Code over IntegerRing(4)
Generator matrix:
[1 1 1 2]
[0 0 2 2]

Example CodeRng_PermutationCode (H98E3)

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

Construction of 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, (where the minimum weight is by convention equal to n).

RepetitionCode(R, n) : Rng, RngIntElt -> Code

Given a ring R and positive integer n, return the [n, 1, n] code over R generated by the all--ones vector.

ZeroSumCode(R, n) : Rng, 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, ... , c_n) we have sum_(i) c_i =0 .

UniverseCode(R, n) : Rng, RngIntElt -> Code

Given a ring R and positive integer n, return the [n, n, 1] code consisting of all possible codewords.

UniverseCode(R, n) : Rng, RngIntElt -> Code

Given a ring R and positive integer n, return the [n, n, 1] code consisting of all possible codewords.

Construction of General Cyclic Codes

CyclicCode(u) : ModTupRngElt -> Code

Given a vector u belonging to the R-space R^((n)), construct the [n, k] 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) in R[x] of degree n - k such that g(x) | x^n - 1, construct the [n, k] cyclic code generated by g(x).

Z4CyclotomicFactors(n) : RngIntElt -> [RngUPolElt]

Given an odd positive integer n, return the distinct irreducible factors of x^n - 1 over Z_4. These are constructed by factoring x^n - 1 over GF(2) and then applying Hensel lifting.

Example CodeRng_CyclicCode (H98E4)

> Z4 := IntegerRing(4);
> P<x> := PolynomialRing(Z4);
> n := 7; L := Z4CyclotomicFactors(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 := Z4CyclotomicFactors(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]