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
HorizontalJoinof eachGeneratorMatrixfrom theCyclicCode’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\).
> P<x> := PolynomialRing(GF(2)); > n := 7; > F := Factorization(x^n-1); > F; [ <x + 1, 1>, <x^3 + x + 1, 1>, <x^3 + x^2 + 1, 1> ] > 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\).
> n := 11; > k := GF(5); > _<x> := PolynomialRing(k); > a := k!3; > > f := Factorisation( x^n - a ); > f; [ <x + 3, 1>, <x^5 + 3*x^4 + x^3 + 3*x^2 + 3*x + 3, 1>, <x^5 + 4*x^4 + x^3 + 3*x^2 + x + 3, 1> ]
The two polynomials of degree \(5\) will give us non-trivial codes.
> 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<p, q> := 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.
> 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
> 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\).
> q := 2^5; > K<w> := FiniteField(q); > P<z> := 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\).
> q := 2^4; > K<w> := 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].
- 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).
> 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, 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, 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, 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\).
> q := 2^3; > K<w> := 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.