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.
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 32Verbose 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.
> 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.