# Constructions ## General Linear Codes ### `LinearCode: 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](../../references.md#cite-wan-z4), Ex. 1.3] can be defined as follows: ```magma > Z4 := IntegerRing(4); > O8 := LinearCode [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: ```magma > O8 := LinearCode(sub [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: ```magma > R := 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: ```magma > 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. ```magma > 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: $$ (c_0,c_1,\ldots,c_{n-1},c_n), (c_n,c_0,\ldots,c_{n-2},c_{n-1}), \ldots, (c_1,c_2,\ldots,c_n,c_0) $$ 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. ```magma > Z4 := IntegerRing(4); > P := 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)$. ```magma > R := GR(4,2); > P := 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] ```