|
An adaptation of the minimum weight algorithm for linear codes
(see Section The Minimum Weight) has been developed
for additive codes by Markus Grassl and Greg White.
From a user's perspective, the description given in The Minimum Weight
is sufficient to understand the additive case.
The algorithm is still new, and has yet to be optimised
to its full potential.
MinimumDistance(C: parameters) : CodeAdd -> RngIntElt
RankLowerBound: RngIntElt Default: 0
MaximumTime: RngReSubElt Default: ∞
Determine the minimum weight of the words belonging to the code C, which
is also the minimum distance between any two codewords. The parameter
RankLowerBound sets a minimum rank on the information sets used
in the calculation, while the parameter MaximumTime sets a time
limit (in seconds of "user time") after which the calculation is aborted.
By setting the verbose flag "Code", information about the progress of the
computation can be printed. An example to demonstrate the interpretation
of the verbose output follows:
> SetVerbose("Code", true);
> SetSeed(1);
> MinimumWeight(RandomAdditiveCode(GF(4),GF(2),82,39));
GF(2)-Additive code over GF(4) of length 82 with 39 generators.
Is not cyclic
Lower Bound: 1, Upper Bound: 64
Constructed 5 distinct generator matrices
Total Ranks: 21 20 20 20 20
Relative Ranks: 21 20 20 20 1
Starting search for low weight codewords... 0.020
Discarding non-contributing rank 1 matrix
Enumerating using 1 generator at a time:
New codeword identified of weight 48, time 0.020
New codeword identified of weight 46, time 0.020
New codeword identified of weight 44, time 0.020
New codeword identified of weight 42, time 0.020
Completed Matrix 1: lower = 5, upper = 42. Time so far: 0.030
New codeword identified of weight 41, time 0.030
Completed Matrix 2: lower = 6, upper = 41. Time so far: 0.030
Completed Matrix 3: lower = 7, upper = 41. Time so far: 0.040
New codeword identified of weight 40, time 0.040
Completed Matrix 4: lower = 8, upper = 40. Time so far: 0.040
Enumerating using 2 generators at a time:
New codeword identified of weight 37, time 0.050
Completed Matrix 1: lower = 9, upper = 37. Time so far: 0.050
Completed Matrix 2: lower = 10, upper = 37. Time so far: 0.050
Completed Matrix 3: lower = 11, upper = 37. Time so far: 0.060
New codeword identified of weight 36, time 0.060
Completed Matrix 4: lower = 12, upper = 36. Time so far: 0.060
Enumerating using 3 generators at a time:
New codeword identified of weight 34, time 0.070
Completed Matrix 1: lower = 13, upper = 34. Time so far: 0.070
New codeword identified of weight 33, time 0.080
Completed Matrix 2: lower = 14, upper = 33. Time so far: 0.090
Completed Matrix 3: lower = 15, upper = 33. Time so far: 0.100
Completed Matrix 4: lower = 16, upper = 33. Time so far: 0.110
Enumerating using 4 generators at a time:
New codeword identified of weight 32, time 0.120
Completed Matrix 1: lower = 17, upper = 32. Time so far: 0.170
Completed Matrix 2: lower = 18, upper = 32. Time so far: 0.250
Completed Matrix 3: lower = 19, upper = 32. Time so far: 0.320
Completed Matrix 4: lower = 20, upper = 32. Time so far: 0.390
Termination predicted with 7 generators at matrix 4
Enumerating using 5 generators at a time:
Completed Matrix 1: lower = 21, upper = 32. Time so far: 0.960
Completed Matrix 2: lower = 22, upper = 32. Time so far: 1.570
Completed Matrix 3: lower = 23, upper = 32. Time so far: 2.160
Completed Matrix 4: lower = 24, upper = 32. Time so far: 2.750
Termination predicted at 118 s (1 m 57 s) with 7 generators at matrix 4
Enumerating using 6 generators at a time:
Completed Matrix 1: lower = 25, upper = 32. Time so far: 6.680
Completed Matrix 2: lower = 26, upper = 32. Time so far: 10.969
Completed Matrix 3: lower = 27, upper = 32. Time so far: 15.149
Completed Matrix 4: lower = 28, upper = 32. Time so far: 19.440
Termination predicted at 114 s (1 m 54 s) with 7 generators at matrix 4
Enumerating using 7 generators at a time:
Completed Matrix 1: lower = 29, upper = 32. Time so far: 41.739
Completed Matrix 2: lower = 30, upper = 32. Time so far: 66.239
Completed Matrix 3: lower = 31, upper = 32. Time so far: 90.780
Completed Matrix 4: lower = 32, upper = 32. Time so far: 115.510
Final Results: lower = 32, upper = 32, Total time: 115.510
32
Verbose output can be invaluable in the case of lengthy minimum weight
calculations.
The algorithm constructs different (equivalent) generator matrices,
each of which has pivots in different column positions of the code, called
its information set.
The relative rank of a generator matrix is the size of its information
set independent of the previously constructed matrices.
When enumerating all generators taken r at a time, once r exceeds
the difference between the total rank of a matrix, and its relative rank,
the lower bound on the minimum weight will be incremented by 1 for
that step.
The upper bound on the minimum weight is determined by the minimum weight of
codewords that are enumerated. As soon as these bounds become equal, the
computation is complete.
We illustrate the much greater efficiency of the minimum weight algorithm
compared to computing the full weight distribution.
> SetVerbose("Code",true);
> C := RandomAdditiveCode(GF(9),GF(3),39,25);
> MinimumWeight(C);
GF(3)-Additive code over GF(9) of length 39 with 25 generators. Is not cyclic
Lower Bound: 1, Upper Bound: 28
Constructed 4 distinct generator matrices
Total Ranks: 13 13 13 13
Relative Ranks: 13 13 12 1
Starting search for low weight codewords... 0.009
Discarding non-contributing rank 1 matrix
Enumerating using 1 generator at a time:
New codeword identified of weight 25, time 0.009
New codeword identified of weight 23, time 0.009
New codeword identified of weight 21, time 0.009
Completed Matrix 1: lower = 3, upper = 21. Time so far: 0.009
Completed Matrix 2: lower = 4, upper = 21. Time so far: 0.009
Completed Matrix 3: lower = 5, upper = 21. Time so far: 0.009
Enumerating using 2 generators at a time:
New codeword identified of weight 20, time 0.009
New codeword identified of weight 19, time 0.009
New codeword identified of weight 18, time 0.009
Completed Matrix 1: lower = 6, upper = 18. Time so far: 0.009
Completed Matrix 2: lower = 7, upper = 18. Time so far: 0.019
Completed Matrix 3: lower = 8, upper = 18. Time so far: 0.019
Enumerating using 3 generators at a time:
New codeword identified of weight 17, time 0.070
Completed Matrix 1: lower = 9, upper = 17. Time so far: 0.089
Completed Matrix 2: lower = 10, upper = 17. Time so far: 0.149
Completed Matrix 3: lower = 11, upper = 17. Time so far: 0.210
Enumerating using 4 generators at a time:
Completed Matrix 1: lower = 12, upper = 17. Time so far: 1.379
Completed Matrix 2: lower = 13, upper = 17. Time so far: 2.539
Completed Matrix 3: lower = 14, upper = 17. Time so far: 3.719
Termination predicted at 49 s with 5 generators at matrix 3
Enumerating using 5 generators at a time:
Completed Matrix 1: lower = 15, upper = 17. Time so far: 19.409
Completed Matrix 2: lower = 16, upper = 17. Time so far: 35.019
Completed Matrix 3: lower = 17, upper = 17. Time so far: 50.649
Final Results: lower = 17, upper = 17, Total time: 50.649
17
> time WeightDistribution(C);
[ <0, 1>, <17, 2>, <18, 58>, <19, 496>, <20, 4000>, <21, 29608>, <22, 194760>,
<23, 1146680>, <24, 6126884>, <25, 29400612>, <26, 126624092>, <27, 487889854>,
<28, 1672552654>, <29, 5075315756>, <30, 13534236754>, <31, 31434430104>, <32,
62869109200>, <33, 106686382216>, <34, 150616653852>, <35, 172132748756>, <36,
153007413552>, <37, 99247655566>, <38, 41788710876>, <39, 8571983110> ]
Time: 224142.820
This function determines 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, wi say,
and the number of codewords having weight wi.
The weight distribution of the code which is dual to the additive code C
(see WeightDistribution).
The (Hamming) weight enumerator WC(x, y) for the additive code C.
The weight enumerator is the sum over u in C of (xn - wt(u)ywt(u))
The complete weight enumerator (W)C(z0, ..., zq - 1)
for the additive code C where q is the size of the alphabet E of C.
Let the q elements of E be denoted by
ω0, ..., ωq - 1. If E is a prime field, we let
ωi be i (i.e. take the natural representation of each number).
If E is a non-prime field, we let ω0 be the zero element of E
and let ωi be αi - 1 for i = 1 ... q - 1 where α
is the primitive element of E. Now for a codeword u of C, let
si(u) be the number of components of u equal to ωi.
The complete weight enumerator is the
sum over u in C of ((z0)s0(u) ... (zq - 1)sq - 1(u))
The complete weight enumerator (W)C + u(z0, ..., zq - 1)
for the coset C + u, where u is an element of the generic vector space
for the code C.
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 by 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---the function simply works with the sequence
of integer pairs supplied by the user. 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.
The functions in this section only apply to codes over finite fields.
Cutoff: RngIntElt Default: ∞
StoreWords: BoolElt Default: true
Given a linear code C defined over a finite field, return the set of all words
of C having weight w. If Cutoff is set to a non-negative integer c,
then the algorithm will terminate after a total of c words have been
found. If StoreWords is true then the words generated will be stored
internally.
Given a linear code C defined over a finite field, return the number of words
of C having weight w.
Cutoff: RngIntElt Default: ∞
StoreWords: BoolElt Default: true
Given a linear code C defined over a finite field, return the set of all words
of C having weight between l and u, inclusive.
If Cutoff is set to a non-negative integer c, then
the algorithm will terminate after a total of c words have been
found.
If StoreWords is true then any words of a single weight
generated will be stored
internally.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|