[Next] [Prev] [Right] [Left] [Up] [Index] [Root]
Definition of a Code
Definition of a Code
Subsections
Construction of General Linear Codes
LinearCode<K, n | L> : FldFin, RngIntElt, List -> Code
Create a code as a subspace of V = K^((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:
- An element of V.
- A set or sequence of elements of V.
- A sequence of n elements of K, defining an element of V.
- A set or sequence of sequences of type (c).
- A subspace of V.
- A set or sequence of subspaces of V.
LinearCode(U) : ModTupFld -> Code
Let V be the K-space K^((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.
Suppose the code C being constructed has dimension k. The
evaluation of this constructor results in the creation of
the following objects:
- The K-matrix space Hom(U, V), where U is the
k-dimensional vector space of n-tuples over K.
- The K-matrix space Hom(V, U), where U is as in (a).
- The generator matrix G for C, created as an
element of Hom(U, V).
- The parity check matrix H for C, created as an
element of Hom(V, U).
LinearCode(A) : ModMatFldElt -> Code
Given a matrix A belonging to Hom(U, V), where U is a
k-dimensional K-space and V is an n-dimensional
K-space, construct the linear code generated by the rows
of A. Note that we do not assume that the rank of A is
k. The effect of this constructor is otherwise identical
to that described above.
PermutationCode(u, G) : ModTupFldElt, 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 field K, 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 Code_TernaryGolayCode (H58E1)
We define the ternary Golay code as a six-dimensional subspace of
the vector space K^((11)), where K is GF(3).
The ternary Golay code could be defined in a single statement as follows:
> K := FiniteField(3);
> C := LinearCode<K, 11 |
> [1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1], [0, 1, 0, 0, 0, 0, 0, 1, 2, 2, 1],
> [0, 0, 1, 0, 0, 0, 1, 0, 1, 2, 2], [0, 0, 0, 1, 0, 0, 2, 1, 0, 1, 2],
> [0, 0, 0, 0, 1, 0, 2, 2, 1, 0, 1], [0, 0, 0, 0, 0, 1, 1, 2, 2, 1, 0]>;
Alternatively, if we want to see the code as a subspace of K^((11)),
we would proceed as follows:
> K := FiniteField(3);
> K11 := VectorSpace(K, 11);
> C := LinearCode(sub<K11 |
> [1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1], [0, 1, 0, 0, 0, 0, 0, 1, 2, 2, 1],
> [0, 0, 1, 0, 0, 0, 1, 0, 1, 2, 2], [0, 0, 0, 1, 0, 0, 2, 1, 0, 1, 2],
> [0, 0, 0, 0, 1, 0, 2, 2, 1, 0, 1], [0, 0, 0, 0, 0, 1, 1, 2, 2, 1, 0]>);
Example Code_CodeFromMatrix (H58E2)
We define a code by constructing a matrix in a K-matrix space and using
its row space to generate the code:
> M := KMatrixSpace(FiniteField(5), 2, 4);
> G := M ! [1,1,1,2, 3,2,1,4];
> G;
[1 1 1 2]
[3 2 1 4]
> C := LinearCode(G);
> C;
[4, 2, 2] Linear Code over GF(5)
Generator matrix:
[1 0 4 0]
[0 1 2 2]
Example Code_PermutationCode (H58E3)
We set G to be a permutation group of degree 7 and set C to be the code
over the finite field with 2 elements 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)
> V := VectorSpace(GF(2), 7);
> u := V ! [1, 0, 0, 1, 0, 1, 1];
> C := PermutationCode(u, G);
> C;
[7, 3, 4] Linear 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]
Construction of Standard Linear Codes
HammingCode(K, r) : FldFin, RngIntElt -> Code
Given a positive integer r, and a finite field K of
cardinality q, construct the r-th order Hamming code
over K of cardinality q. This code has length
n = (q^r - 1)/(q - 1).
ReedMullerCode(r, m) : RngIntElt, RngIntElt -> Code
Given positive integers r and m, where 0 <= r <= m,
construct the r-th order binary Reed-Muller code of length
n = 2^m.
SimplexCode(r) : RngIntElt -> Code
Given a positive integer r, construct the [2^r - 1, r, 2^(r - 1)]
simplex binary code.
Example Code_HammingCode (H58E4)
We construct the third order Hamming code over GF(2) and check
that its parity check matrix is as expected.
> H := HammingCode(FiniteField(2), 3);
> H;
[7, 4, 3] Hamming code (r = 3) over GF(2)
Generator matrix:
[1 0 0 0 0 1 1]
[0 1 0 0 1 1 0]
[0 0 1 0 1 0 1]
[0 0 0 1 1 1 1]
> ParityCheckMatrix(H);
[1 0 1 0 1 1 0]
[0 1 1 0 0 1 1]
[0 0 0 1 1 1 1]
Example Code_ReedMullerCode (H58E5)
We construct the first order Reed-Muller of length 16 and count
the number of pairs of vectors whose components are orthogonal.
> R := ReedMullerCode(1, 4);
> R;
[16, 5, 8] Reed-Muller Code (r = 1, m = 4) over GF(2)
Generator matrix:
[1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1]
[0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
[0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1]
[0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1]
[0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1]
> #{ <v, w>: v, w in R | IsZero(InnerProduct(v, w)) };
1024
Construction of Simple Linear Codes
EvenWeightCode(n) : RngIntElt -> Code
Given a positive integer n return the [n, n - 1, 2]
even-weight code over GF(2).
RandomLinearCode(K, n, k) : FldFin, RngIntElt, RngIntElt -> Code
Return a random linear code of length n and dimension k over the field K.
RepetitionCode(K, n) : FldFin, RngIntElt -> Code
Given a finite field K and positive integer n return the [n, 1, n]
repetition code over K.
UniverseCode(K, n) : FldFin, RngIntElt -> Code
Given a finite field K and positive integer n return the [n, n, 1]
universe code over K.
ZeroCode(K, n) : FldFin, RngIntElt -> Code
Given a finite field K and positive integer n return the [n, 0, n]
zero code over K.
ZeroSumCode(K, n) : FldFin, RngIntElt -> Code
Given a finite field K and positive integer n return the [n, n - 1, 2]
zero-sum code over K.
Construction of General Cyclic Codes
CyclicCode(u) : ModTupFldElt -> Code
Given a vector u belonging to the K-space K^((n)),
construct the [n, k] cyclic code generated by the
right cyclic shifts of the vector u.
CyclicCode(n, g) : RngIntElt, RngUPolElt -> Code
Let K be a finite field. Given a positive integer n and a univariate
polynomial g(x) in K[x] of degree n - k such that g(x) | x^n - 1,
construct the [n, k] cyclic code generated by g(x).
CyclicCode(n, R, K) : RngIntElt, [ FldFinElt ], FldFin -> Code
CyclicCode(n, R, K) : RngIntElt, { FldFinElt }, FldFin -> Code
Given a positive integer n and a set or sequence R of primitive n-th
roots of unity from a 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 R as roots.
Example Code_CyclicCode (H58E6)
We construct the length 23 Golay code over GF(2) as a cyclic code by
factorizing the polynomial x^(23) - 1 over GF(2) and constructing
the cyclic code generated by one of the factors of degree 11.
> P<x> := PolynomialRing(FiniteField(2));
> F := Factorization(x^23 - 1);
> F;
[
<x + 1, 1>,
<x^11 + x^9 + x^7 + x^6 + x^5 + x + 1, 1>,
<x^11 + x^10 + x^6 + x^5 + x^4 + x^2 + 1, 1>
]
> CyclicCode(23, F[2][1]);
[23, 12, 7] Cyclic Code over GF(2)
Generator matrix:
[1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1]
[0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 0 0]
[0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 0]
[0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1]
[0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 1 1 0 0]
[0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 1 1 0]
[0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 1 1]
[0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 1 1 1 0 0 0 1 1]
[0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1]
[0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1]
[0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 0 1]
Construction of BCH Codes and their Generalizations
AlternantCode(A, Y, r, S) : [ FldFinElt ], [ FldFinElt ], RngIntElt, FldFin -> Code
AlternantCode(A, Y, r) : [ FldFinElt ], [ FldFinElt ], RngIntElt -> Code
Let A = [alpha_1, ..., 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, ..., 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 >= n - mr, d >= r + 1] code.
If S is omitted, S is taken to be the prime subfield of K.
BCHCode(K, n, d, b) : FldFin, RngIntElt, RngIntElt, RngIntElt -> Code
BCHCode(K, n, d) : FldFin, RngIntElt, RngIntElt -> Code
Let K be the field GF(q) and let alpha be a primitive
n-th root of unity in the degree m extension of K (i.e.
the field GF(q^m)) where n satisfies the condition
gcd(n, q) = 1. Given a positive integer d, and an integer
b >= 1, this function constructs the BCH code of designated
distance d having generator polynomial
g(x) = lcm{ m_1(x), ..., m_(d - 1)}
where m_i(x) is the minimum polynomial of alpha^(b + i - 1),
for i = 1, ..., d - 1. If the parameter b is omitted, its
value is taken to be one. The BCH code is an
[n, k >= n - m(d - 1), D >= d] code over K.
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 1, 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.
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 of parameters A, W, Z, t.
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, ..., alpha_n]
be a sequence of elements of F such that G(alpha_i) != 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 >= n - mr, d >= r + 1] code.
GRSCode(A, V, k) : [ FldFinElt ], [ FldFinElt ], RngIntElt -> Code
Let A = [alpha_1, ..., alpha_n] be a sequence of n
distinct elements taken from the finite field K, and let
V = [v_1, ..., 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' <= k] code.
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 of parameters A, W, Z,
t, over S.
ReedSolomonCode(K, d, b) : FldFin, RngIntElt, RngIntElt -> Code
ReedSolomonCode(K, d) : FldFin, RngIntElt -> Code
Given a field K of cardinality q and a positive integer d, together with
an integer b >= 0, construct the Reed-Solomon code of length n = q - 1
over K and designated distance d. If an integer b is given, the primitive
element alpha is first raised to the b-th power. This is just the same
as calling the function BCHCode with arguments K, n, d, and
b.
ReedSolomonCode(n, d) : RngIntElt, RngIntElt -> Code
ReedSolomonCode(n, d, b) : RngIntElt, RngIntElt, RngIntElt -> Code
Given positive integers n and d, together with
an integer b >= 0, such that n = q - 1 for some prime power q,
construct the Reed-Solomon code of length n over the default finite
field GF(q) with designated distance d. If an integer b is given,
the primitive element alpha is first raised to the b-th power. This is
just the same as calling the function BCHCode with arguments
GF(q), n, d, and b, where q is n - 1.
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.
Example Code_AlternantCode (H58E7)
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]
Example Code_BCHCode (H58E8)
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]
Example Code_GoppaCode (H58E9)
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;
[31, 16, 7] Goppa code (r = 3) over GF(2)
Generator matrix:
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 0 1 1 0 0 0 0 1]
[0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 0 0 1 0 1 1 0 1]
[0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 1]
[0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 1 0 1 0 1 0 1 1]
[0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 1 1 1 1 1]
[0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 1 0 1 0]
[0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 1 1 1 0 1 0]
[0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 1 0 0 1 1]
[0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 0]
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 1 0 1 0]
[0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 1 1 1 0 1 1 1 1]
[0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1]
[0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 1 0 0 1 1 1 1]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 1 0 1 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 1 1 0 0 1]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 1 1 1 1]
Example Code_GRSCode (H58E10)
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);
> C;
[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]
Construction of Quadratic Residue Codes
QRCode(K, n) : FldFin, RngIntElt -> Code
Given a field K of cardinality q and an odd prime n such
that q is a quadratic residue modulo n, construct the
quadratic residue code of length n over K with generator
polynomial
g_0(x) = the product over the quadratic residues in L of
(x - alpha^r), where alpha is a primitive n-th root of unity in an
extension field L of K.
GolayCode(K, extend) : 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 extend is true,
construct the extended code.
Example Code_QuadraticResidueCode (H58E11)
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]
[Next] [Prev] [Right] [Left] [Up] [Index] [Root]