|
|
Create a code as a subspace of 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 K, 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.
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]>);
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.
Suppose the code C being constructed has dimension k. The
evaluation of this constructor results in the creation of
the following objects:
- (a)
- The generator matrix G for C, created as a
k x n matrix belonging to the R-matrix space,
R(k x n).
- (b)
- The parity check matrix H for C, created as an
(n - k) x n matrix belonging to the R-matrix space,
R(n - k) x n).
Given a k x 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.
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]
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.
We define G to be a permutation group of degree 7 and construct the
code C as the F 2-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)
> 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]
Given a ring R and positive integer n, return the [n, 0, n] code
consisting of only the zero code word,
(where the minimum weight is by convention equal to n).
Given a ring R and positive integer n, return the [n, 1, n]
code over K generated by the all-ones vector.
Given a ring R and positive integer n, return the [n, n - 1, 2]
code over R such that for all codewords (c1, c2, ... , cn) we have
∑i ci =0 .
Given a ring R and positive integer n, return the [n, n, 1]
code consisting of all possible codewords.
Given a positive integer n, return the [n, n - 1, 2] code
over GF(2) such that all vectors have even weight.
This is equivalent to the zero sum code over GF(2).
Given a linear code C over GF(2), return the subcode of C
containing the vectors of even weight.
Given a finite field K and positive integers n and k, such
that 0 < k ≤n, the function returns a random linear code
of length n and dimension k over the field K. The method
employed is to successively choose random vectors from K(n)
until generators for a k-dimensional subspace have been found.
Construct the Cordaro--Wagner code of length n, This is the
2-dimensional repetition code over GF(2) of length n
and having the largest possible minimum weight.
Over any specific finite field K, the zero code of length n is
contained in every code of length n,
and similarly every code of length n is contained in the
universe code of length n. This is illustrated over GF(2)
for length 6 codes
with an arbitrary code of length 6 dimension 3.
> K := GF(2);
> U := UniverseCode(K, 6);
> U;
[6, 6, 1] Linear Code over GF(2)
> Z := ZeroCode(K, 6);
> Z;
[6, 0, 6] Linear Code over GF(2)
> R := RandomLinearCode(K, 6, 3);
> (Z subset R) and (R subset U);
true
In this section we describe how to construct three very important
families of codes: cyclic codes, Hamming codes and Reed-Muller codes.
We choose to present these very important families at this stage
since they are easily understood and they give us a nice collection
of codes for use in examples.
Many more constructions will be described in subsequent sections.
In particular, variations and generalizations of the cyclic code
construction presented here will be given.
Let K be a finite field. Given a positive integer n and a univariate
polynomial g(x) ∈K[x] of degree n - k such that g(x) | xn - 1,
construct the [n, k] cyclic code generated by g(x).
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]
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 = (qr - 1)/(q - 1).
We construct the third order Hamming code over GF(2) together with
its parity check matrix.
> 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]
Given a positive integer r, construct the [2r - 1, r, 2r - 1] binary
simplex code, which is the dual of a Hamming code.
Given positive integers r and m, where 0 ≤r ≤m,
construct the r-th order binary Reed--Muller code of length
n = 2m.
We construct the first order Reed--Muller code 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
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|
|