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, dupper, on the minimum weight of C is obtained. A strictly increasing function, dlower(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 dlower(r) ≥dupper, at which point the actual minimum weight is equal to dupper.
The algorithm is used for non-cyclic codes, and is due to A.E. Brouwer and K.H. Zimmermann [BFK+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, dlower(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.
A well known improvement attributed to Brouwer exists for cyclic codes, requiring the enumeration fo only one information set. A generalisation of this improvement has been made by G. White to quasicyclic codes, and any codes whose known automorphisms have large cycles. Functionality is included in this section for inputting partial knowledge of the automorphism group to take advantage of this improvement.
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.
Method: MonStgElt Default: "Auto"
RankLowerBound: RngIntElt Default: 0
MaximumTime: RngReSubElt Default: ∞
Nthreads: RngIntElt Default: 1
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.If the parameter Nthreads is set to a positive integer n, then n threads will be used in the computation, if POSIX threads are enabled. One can alternatively use the procedure SetNthreads to set the global number of threads to a value n so that n threads are always used by default in this algorithm unless overridden by the Nthreads parameter.
Sometimes a brute force calculation of the entire weight distribution can be a faster way to get the minimum weight for small codes. When the parameter Method is set to the default "Auto" then the method is internally chosen. The user can specify which method they want using setting it to either "Distribution" or "Zimmermann".
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(RandomLinearCode(GF(2),85,26)); Linear Code over GF(2) of length 85 with 26 generators. Is not cyclic Lower Bound: 1, Upper Bound: 60 Constructed 4 distinct generator matrices Relative Ranks: 26 26 26 7 Starting search for low weight codewords... Enumerating using 1 generator at a time: New codeword identified of weight 32, time 0.000 New codeword identified of weight 28, time 0.000 New codeword identified of weight 27, time 0.000 New codeword identified of weight 25, time 0.000 Discarding non-contributing rank 7 matrix New Relative Ranks: 26 26 26 Completed Matrix 1: lower = 4, upper = 25. Time so far: 0.000 New codeword identified of weight 23, time 0.000 Completed Matrix 2: lower = 5, upper = 23. Time so far: 0.000 Completed Matrix 3: lower = 6, upper = 23. Time so far: 0.000 Enumerating using 2 generators at a time: New codeword identified of weight 20, time 0.000 Completed Matrix 1: lower = 7, upper = 20. Time so far: 0.000 Completed Matrix 2: lower = 8, upper = 20. Time so far: 0.000 Completed Matrix 3: lower = 9, upper = 20. Time so far: 0.000 Enumerating using 3 generators at a time: New codeword identified of weight 19, time 0.000 Completed Matrix 1: lower = 10, upper = 19. Time so far: 0.000 Completed Matrix 2: lower = 11, upper = 19. Time so far: 0.000 Completed Matrix 3: lower = 12, upper = 19. Time so far: 0.000 Enumerating using 4 generators at a time: New codeword identified of weight 18, time 0.000 Completed Matrix 1: lower = 13, upper = 18. Time so far: 0.000 New codeword identified of weight 17, time 0.000 Completed Matrix 2: lower = 14, upper = 17. Time so far: 0.010 Completed Matrix 3: lower = 15, upper = 17. Time so far: 0.010 Termination predicted with 5 generators at matrix 2 Enumerating using 5 generators at a time: Completed Matrix 1: lower = 16, upper = 17. Time so far: 0.020 Completed Matrix 2: lower = 17, upper = 17. Time so far: 0.030 Final Results: lower = 17, upper = 17, Total time: 0.030 17Verbose output can be invaluable on long minimum weight calculations.
The algorithm constructs different (equivalent) generator matrices, each of which have pivots in different column positions of the code, called its information set. A generator matrix's relative rank is the size of its information set independent from the previously constructed matrices.
The algorithm proceeds by enumerating all combinations derived from r generators, for each successive r. Once r exceeds the difference between the actual rank of a matrix (i.e., the dimension), and its relative rank, then the lower bound on the minimum weight will increment by 1 for that step.
The upper bound on the minimum weight is determined by the minimum weight of codewords that are enumerated. Once these bounds meet the computation is complete.
Return the currently known lower and upper bounds on the minimum weight of code C.
Undefine the minimum weight of the code C if it is known, and reset any known bounds on its value.
RankLowerBound: RngIntElt Default: 0
MaximumTime: RngIntElt Default: ∞
The minimum weight algorithm is executed until it determines whether or not d is a lower bound for the minimum weight of the code 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: ∞
The minimum weight algorithm is executed until it determines whether or not d is an upper bound for the minimum weight of the code 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.
NumWords: RngIntElt Default:
Method: MonStgElt Default: "Auto"
RankLowerBound: RngIntElt Default: ∞
MaximumTime: RngReSubElt Default: ∞
Given a linear code C, return the set of all words of C having minimum weight. If NumWords is set to a non-negative integer, then the algorithm will terminate after that total of words have been found. Similarly, if MaximumTime then the algorithm will abort if the specified time limit expires.A variation of the Zimmermann minimum weight algorithm is generally used to collect the minimum words, although in some cases (such as small codes) a brute force enumeration may be used. When the parameter Method is set to the default "Auto" then the method is internally chosen. The user can specify which method they want using setting it to either "Distribution" or "Zimmermann".
By setting the verbose flag "Code", information about the progress of the computation can be printed.
> a := BKLC(GF(2),77,34);
> a:Minimal;
[77, 34, 16] Linear Code over GF(2)
> ResetMinimumWeightBounds(a);
> MinimumWeightBounds(a);
1 44
> a:Minimal;
[77, 34] Linear Code over GF(2)
> SetVerbose("Code",true);
> IsLB, d_lower, IsMinWeight := VerifyMinimumWeightLowerBound(a, 11);
Linear Code over GF(2) of length 77 with 34 generators. Is not cyclic
Lower Bound: 1, Upper Bound: 44
Using congruence d mod 4 = 0
Constructed 3 distinct generator matrices
Relative Ranks: 34 34 6
Starting search for low weight codewords...
Discarding non-contributing rank 6 matrix
Enumerating using 1 generator at a time:
New codeword identified of weight 20, time 0.000
New codeword identified of weight 16, time 0.000
Completed Matrix 1: lower = 4, upper = 16. Time so far: 0.000
Completed Matrix 2: lower = 4, upper = 16. Time so far: 0.000
Enumerating using 2 generators at a time:
Completed Matrix 1: lower = 8, upper = 16. Time so far: 0.000
Completed Matrix 2: lower = 8, upper = 16. Time so far: 0.000
Enumerating using 3 generators at a time:
Completed Matrix 1: lower = 8, upper = 16. Time so far: 0.000
Completed Matrix 2: lower = 8, upper = 16. Time so far: 0.000
Enumerating using 4 generators at a time:
Completed Matrix 1: lower = 12, upper = 16. Time so far: 0.010
Final Results: lower = 12, upper = 16, Total time: 0.010
> IsLB;
true
> d_lower, IsMinWeight;
12 false
Given some automorphism p or group of automorphisms G of the code C, which can either be a permutation of the columns or a full monomial permutation of the code. Then include these automorphism in the known automorphisms subgroup. Automorphisms with long cycles that can aid the minimum weight calculation should be added in this way.
Return the maximally known subgroup of the full group of automorphisms of the code C.
Nthreads: RngIntElt Default: 1
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, wi say, and the number of codewords having weight wi.If the parameter Nthreads is set to a positive integer n, then n threads will be used in the computation, if POSIX threads are enabled. One can alternatively use the procedure SetNthreads to set the global number of threads to a value n so that n threads are always used by default in this algorithm unless overridden by the Nthreads parameter.
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, wi say, and the number of codewords having weight wi.
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> ]
Return the weight distribution of the code C up to the specified upper bound. This function uses the minimum weight collection to collect word sets.
The (Hamming) weight enumerator WC(x, y) for the linear code C. The weight enumerator is the sum over u in C of (xn - wt(u)ywt(u))
The (Hamming) weight enumerator WC + u(x, y) for the coset C + u.
The complete weight enumerator (W)C(z0, ..., zq - 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 ω0, ..., ωq - 1. If K is a prime field, we let ωi be i (i.e. take the natural representation of each number). If K is a non-prime field, we let ω0 be the zero element of K and let ωi be αi - 1 for i = 1 ... q - 1 where α is the primitive element of K. 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.
> 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 F2 that has complete weight enumerator u31 + 186u20v11 + 310u19v12 + 527u16v15 + 527u15v16 + 310u12v19 + 186u11v20 + v31 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.
NumWords: RngIntElt Default:
Method: MonStgElt Default: "Auto"
RankLowerBound: RngIntElt Default: ∞
MaximumTime: RngReSubElt Default: ∞
Given a linear code C, return the set of all words of C having weight w. If NumWords is set to a non-negative integer c, then the algorithm will terminate after that total of words have been found. Similarly, if MaximumTime then the algorithm will abort if the specified time limit expires.There are two methods for collecting words, one based on the Zimmermann minimum weight algorithm, and a brute force type calculation. When the parameter Method is set to the default "Auto" then the method is internally chosen. The user can specify which method they want using setting it to either "Distribution" or "Zimmermann".
By setting the verbose flag "Code", information about the progress of the computation can be printed.
Given a linear code C, return the number of words of C having weight w.
Cutoff: RngIntElt Default: ∞
StoreWords: BoolElt Default: true
Given a linear code C, 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.
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 216 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.