# Families of Linear Codes ## Cyclic and Quasicyclic 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, T, K): RngIntElt, [ FldFinElt ], FldFin -> Code` ### `CyclicCode(n, T, K): RngIntElt, { FldFinElt }, FldFin -> Code` Given a positive integer $n$ and a set or sequence $T$ of primitive $n$-th roots of unity from a finite field $L$, together with a subfield $K$ of L, construct the cyclic code $C$ over $K$ of length $n$, such that the generator polynomial for $C$ is the polynomial of least degree having the elements of $T$ as roots. ### `QuasiCyclicCode(n, Gen): RngIntElt, [ RngUPolElt ] -> Code` Constructs the quasi-cyclic code of length $n$ with generator polynomials given by the sequence of polynomials in $Gen$. Created by `HorizontalJoin` of each `GeneratorMatrix` from the `CyclicCode`’s generated by the polynomials in $Gen$. Requires that $|Gen| \mid n$. ### `QuasiCyclicCode(Gen): [ ModTupRngElt ] -> Code` Constructs the quasi-cyclic code of length $n$ generated by simultaneous cyclic shifts of the vectors in $Gen$. ### `QuasiCyclicCode(n, Gen, h): RngIntElt, [ RngUPolElt ], RngIntElt -> Code` Constructs the quasi-cyclic code of length $n$ with generator polynomials given by the sequence of polynomials in $Gen$. The `GeneratorMatrix`’s are joined $2$ dimensionally, with height $h$. Requires that $h \mid (|Gen|)$ and $(|Gen|/h) \mid n$. ### `QuasiCyclicCode(Gen, h): [ModTupRngElt], RngIntElt -> Code` Constructs the quasi-cyclic code generated by simultaneous cyclic shifts of the vectors in $Gen$, arranging them two dimensionally with height $h$. ### `ConstaCyclicCode(n, f, alpha): RngIntElt, RngUPolElt, FldFinElt -> Code` Let $k$ be a finite field and $\alpha$ a non-zero element of $K$. A linear code $C$ of length $n$ is called a *constacyclic code* with shift constant $\alpha$ if for each word $( x_1, x_2, \ldots, x_n)$ in $C$, the vector $(\alpha x_n, x_1, \ldots, x_{n-1})$ is also in $C$. Such a code is generated by a factor $f$ of the polynomial $x^n - \alpha$, where $f$ is monic polynomial. This intrinsic returns the length $n$ code generated by constacyclic shifts by $\alpha$ of the coefficients of polynomial $f$. ### `QuasiTwistedCyclicCode(n, Gen, alpha): RngIntElt, [RngUPolElt], FldFinElt -> Code` Construct the quasi-twisted cyclic code of length $n$ pasting together the constacyclic codes with parameter $\alpha$ generated by the polynomials in $Gen$. ### `QuasiTwistedCyclicCode(Gen, alpha): [ModTupRngElt], FldFinElt -> Code` Construct the quasi-twisted cyclic code generated by simultaneous constacyclic shifts w.r.t. $\alpha$ of the codewords in $Gen$. ### `QuasiTwistedCyclicCode(n, Gen, alpha, h): RngIntElt, [RngUPolElt], FldFinElt, RngIntElt -> Code` Constructs the quasi-twisted cyclic code of length $n$ with generator polynomials given by $Gen$. Attaches the Generator matrices of the consta-cyclic codes with parameter $\alpha$ generated by $Gen$ 2-dimensionally, stacking with height $h$. Requires that $\#Gen$ be a multiple of $h$, and that $n$ be a multiple of $\#Gen/h$. ### `QuasiTwistedCyclicCode(Gen, alpha, h): [ModTupRngElt], FldFinElt, RngIntElt -> Code` Construct the quasi-twisted cyclic code generated by simultaneous constacyclic shifts w.r.t. $\alpha$ of the vectors in $Gen$. Attaches the Generator matrices of the consta-cyclic codes with parameter $\alpha$ generated by $Gen$ 2-dimensionally, stacking with height $h$. Requires that $\#Gen$ be a multiple of $h$, and that $n$ be a multiple of $\#Gen/h$. ### `Example: Chain Cyclic (ex-03b862)` Let the $m$ factors of $x^n-1$ be $f_i(x)$,$i=0, \ldots, m$ in any particular order. Then we can construct a chain of polynomials $g_k(x) = \prod_{i=0}^{k}f_i(x)$ such that $g_k(x) \mid g_{k+1}(x)$. This chain of polynomials will generate a nested chain of cyclic codes of length $n$, which is illustrated here for $n=7$. ```magma > P := PolynomialRing(GF(2)); > n := 7; > F := Factorization(x^n-1); > F; [ , , ] > Gens := [ &*[F[i][1]:i in [1..k]] : k in [1..#F] ]; > Gens; [ x + 1, x^4 + x^3 + x^2 + 1, x^7 + 1 ] > Codes := [ CyclicCode(n, Gens[k]) : k in [1..#Gens] ]; > Codes; [ [7, 6, 2] Cyclic Code over GF(2) Generator matrix: [1 0 0 0 0 0 1] [0 1 0 0 0 0 1] [0 0 1 0 0 0 1] [0 0 0 1 0 0 1] [0 0 0 0 1 0 1] [0 0 0 0 0 1 1], [7, 3, 4] Cyclic Code over GF(2) Generator matrix: [1 0 0 1 0 1 1] [0 1 0 1 1 1 0] [0 0 1 0 1 1 1], [7, 0, 7] Cyclic Code over GF(2) ] > { Codes[k+1] subset Codes[k] : k in [1..#Codes-1] }; { true } ``` ### `Example: Constacyclic (ex-975a7d)` We construct a constacyclic code $C_1$ of length $11$ over $GF(5)$ with shift constant $a = 3$. In order to find a suitable generator polynomial $f$ we first find the factors of the polynomial $x^n -a$. ```magma > n := 11; > k := GF(5); > _ := PolynomialRing(k); > a := k!3; > > f := Factorisation( x^n - a ); > f; [ , , ] ``` The two polynomials of degree $5$ will give us non-trivial codes. ```magma > f1 := f[2][1]; > C1 := ConstaCyclicCode(n, f1, a); [11, 6, 5] Constacyclic by 3 Linear Code over GF(5) [Generator matrix: [1 0 0 0 0 0 1 1 1 2 1] [0 1 0 0 0 0 2 3 3 0 4] [0 0 1 0 0 0 3 0 1 4 3] [0 0 0 1 0 0 1 4 1 3 0] [0 0 0 0 1 0 0 1 4 1 3] [0 0 0 0 0 1 1 1 2 1 2] > E := WeightEnumerator(C1); p^11 + 220*p^6*q^5 + 528*p^5*q^6 + 1980*p^4*q^7 + 2860*p^3*q^8 + 5280*p^2*q^9 + 3344*p*q^10 + 1412*q^11 ``` We now take the second polynomial of degree $5$ and construct the constacyclic code it defines. ```magma > f2 := f[3][1]; > C2 := ConstaCyclicCode(n, f2, a); > iseq := IsEquivalent( C1, C2); iseq; {true} ``` Not unexpectably they define equivalent codes! ## BCH Codes and their Generalizations ### `BCHCode(K, n, d, b): FldFin, RngIntElt, RngIntElt, RngIntElt -> Code` ### `BCHCode(K, n, d): FldFin, RngIntElt, RngIntElt -> Code` Given a finite field $K=F_q$ and positive integers $n$, $d$ and $b$ such that $\gcd(n, q) = 1$, we define $m$ to be the smallest integer such that $n \mid (q^m-1)$, and $\alpha$ to be a primitive $n$-th root of unity in the degree $m$ extension of $K$, $GF(q^m)$. This function constructs the BCH code of designated distance $d$ as the cyclic code with generator polynomial $$ g(x) = {\operatorname{lcm}}\{ m_1(x), \cdots, m_{d-1}(x)\} $$ where $m_i(x)$ is the minimum polynomial of $\alpha^{b+i-1}$. The BCH code is an $[n,\geq (n - m(d - 1)),\geq d]$ code over $K$. If $b$ is omitted its value is taken to be $1$, in which case the corresponding code is a *narrow sense* BCH code. ### `Example: BCH Code (ex-4d1633)` We construct a BCH code of length 13 over GF(3) and designated minimum distance 3 ```magma > C := BCHCode(GF(3), 13, 3); > C; [13, 7, 4] BCH code (d = 3, b = 1) over GF(3) Generator matrix: [1 0 0 0 0 0 0 1 2 1 2 2 2] [0 1 0 0 0 0 0 1 0 0 0 1 1] [0 0 1 0 0 0 0 2 2 2 1 1 2] [0 0 0 1 0 0 0 1 1 0 1 0 0] [0 0 0 0 1 0 0 0 1 1 0 1 0] [0 0 0 0 0 1 0 0 0 1 1 0 1] [0 0 0 0 0 0 1 2 1 2 2 2 1] ``` ### `GoppaCode(L, G): [ FldFinElt ], RngUPolElt -> Code` Let $K$ be the field $GF(q)$, let $G(z) = G$ be a polynomial defined over the degree $m$ extension field $F$ of $K$ (i.e. the field $GF(q^m)$) and let $L = [\alpha_1, \ldots, \alpha_n]$ be a sequence of elements of $F$ such that $G(\alpha_i) \neq 0$ for all $\alpha_i \in L$. This function constructs the Goppa code $\Gamma(L, G)$ over $K$. If the degree of $G(z)$ is $r$, this is an $[n, k \geq n - mr, d \geq r + 1]$ code. ### `Example: Goppa Code (ex-150eaa)` We construct a Goppa code of length 31 over GF(2) with generator polynomial $G(z) = z^3 + z + 1$. ```magma > q := 2^5; > K := FiniteField(q); > P := PolynomialRing(K); > G := z^3 + z + 1; > L := [w^i : i in [0 .. q - 2]]; > C := GoppaCode(L, G); > C:Minimal; [31, 16, 7] Goppa code (r = 3) over GF(2) > WeightDistribution(C); [ <0, 1>, <7, 105>, <8, 295>, <9, 570>, <10, 1333>, <11, 2626>, <12, 4250>, <13, 6270>, <14, 8150>, <15, 9188>, <16, 9193>, <17, 8090>, <18, 6240>, <19, 4270>, <20, 2590>, <21, 1418>, <22, 650>, <23, 195>, <24, 55>, <25, 36>, <26, 11> ] ``` ### `ChienChoyCode(P, G, n, S): RngUPolElt, RngUPolElt, RngIntElt, FldFin -> Code` Let $P$ and $G$ be polynomials over a finite field $F$, let $n$ be an integer greater than one, and let $S$ be a subfield of $F$. Suppose also that $n$ is coprime to the cardinality of $S$, $F$ is the splitting field of $x^n - 1$ over $S$, $P$ and $G$ are both coprime to $x^n - 1$ and both have degree less than $n$. This function constructs the Chien-Choy generalised BCH code with parameters $P$, $G$, $n$ over $S$. ### `AlternantCode(A, Y, r, S): [ FldFinElt ], [ FldFinElt ], RngIntElt, FldFin -> Code` ### `AlternantCode(A, Y, r): [ FldFinElt ], [ FldFinElt ], RngIntElt -> Code` Let $A = [\alpha_1, \ldots, \alpha_n]$ be a sequence of $n$ distinct elements taken from the degree $m$ extension $K$ of the finite field $S$, and let $Y = [y_1, \ldots, y_n]$ be a sequence of $n$ non-zero elements from $K$. Let $r$ be a positive integer. Given such $A$, $Y$, $r$, and $S$, this function constructs the alternant code $A(A, Y)$ over $S$. This is an $[n, k \geq n - mr, d \geq r + 1]$ code. If $S$ is omitted, $S$ is taken to be the prime subfield of $K$. ### `Example: Alternant Code (ex-c9dd03)` We construct an alternant code over GF(2) based on sequences of elements in the extension field GF($2^4$) of GF(2). The parameter $r$ is taken to be 4, so the minimum weight 6 is greater than $r + 1$. ```magma > q := 2^4; > K := GF(q); > A := [w ^ i : i in [0 .. q - 2]]; > Y := [K ! 1 : i in [0 .. q - 2]]; > r := 4; > C := AlternantCode(A, Y, r); > C; [15, 6, 6] Alternant code over GF(2) Generator matrix: [1 0 0 0 0 0 1 1 0 0 1 1 1 0 0] [0 1 0 0 0 0 0 1 1 0 0 1 1 1 0] [0 0 1 0 0 0 0 0 1 1 0 0 1 1 1] [0 0 0 1 0 0 1 1 0 1 0 1 1 1 1] [0 0 0 0 1 0 1 0 1 0 0 1 0 1 1] [0 0 0 0 0 1 1 0 0 1 1 1 0 0 1] ``` ### `NonPrimitiveAlternantCode(n, m, r): RngIntElt, RngIntElt, RngIntElt -> Code` Returns the $[n,k,d]$ non-primitive alternant code over ${\bf F}_{2}$, where $n-mr \le k \le n-r$ and $d \ge r+1$. ### `FireCode(h, s, n): RngUPolElt, RngIntElt, RngIntElt -> Code` Let $K$ be the field $GF(q)$. Given a polynomial $h$ in $K$[X], a nonnegative integer $s$, and a positive integer $n$, this function constructs a Fire code of length $n$ with generator polynomial $h(X^s - 1)$. ### `GabidulinCode(A, W, Z, t): [ FldFinElt ], [ FldFinElt ], [ FldFinElt ], RngIntElt -> Code` Given sequences $A = [a_1,...a_n]$, $W = [w_1,...w_s]$, and $Z=[z_1, ... z_k]$, such that the $n + s$ elements of $A$ and $W$ are distinct and the elements of $Z$ are non-zero, together with a positive integer $t$, construct the Gabidulin MDS code with parameters $A, W, Z, t$. ### `SrivastavaCode(A, W, mu, S): [ FldFinElt ], [ FldFinElt ], RngIntElt, FldFin -> Code` Given sequences $A = [\alpha_1, ..., \alpha_n]$, $W = [w_1, ..., w_s]$ of elements from the extension field $K$ of the finite field $S$, such that the elements of $A$ are non-zero and the $n + s$ elements of $A$ and $W$ are distinct, together with an integer $\mu$, construct the Srivastava code of parameters $A$, $W$, $mu$, over $S$. ### `GeneralizedSrivastavaCode(A, W, Z, t, S): [ FldFinElt ], [ FldFinElt ], [ FldFinElt ], RngIntElt, FldFin -> Code` Given sequences $A = [\alpha_1, ..., \alpha_n]$, $W = [w_1, ..., w_s]$, and $Z = [z_1, ... z_k]$ of elements from the extension field $K$ of the finite field $S$, such that the elements of $A$ and $Z$ are non-zero and the $n + s$ elements of $A$ and $W$ are distinct, together with a positive integer $t$, construct the generalized Srivastava code with parameters $A$, $W$, $Z$, $t$, over $S$. ## Quadratic Residue Codes and their Generalizations If $p$ is an odd prime, the *quadratic residues modulo* $p$ consist of the set of non-zero squares modulo $p$ while the set of non-squares modulo $p$ are termed the *quadratic nonresidues modulo* $p$. ### `QRCode(K, n): FldFin, RngIntElt -> Code` Given a finite field $K = F_q$ and an odd prime $n$ such that $q$ is a quadratic residue modulo $n$, this function returns the quadratic residue code of length $n$ over $K$. This corresponds to the cyclic code with generator polynomial $g_0(x) = \prod (x - \alpha^r)$, where $\alpha$ is a primitive $n$-th root of unity in some extension field of $K$, and the product is taken over all quadratic residues modulo $p$. ### `GolayCode(K, ext): FldFin, BoolElt -> Code` If the field $K$ is $GF(2)$, construct the binary Golay code. If the field $K$ is $GF(3)$, construct the ternary Golay code. If the boolean argument $ext$ is `true`, construct the extended code in each case. ### `DoublyCirculantQRCode(p): RngIntElt -> Code` Given an odd prime $p$, this function returns the doubly circulant binary $[2p, p]$ code based on quadratic residues modulo $p$. A doubly circulant code has generator matrix of the form $[I \mid A]$, where $A$ is a circulant matrix. ### `DoublyCirculantQRCodeGF4(m, a): RngIntElt, RngElt -> Code` Given a prime power $m$ that is greater than $2$ and an integer $a$ that is either $0$ or $1$, return a $[2m, m]$ doubly circulant linear code over GF(4). For details see [[Gaborit, 2002](../../references.md#cite-gaborit02)]. ### `BorderedDoublyCirculantQRCode(p, a, b): RngIntElt, RngElt, RngElt -> Code` Given an odd prime $p$ and integers $a$ and $b$, this function returns the bordered doubly circulant binary $[2p+1, p+1]$ code based on quadratic residues modulo $p$. The construction is similar to that of a doubly circulant code except that the first $p$ rows are extended by $a$ mod $2$ while the $p+1$-th row is extended by $b$ mod $2$. ### `TwistedQRCode(l, m): RngIntElt, RngIntElt -> Code` Given positive integers $l$ and $m$, both coprime to $2$, return a binary “twisted QR” code of length $l*m$. ### `PowerResidueCode(K, n, p): FldFin, RngIntElt, RngIntElt -> Code` Given a finite field $K=F_q$, a positive integer $n$ and a prime $p$ such that $q$ is a $p$-th power residue modulo $n$, construct the $p$-th power residue code of length $n$. ### `Example: Quadratic Residue Code (ex-6c6e7c)` We construct a quadratic residue code of length 23 over GF(3). ```magma > QRCode(GF(3), 23); [23, 12, 8] Quadratic Residue code over GF(3) Generator matrix: [1 0 0 0 0 0 0 0 0 0 0 0 2 2 2 1 1 0 2 0 2 0 0] [0 1 0 0 0 0 0 0 0 0 0 0 0 2 2 2 1 1 0 2 0 2 0] [0 0 1 0 0 0 0 0 0 0 0 0 0 0 2 2 2 1 1 0 2 0 2] [0 0 0 1 0 0 0 0 0 0 0 0 2 2 2 0 0 2 0 1 2 2 0] [0 0 0 0 1 0 0 0 0 0 0 0 0 2 2 2 0 0 2 0 1 2 2] [0 0 0 0 0 1 0 0 0 0 0 0 2 2 1 0 0 0 2 2 2 1 2] [0 0 0 0 0 0 1 0 0 0 0 0 2 1 1 2 1 0 2 2 1 2 1] [0 0 0 0 0 0 0 1 0 0 0 0 1 0 2 0 1 1 1 2 0 1 2] [0 0 0 0 0 0 0 0 1 0 0 0 2 0 2 0 1 1 0 1 1 0 1] [0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 2 1 2 0 2 1 0] [0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 2 1 2 0 2 1] [0 0 0 0 0 0 0 0 0 0 0 1 1 1 2 2 0 1 0 1 0 0 2] ``` ## Reed–Solomon and Justesen Codes ### `ReedSolomonCode(K, d, b): FldFin, RngIntElt, RngIntElt -> Code` ### `ReedSolomonCode(K, d): FldFin, RngIntElt -> Code` Given a finite field $K=F_q$ and a positive integer $d$, return the Reed–Solomon code of length $n=q-1$ with design distance $d$. This corresponds to `BCHCode(K, q-1, d)`. For details see [[MacWilliams and Sloane, 1978](../../references.md#cite-sloane), p.294]. If $b$ is given as a non-negative integer then the primitive element is first raised to the $b$-th power. ### `ReedSolomonCode(n, d): RngIntElt, RngIntElt -> Code` ### `ReedSolomonCode(n, d, b): RngIntElt, RngIntElt, RngIntElt -> Code` Given an integer $n$ such that $q=n+1$ is a prime power, and a positive integer $d$, return the Reed–Solomon code over $F_q$ of length $n$ and designed minimum distance $d$. If $b$ is given as a non-negative integer then the primitive element is first raised to the $b$-th power. ### `GRSCode(A, V, k): [ FldFinElt ], [ FldFinElt ], RngIntElt -> Code` Let $A = [\alpha_1, \ldots, \alpha_n]$ be a sequence of $n$ distinct elements taken from the finite field $K$, and let $V = [v_1, \ldots, v_n]$ be a sequence of $n$ non-zero elements from $K$. Let $k$ be a non-negative integer. Given such $A$, $V$, and $k$, this function constructs the generalized Reed–Solomon code $GRS_k(A, V)$ over $K$. This is an $[n, k' \leq k]$ code. For details see [[MacWilliams and Sloane, 1978](../../references.md#cite-sloane), p.303]. ### `JustesenCode(N, K): Code, FldFinElt, RngIntElt -> Code` Given an integer $N$ such that $N=2^m-1$ and a positive integer $K$, construct the binary linear Justesen code of length $2mN$ and dimension mK. For details see [[MacWilliams and Sloane, 1978](../../references.md#cite-sloane), p.307]. ### `Example: GRS Code (ex-6976f5)` We construct a generalized Reed–Solomon code over GF(2) based on sequences of elements in the extension field GF($2^3$) of GF(2). The parameter $k$ is taken to be 3, so the dimension 3 is at most $k$. ```magma > q := 2^3; > K := GF(q); > A := [w ^ i : i in [0 .. q - 2]]; > V := [K ! 1 : i in [0 .. q - 2]]; > k := 3; > C := GRSCode(A, V, k); [7, 3, 5] GRS code over GF(2^3) Generator matrix: [ 1 0 0 w^3 w 1 w^3] [ 0 1 0 w^6 w^6 1 w^2] [ 0 0 1 w^5 w^4 1 w^4] ``` ## Maximum Distance Separable Codes ### `MDSCode(K, k): FldFin, RngIntElt -> Code` Given a finite field $GF(q = 2^m)$, this function constructs the $[q + 1,k,q - k + 2]$ maximum distance separable code.