|
|
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
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.
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| | n.
Constructs the quasi-cyclic code of length n generated by
simultaneous cyclic shifts of the
vectors in Gen.
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 | (|Gen|)
and (|Gen|/h) | n.
Constructs the quasi-cyclic code generated by simultaneous cyclic shifts of the
vectors in Gen, arranging them two dimensionally with height h.
Let k be a finite field and α a non-zero element of K. A linear code C
of length n is called a constacyclic code with shift constant α if
for each word ( x1, x2, ..., xn) in C, the vector (α xn, x1, ..., xn - 1)
is also in C. Such a code is generated by a factor f of the polynomial
xn - α, where f is monic polynomial. This intrinsic returns the
length n code generated by constacyclic shifts by α of the coefficients
of polynomial f.
Construct the quasi-twisted cyclic code of length n pasting together the
constacyclic codes with parameter α generated by the polynomials in
Gen.
Construct the quasi-twisted cyclic code generated by simultaneous
constacyclic shifts w.r.t. α of the codewords in Gen.
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 α 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.
Construct the quasi-twisted cyclic code generated by simultaneous
constacyclic shifts w.r.t. α of the vectors in Gen. Attaches the
Generator matrices of the consta-cyclic codes with parameter α
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.
Let the m factors of x n - 1 be f i(x),i=0, ..., m in any particular
order. Then we can construct a chain of polynomials
g k(x) = ∏ i=0kf i(x) such that g k(x) | 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 }
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!
BCHCode(K, n, d) : FldFin, RngIntElt, RngIntElt -> Code
Given a finite field K=Fq and positive integers n, d and b
such that gcd(n, q) = 1, we define m to be the smallest integer
such that n | (qm - 1), and α to be a primitive n-th root
of unity in the degree m extension of K, GF(qm). This function
constructs the BCH code of designated distance d as the cyclic code
with generator polynomial
g(x) = lcm{ m1(x), ..., md - 1(x)}
where mi(x) is the minimum polynomial of αb + i - 1.
The BCH code is an [n, ≥(n - m(d - 1)), ≥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.
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]
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(qm)) and let L = [α1, ..., αn]
be a sequence of elements of F such that G(αi) != 0
for all αi ∈L. This function constructs the Goppa code
Γ(L, G) over K. If the degree of G(z) is r,
this is an [n, k ≥n - mr, d ≥r + 1] code.
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> ]
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 xn - 1 over S, P and G are both coprime to xn - 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) : [ FldFinElt ], [ FldFinElt ], RngIntElt -> Code
Let A = [α1, ..., αn] be a sequence of n
distinct elements taken from the degree m extension K of
the finite field S, and let
Y = [y1, ..., yn] 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.
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]
Returns the [n, k, d] non-primitive alternant code over GF(2), where
n - mr ≤k ≤n - r and d ≥r + 1.
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(Xs - 1).
Given sequences A = [a1, ...an], W = [w1, ...ws], and
Z=[z1, ... zk], 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.
Given sequences A = [α1, ..., αn], W = [w1, ..., ws]
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 μ, construct the
Srivastava code of parameters A, W, mu, over S.
Given sequences A = [α1, ..., αn], W = [w1, ..., ws],
and Z = [z1, ... zk] 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.
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.
Given a finite field K = Fq 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 g0(x) = ∏(x - αr),
where α 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.
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.
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 | A],
where A is a circulant matrix.
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 [Gab02].
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.
Given positive integers l and m, both coprime to 2, return
a binary "twisted QR" code of length l * m.
Given a finite field K=Fq, 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.
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]
ReedSolomonCode(K, d) : FldFin, RngIntElt -> Code
Given a finite field K=Fq 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
[MS78, 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, 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 Fq 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.
Let A = [α1, ..., αn] be a sequence of n
distinct elements taken from the finite field K, and let
V = [v1, ..., vn] 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
GRSk(A, V) over K. This is an [n, k' ≤k] code.
For details see [MS78, p.303].
Given an integer N such that N=2m - 1 and a positive integer K,
construct the binary linear Justesen code of length 2mN and dimension mK.
For details see [MS78, p.307].
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]
Given a finite field GF(q = 2m), this function constructs the
[q + 1, k, q - k + 2] maximum distance separable code.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|
|