In the case of a linear code, the minimum weight and distance are equivalent. It is clear that is substantially easier to determine the minimum weight of a (possibly non-linear) code than its minimum distance. The general principle underlying the minimum weight algorithm in Magma is the embedding of low-weight information vectors into the code space, in the hope that they will map onto low weight codewords.
Let C be a [n, k] linear code over a finite field and G be its generator matrix. The minimum weight algorithm proceeds as follows: Starting with r = 1, all linear combinations of r rows of G are enumerated. By taking the minimum weight of each such combination, an upper bound, d_(upper), on the minimum weight of C is obtained. A strictly increasing function, d_(lower)(r), finds a lower bound on the minimum weight of the non-enumerated vectors for each computational step (the precise form of this function depends upon the algorithm being used). The algorithm terminates when d_(lower)(r) >= d_(upper), at which point the actual minimum weight is equal to d_(upper).
Two different algorithms are used. The first is used in the determination of the minimum weight of cyclic codes, and is attributed to A.E. Brouwer. This algorithm takes advantage of the fact that cyclic codes contain all cyclic shifts of a given codeword, and thus the number of information symbols for a codeword of any given weight (if it exists in the code) can be calculated in advance.
The second algorithm is used for non-cyclic codes, and is due to K.H. Zimmermann [BFKetalchar+98]. The key idea is to construct as many different generator matrices for the same code as possible, each having a different information set and such that the information sets are as disjoint as possible. By maximizing the number of information sets, d_(lower)(r) can be made increasingly accurate. Each information set will provide a different embedding of information vectors into the code, and thus the probability of a low-weight information vector mapping onto a low-weight codeword is increased.
Information sets are discarded if their ranks are too low to contribute to the lower bound calculation. The user may also specify a lower bound, RankLowerBound, on the rank of information sets initially created.
RankLowerBound: RngIntElt Default: 0
MaximumTime: RngIntElt Default: Infinity
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 informations 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:
> MinimumWeight(RandomLinearCode(GF(2),32,16)); Code MinimumWeightZimmermann: length 32, dimension 16, not cyclic Finished constructing sets, time taken: 0.000 Ranks: 16 14 2 Maximum Projected r: 9 Deleting non-contributing rank 2 information set New Ranks: 16 14 Starting Search... r: 1, i: 0, lower: 1, upper: 17, time: 0.000 New codeword identified of weight 8, time 0.000 New codeword identified of weight 7, time 0.000 New codeword identified of weight 6, time 0.000 New codeword identified of weight 5, time 0.000 r: 1, i: 1, lower: 1, upper: 5, time: 0.000 New Maximum Projected r: 3 r: 2, i: 0, lower: 2, upper: 5, time: 0.000 r: 2, i: 1, lower: 2, upper: 5, time: 0.000 r: 3, i: 0, lower: 4, upper: 5, time: 0.000 r: 3, i: 1, lower: 4, upper: 5, time: 0.000 Final Results: lower = 6, upper = 5, total time time: 0.000 5
Verbose output can be invaluable on long minimum weight calculations. The line:
r: 3, i: 0, lower: 4, upper: 5, time: 0.000
should be interpreted as saying that, currently, after 0.000 seconds of calculation, the minimum weight d is known to satisfy 4 <= d <= 5, and the algorithm is about to enumerate over the rows of the (i=0) first generator matrix in the set, in selections of (r=3) three vectors at a time.
Every time a new upper bound is found, a line is printed:
New codeword identified of weight 5, time 0.000
If this new upper bound reduces the maximum possible value of r the algorithm can attain, then this value is printed.
RankLowerBound: RngIntElt Default: 0
MaximumTime: RngIntElt Default: Infinity
The minimum weight algorithm is executed until it determines whether or not d is a lower bound for the minimum weight of C. (See the description of the function MinimumWeight for information on the parameters RankLowerBound and MaximumTime and on the verbose output). Three values are returned. The first of these is a boolean value, taking the value true if and only if d is verified to be a lower bound for the minimum weight of C, (false if the calculation is aborted due to time restrictions). The second return value is the best available lower bound for the minimum weight of C, and the third is a boolean which is true if this value is the actual minimum weight of C.
RankLowerBound: RngIntElt Default: 0
MaximumTime: RngIntElt Default: Infinity
The minimum weight algorithm is executed until it determines whether or not d is an upper bound for the minimum weight of C. (See the description of the function MinimumWeight for information on the parameters RankLowerBound and MaximumTime and on the verbose output). Three values are returned. The first of these is a boolean value, taking the value true if and only if d is verified to be an upper bound for the minimum weight of C, (false if the calculation is aborted due to time restrictions). The second return value is the best available upper bound for the minimum weight of C, and the third is a boolean which is true if this value is the actual minimum weight of C.
Return one word of the code C having minimum weight.
The set of words of the code C having minimum weight.
> a := BKLC(GF(2),77,34);
> a:Minimal;
[77, 34, 16] Linear Code over GF(2)
> g := GeneratorMatrix(a);
> delete a;
> ClearPrevious();
> a := LinearCode(g);
> a:Minimal;
[77, 34] Linear Code over GF(2)
> SetVerbose("Code",true);
> IsLB,d_lower,IsMinWeight := VerifyMinimumWeightLowerBound(a,11);
Code MinimumWeightZimmermann: length 77, dimension 34, not cyclic
Finished constructing sets, time taken: 0.000
Ranks: 34 34 6
Using congruence d mod 4 = 0
Maximum Projected r: 20
Deleting non-contributing rank 6 information set
New Ranks: 34 34
Starting Search...
r: 1, i: 0, lower: 4, upper: 44, time: 0.000
New codeword identified of weight 24, time 0.000
New codeword identified of weight 20, time 0.000
New codeword identified of weight 16, time 0.000
r: 1, i: 1, lower: 4, upper: 16, time: 0.000
New Maximum Projected r: 6
r: 2, i: 0, lower: 4, upper: 16, time: 0.000
r: 2, i: 1, lower: 4, upper: 16, time: 0.000
r: 3, i: 0, lower: 8, upper: 16, time: 0.000
r: 3, i: 1, lower: 8, upper: 16, time: 0.000
r: 4, i: 0, lower: 8, upper: 16, time: 0.009
r: 4, i: 1, lower: 8, upper: 16, time: 0.030
Final Results: lower = 12, upper = 16, total time time: 0.049
> IsLB;
true
> d_lower,IsMinWeight;
12 false
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.
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.
The weight distribution of the dual code of C (see WeightDistribution).
We construct the second order Reed--Muller code of length 64, and calculate the its weight distribution and that of 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 > time 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> ]
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)))
The (Hamming) weight enumerator W_(C + u)(x, y) for the coset C + u.
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)))
The complete weight enumerator ( W)_(C + u)(z_0, ..., z_(q - 1)) for the coset C + u.
> R<t> := PolynomialRing(GF(3));
> C := CyclicCode(11, t^5 + t^4 + 2*t^3 + t^2 + 2);
> W<x, y> := WeightEnumerator(C);
> 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<u, v, w> := CompleteWeightEnumerator(C);
> CW;
u^11 + 11*u^6*v^5 + 55*u^6*v^3*w^2 + 55*u^6*v^2*w^3 + 11*u^6*w^5 +
11*u^5*v^6 + 110*u^5*v^3*w^3 + 11*u^5*w^6 + 55*u^3*v^6*w^2 +
110*u^3*v^5*w^3 + 110*u^3*v^3*w^5 + 55*u^3*v^2*w^6 + 55*u^2*v^6*w^3 +
55*u^2*v^3*w^6 + v^11 + 11*v^6*w^5 + 11*v^5*w^6 + w^11
The vector u = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1) does not lie in the code C and can be taken as a coset leader. We determine the weight enumerator of the coset containing u.
> u := AmbientSpace(C)![0,0,0,0,0,0,0,0,0,0,1];
> Wu := WeightEnumerator(C, u);
> Wu;
x^10*y + 30*x^7*y^4 + 66*x^6*y^5 + 108*x^5*y^6 + 180*x^4*y^7 + 165*x^3*y^8 +
135*x^2*y^9 + 32*x*y^10 + 12*y^11
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.
Let C be a hypothetical [n, k] linear code over a finite field K. Let W be the complete weight enumerator of C (in the form as returned by 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---the function simply manipulates the given polynomial. Furthermore, if W is not the weight distribution of an actual code, the weight enumerator W' will be meaningless.
Let us suppose there exists a [31, 11] code C over F_2 that has complete weight enumerator u^(31) + 186u^(20)v^(11) + 310u^(19)v^(12) + 527u^(16)v^(15) + 527u^(15)v^(16) + 310u^(12)v^(19) + 186u^(11)v^(20) + v^(31) We compute the weight distribution and the complete weight enumerator of the dual of the hypothetical code C.
> W := [ <0, 1>, <11, 186>, <12, 310>, <15, 527>, <16, 527>,
> <19, 310>, <20, 186>, <31, 1> ];
> MacWilliamsTransform(31, 11, 2, W);
[ <0, 1>, <6, 806>, <8, 7905>, <10, 41602>, <12, 142600>, <14,
251100>, <16, 301971>, <18, 195300>, <20, 85560>, <22, 18910>, <24,
2635>, <26, 186> ]
> R<u, v> := PolynomialRing(Integers(), 2);
> CWE := u^31 + 186*u^20*v^11 + 310*u^19*v^12 + 527*u^16*v^15 + 527*u^15*v^16 +
> 310*u^12*v^19 + 186*u^11*v^20 + v^31;
> MacWilliamsTransform(31, 11, GF(2), CWE);
u^31 + 806*u^25*v^6 + 7905*u^23*v^8 + 41602*u^21*v^10 + 142600*u^19*v^12 +
251100*u^17*v^14 + 301971*u^15*v^16 + 195300*u^13*v^18 + 85560*u^11*v^20 +
18910*u^9*v^22 + 2635*u^7*v^24 + 186*u^5*v^26
The functions in this section only apply to codes over finite fields.
Cutoff: RngIntElt Default: Infinity
Given a linear code C, 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.
Given a linear code C, return the number of words of C having weight w.
Given a linear code C, return the set of all words of C having weight between l and u, inclusive.
Given a linear code C, return the set of all words of C which have weight i and which consist of zeros and ones alone.
Given a linear code C, return the number of words of C which have weight i and which consist of zeros and ones alone.
> R<x> := PolynomialRing(GF(3)); > f := x^11 + x^10 + x^9 + 2*x^8 + 2*x^7 + x^5 + x^3 + 2; > C := CyclicCode(23, f); > 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] > time 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> ] Time: 0.030
Note that the minimum distance is 8. We calculate all words of weight 11 and the constant words of weight 11.
1518 > time W11 := Words(C, 11); Time: 0.350 > #W11; 30912 > ZOW11 := ConstantWords(C, 11); > #ZOW11; 23 > ZOW11 subset W11; true
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. The distribution is returned as a sequence of pairs comprising a distance d and the number of cosets that are distance d from C.
The covering radius of the linear code C.
The diameter of the code C (the largest weight of the codewords of C).
We construct the second order Reed--Muller code of length 32, and calculate its coset distance distribution.
> R := ReedMullerCode(2, 5); > R:Minimal; [32, 16, 8] Reed-Muller Code (r = 2, m = 5) over GF(2) > CD := CosetDistanceDistribution(R); > CD; [ <0, 1>, <1, 32>, <2, 496>, <3, 4960>, <4, 17515>, <5, 27776>, <6, 14756> ]
From the dimension of the code we know C has 2^(16) cosets. The coset distance distribution tells us that there are 32 cosets at distance 1 from C, 496 cosets are distance 2, etc. We confirm that all cosets are represented in the distribution.
> &+ [ t[2] : t in CD ]; 65536 > CoveringRadius(R); 6 > Diameter(R); 32 > WeightDistribution(R); [ <0, 1>, <8, 620>, <12, 13888>, <16, 36518>, <20, 13888>, <24, 620>, <32, 1> ]
The covering radius gives the maximum distance of any coset from the code, and, from the coset distance distribution, we see that this maximum distance is indeed 6. We can confirm the value (32) for the diameter by examining the weight distribution and seeing that 32 is the largest weight of a codeword.