[Next] [Prev] [Right] [Left] [Up] [Index] [Root]
Structural Properties of Codes
Structural Properties of Codes
Subsections
The Minimum Distance and Weight
MinimumDistance(C) : Code -> RngIntElt
Determine the minimum distance of the code C. By setting the verbose
flag "Code", information during the computation can be obtained.
For linear codes, this is just the same as the minimum weight of course.
MinimumWeight(C) : Code -> RngIntElt
Determine the minimum weight of the words belonging to the code C.
By setting the verbose flag "Code", information during the computation
can be obtained.
VerifyMinimumDistance(C, d) : Code, RngIntElt -> BoolElt, RngIntElt, BoolElt
Return true if and only if the code C has minimum distance at least d.
In either
case, return also the smallest distance d' encountered and return
also whether d' is known to be the true minimum distance. Thus the true
minimum distance will be less than or equal to d' and also d
will be the true minimum distance if the third return value is true and d'=d.
For linear codes, this function is just the same as VerifyMinimumWeight
of course.
VerifyMinimumWeight(C, d) : Code, RngIntElt -> BoolElt, RngIntElt, BoolElt
Return true if and only if the code C has minimum weight at least d.
In either
case, return also the smallest weight d' encountered and return
also whether d' is known to be the true minimum weight. Thus the true
minimum weight will be less than or equal to d' and also d
will be the true minimum weight if the third return value is true and d'=d.
MinimumWords(C) : Code -> { ModTupFldElt }
The set of words of the code C having minimum weight.
The Weight Distribution
WeightDistribution(C) : Code -> [ <RngIntElt, RngIntElt> ]
Determine the weight distribution for the code C. The
distribution is returned in the form of a sequence of tuples,
where the i-th tuple contains the i-th weight, w_i say,
and the number of codewords having weight w_i.
WeightDistribution(C, u) : Code, ModTupFldElt -> [ <RngIntElt, RngIntElt> ]
Determine the weight distribution of the coset C + u of the
linear code C. The distribution is returned in the form of a
sequence of tuples, where the i-th tuple contains the i-th
weight, w_i say, and the number of codewords having weight
w_i.
DualWeightDistribution(C) : Code -> [ <RngIntElt, RngIntElt> ]
The weight distribution of the dual code of C (see WeightDistribution).
The MacWilliams Transform
MacWilliamsTransform(n, k, q, W) : RngIntElt, RngIntElt, RngIntElt, [ <RngIntElt, RngIntElt> ] -> [ <RngIntElt, RngIntElt> ]
Let C be a hypothetical [n, k] linear code over a finite field of
cardinality q. Let W be the weight distribution of C (in the form as
returned from the function WeightDistribution). This function applies the
MacWilliams transform to W to obtain the weight distribution W' of the
dual code of C. The transform is a combinatorial algorithm based on n, k,
q and W alone. Thus C itself need not exist of course---the function
simply manipulates the integers given to it. Furthermore, if W is not
the weight distribution of an actual code, the result W' will be meaningless
and even negative weights may be returned.
MacWilliamsTransform(n, k, K, W) : RngIntElt, RngIntElt, FldFin, RngMPol -> RngMPol
Let C be a hypothetical [n, k] linear code over a finite field K
W be the complete weight enumerator of C (in the form as
returned from the function CompleteWeightEnumerator).
This function applies the
MacWilliams transform to W to obtain the complete weight
enumerator W' of the
dual code of C. The transform is a combinatorial algorithm based on K,
n, k, and W alone.
Thus C itself need not exist of course---the function
simply manipulates the polynomial given to it. Furthermore, if W is not
the weight distribution of an actual code, the result W' will be meaningless.
The Weight Enumerator
WeightEnumerator(C): Code -> RngMPolElt
The (Hamming) weight enumerator W_C(x, y) for the linear code C.
The weight enumerator is the sum over u in C of (x^(n - wt(u))y^(wt(u))).
WeightEnumerator(C, u): Code, ModTupFldElt -> RngMPolElt
The (Hamming) weight enumerator W_(C + u)(x, y) for the coset C + u.
CompleteWeightEnumerator(C): Code -> RngMPolElt
The complete weight enumerator ( W)_C(z_0, ..., z_(q - 1))
for the linear code C where q is the size of the alphabet K of C.
Let the q elements of K be denoted by
omega _0, ..., omega _(q - 1). If K is a prime field, we let
omega _i be i (i.e. take the natural representation of each number).
If K is a non-prime field, we let omega _0 be the zero element of K
and let omega _i be alpha^(i - 1) for i = 1 ... q - 1 where alpha
is the primitive element of K. Now for a codeword u of C, let
s_i(u) be the number of components of u equal to omega _i.
The complete weight enumerator is the
sum over u in C of ((z_0)^(s_0(u)) ... (z_(q - 1))^(s_(q - 1)(u))).
CompleteWeightEnumerator(C, u): Code, ModTupFldElt -> RngMPolElt
The complete weight enumerator ( W)_(C + u)(z_0, ..., z_(q - 1))
for the coset C + u.
Words
Words(C, i) : Code, RngIntElt -> { ModTupFldElt }
Given a linear code C, return the set of all words of C having
weight i.
NumberOfWords(C, i) : Code, RngIntElt -> RngIntElt
Given a linear code C, return the number of words of C having
weight i.
ConstantWords(C, i) : Code, RngIntElt -> { ModTupFldElt }
Given a linear code C, return the set of all words of C which
have weight i and consist of zeros and ones alone.
NumberOfConstantWords(C, i) : Code, RngIntElt -> RngIntElt
Given a linear code C, return the number of words of C which
have weight i and consist of zeros and ones alone.
Example Code_Words (H58E15)
We construct the words of weight 11 and the constant (zero-one) words of weight
11 of a BCH code over GF(3).
> C := BCHCode(GF(3), 23, 5);
> C;
[23, 12, 8] BCH code (d = 5, b = 1) over GF(3)
Generator matrix:
[1 0 0 0 0 0 0 0 0 0 0 0 2 0 0 1 0 1 0 2 2 1 1]
[0 1 0 0 0 0 0 0 0 0 0 0 1 2 0 2 1 2 1 1 0 1 0]
[0 0 1 0 0 0 0 0 0 0 0 0 0 1 2 0 2 1 2 1 1 0 1]
[0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 2 0 2]
[0 0 0 0 1 0 0 0 0 0 0 0 2 1 0 2 1 1 1 0 2 0 1]
[0 0 0 0 0 1 0 0 0 0 0 0 1 2 1 2 2 0 1 2 1 1 2]
[0 0 0 0 0 0 1 0 0 0 0 0 2 1 2 2 2 0 0 0 1 2 2]
[0 0 0 0 0 0 0 1 0 0 0 0 2 2 1 0 2 0 0 2 2 2 0]
[0 0 0 0 0 0 0 0 1 0 0 0 0 2 2 1 0 2 0 0 2 2 2]
[0 0 0 0 0 0 0 0 0 1 0 0 2 0 2 0 1 1 2 2 2 0 0]
[0 0 0 0 0 0 0 0 0 0 1 0 0 2 0 2 0 1 1 2 2 2 0]
[0 0 0 0 0 0 0 0 0 0 0 1 0 0 2 0 2 0 1 1 2 2 2]
> WeightDistribution(C);
[ <0, 1>, <8, 1518>, <9, 2530>, <11, 30912>, <12, 30912>, <14, 151800>, <15,
91080>, <17, 148764>, <18, 49588>, <20, 21252>, <21, 3036>, <23, 48> ]
> W11 := Words(C, 11);
> ZOW11 := ConstantWords(C, 11);
> #W11;
30912
> #ZOW11;
23
> ZOW11 subset W11;
true
> ZOW11;
{
(0 1 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 0 0 1 0 1 0),
(0 1 0 1 0 0 1 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 0),
(1 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 0 0 1 0 1 0 0),
(1 1 0 1 0 1 1 1 1 0 0 0 0 0 1 0 1 0 0 1 1 0 0),
(0 0 0 0 0 1 0 1 0 0 1 1 0 0 1 1 0 1 0 1 1 1 1),
(0 1 0 1 1 1 1 0 0 0 0 0 1 0 1 0 0 1 1 0 0 1 1),
(1 0 1 0 0 1 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 0 0),
(1 0 1 1 1 1 0 0 0 0 0 1 0 1 0 0 1 1 0 0 1 1 0),
(1 1 0 0 0 0 0 1 0 1 0 0 1 1 0 0 1 1 0 1 0 1 1),
(1 1 1 0 0 0 0 0 1 0 1 0 0 1 1 0 0 1 1 0 1 0 1),
(0 0 0 1 0 1 0 0 1 1 0 0 1 1 0 1 0 1 1 1 1 0 0),
(1 1 1 1 0 0 0 0 0 1 0 1 0 0 1 1 0 0 1 1 0 1 0),
(0 0 1 1 0 1 0 1 1 1 1 0 0 0 0 0 1 0 1 0 0 1 1),
(0 1 0 0 1 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 0 0 1),
(0 1 1 0 1 0 1 1 1 1 0 0 0 0 0 1 0 1 0 0 1 1 0),
(1 0 0 0 0 0 1 0 1 0 0 1 1 0 0 1 1 0 1 0 1 1 1),
(1 0 1 0 1 1 1 1 0 0 0 0 0 1 0 1 0 0 1 1 0 0 1),
(0 0 1 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 0 0 1 0 1),
(0 0 1 0 1 0 0 1 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0),
(0 1 1 1 1 0 0 0 0 0 1 0 1 0 0 1 1 0 0 1 1 0 1),
(0 0 0 0 1 0 1 0 0 1 1 0 0 1 1 0 1 0 1 1 1 1 0),
(1 0 0 1 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 0 0 1 0),
(1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 0 0 1 0 1 0 0 1)
}
Other Structural Properties
CosetDistanceDistribution(C) : Code -> [ <RngIntElt, RngIntElt> ]
Given a linear code C, determine the coset distance
distribution of C, relative to C. The distance between
C and a coset D of C is the Hamming weight of a
vector of minimum weight in D.
CoveringRadius(C) : Code -> RngIntElt
The covering radius of the linear code C.
Diameter(C) : Code -> RngIntElt
The diameter of the code C (the largest weight of the codewords of C).
Example Code_WeightDistribution (H58E16)
We construct the second order Reed-Muller code of length 64, and calculate
the weight distribution of it and its dual code.
> R := ReedMullerCode(2, 6);
> #R;
4194304
> WeightDistribution(R);
[ <0, 1>, <16, 2604>, <24, 291648>, <28, 888832>, <32, 1828134>, <36, 888832>,
<40, 291648>, <48, 2604>, <64, 1> ]
> D := Dual(R);
> #D;
4398046511104
> WeightDistribution(D);
[ <0, 1>, <8, 11160>, <12, 1749888>, <14, 22855680>, <16, 232081500>, <18,
1717223424>, <20, 9366150528>, <22, 38269550592>, <24, 119637587496>, <26,
286573658112>, <28, 533982211840>, <30, 771854598144>, <32, 874731154374>,
<34, 771854598144>, <36, 533982211840>, <38, 286573658112>, <40,
119637587496>, <42, 38269550592>, <44, 9366150528>, <46, 1717223424>,
<48, 232081500>, <50, 22855680>, <52, 1749888>, <56, 11160>, <64, 1> ]
Example Code_WeightEnumerator (H58E17)
We construct the unextended Ternary Golay code and calculate its weight
enumerator and its complete weight enumerator. To make the polynomials
print out nicely, we assign names to the parent polynomial rings in each
case. These names will stay for further calls to WeightEnumerator
and CompleteWeightEnumerator over the same alphabet.
> G := GolayCode(GF(3), false);
> W := WeightEnumerator(G);
> P<x, y> := Parent(W);
> W;
x^11 + 132*x^6*y^5 + 132*x^5*y^6 + 330*x^3*y^8 + 110*x^2*y^9 + 24*y^11
> CW := CompleteWeightEnumerator(G);
> CP<z0, z1, z2> := Parent(CW);
> CW;
z0^11 + 11*z0^6*z1^5 + 55*z0^6*z1^3*z2^2 + 55*z0^6*z1^2*z2^3 + 11*z0^6*z2^5 +
11*z0^5*z1^6 + 110*z0^5*z1^3*z2^3 + 11*z0^5*z2^6 + 55*z0^3*z1^6*z2^2 +
110*z0^3*z1^5*z2^3 + 110*z0^3*z1^3*z2^5 + 55*z0^3*z1^2*z2^6 +
55*z0^2*z1^6*z2^3 + 55*z0^2*z1^3*z2^6 + z1^11 + 11*z1^6*z2^5 +
11*z1^5*z2^6 + z2^11
[Next] [Prev] [Right] [Left] [Up] [Index] [Root]