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: Ternary Golay Code (ex-adca47)#
The octacode \(O_8\) over \({\mathbb{Z}}_4\) [Wan, 1997, 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 Matrix (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 (ex-215ff7)#
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: Simple Finite Ring (ex-3c3cdf)#
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 Code (ex-567853)#
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 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]