Constructions
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\ \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.
- 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: Octacode over Z4 (ex-adca47)
Run in calculator (opens in a new tab)
The octacode \(O_8\) over \({\mathbb{Z}}_4\) [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={\mathbb{Z}}_4\), 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: Code from a Matrix over a Galois Ring (ex-11a0fe)
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: Permutation Code over Z4 (ex-215ff7)
Run in calculator (opens in a new tab)
We define \(G\) to be a permutation group of degree 7 and construct the code \(C\) as the \({\mathbb{Z}}_4\)-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 \((c_1,c_2,\ldots ,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 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 \le n\), the function returns a random linear code of length \(n\) over \(R\) with \(k\) generators.
- Example: Repetition and Zero Sum Codes (ex-3c3cdf)
Run in calculator (opens in a new tab)
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:
Using the correspondence \((c_0,c_1,\ldots,c_n) \iff c_0 + c_1x + \cdots + c_nx^n\), the cyclic codes of length \(n\) over the ring \(R\) are in one-to-one correspondence with the principal ideals of \(R[x]/(x^n-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) \in 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 \(x^n - 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: Cyclic Codes over Z4 (ex-567853)
Run in calculator (opens in a new tab)
We construct some cyclic codes over \({\mathbb{Z}}_4\) by factorizing \(x^n-1\) over \({\mathbb{Z}}_4\) 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: Cyclic Code over a Galois Ring (ex-63adb5)
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]