|
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.
MinimumWeight(C: parameters) : Code -> RngIntElt
MinimumDistance(C: parameters) : Code -> RngIntElt
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
17
Verbose 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.
VerifyMinimumWeightUpperBound(C, d: parameters) : Code, RngIntElt -> BoolElt, RngIntElt, BoolElt
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.
The function BKLC(K, n, k) returns the best known linear [n, k]-code
over the field K. We use this function to construct the [77, 34, 16] best
known linear code and confirm a lower bound on its minimum weight (which is
not as good as its actual minimum weight).
We check to see whether the minimum weight of this code is at least 11
and in doing so we will actually get a slightly better bound, though it
will be still less than the true minimum weight.
Since the function BLKC will set the true minimum weight, it is first
necessary to reset the bounds so that the minimum weight data
is lost.
> 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
IncludeAutomorphism(~C, G) : Code, GrpPerm ->
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.
We construct the cyclic ternary code of length 11 with generator
polynomial t 5 + t 4 + 2t 3 + t 2 + 2 and calculate both its weight
enumerator and its complete weight enumerator. To ensure the polynomials
print out nicely, we assign names to the polynomial ring indeterminates
in each case. These names will persist if further calls to
WeightEnumerator and CompleteWeightEnumerator over the same
alphabet are made.
> 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.
We construct the words of weight 11 and also the constant (zero-one)
words of weight 11 in the length 23 cyclic code over GF(3)
that is defined by the generator polynomial
x 11 + x 10 + x 9 + 2x 8 + 2x 7 + x 5 + x 3 + 2.
> 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.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|