|
Important invariants of a linear code relate to the weights of code
words and in particular, their minimum and distribution. The computation
of these invariants involves some form of enumeration of code words
and in many ways is similar to the enumeration of lattice vectors.
Since V2.26-4 (May 2021), we have parallelised the computation of the
minimum weight of a code word in a code and the distribution of
weights.
In this section all codes will be linear codes over a finite field.
The two main enumerations which have been parallelised are:-
- (i)
- Determining the minimum weight of a code C: Intrinsic
MinimumWeight(C)
- (ii)
- Determining the weight distribution of a code: Intrinsic
MinimumDistance(C)
Related algorithms that are also parallelised are:-
- (i)
- MinimumDistance (C): Same as minimum weight
- (ii)
- MinimumWord (C): Returns a word of minimum weight
Pthreads code is available in the Magma kernel for each type of
enumeration as well as distributed parallelism of nodes which
are running the Pthreads code. The progress of a code word enumeration
can tracked using the statement SetVerbose ("Code", 1); .
Perhaps the most important invariant is the minimum weight of a code
word as this determines the error-correction capability of the code.
The serial algorithm used in Magma is based on an algorithm of
A.E. Brouwer and K.H. Zimmermann with improvements by M. Grassl,
A. Steel and G. White. A version of the algorithm that uses both
POSIX threads and/or distributed computation is available in Magma.
As usual, one uses SetNthreads and optionally StartWorkers.
Let C be the binary quadratic residue code of length 191
and dimension 96. Quadratic residue codes can be constructed using
the Magma intrinsic QRCode. Its minimum was found to be 27 on
single relatively slow machine with 36 cores. The real time was 516,120
seconds and the CPU time was 36,667,875 seconds. Note that a total of
4,761,899,689,016,196 vectors were enumerated. The code for this
calculation is:-
> SetNthreads(108);
> C := QRCode( GF(2), 191);
> time mw := MinimumWeight(C); mw;
Let C be the quadratic residue code [97, 49] over GF(3).
Using Pthreads on a single machine, its minimum was found to be 23
in 21,121 seconds real time. The code for this calculation is:-
> SetNthreads(32);
> C := QRCode( GF(3), 97);
> time mw := MinimumWeight(C); mw;
Let D be the binary code constructed from the lines of the
dual of a Dempwolff plane. Let the code C be the hull of D, that
is C := D ∪(Dual)(D). This is a [273, 102] code over GF(2)
and we find its minimum to be 24 using one manager machine and one worker
machine each having 16 cores. The real time for the computation was
1391 seconds.
In this rather large example we use both POSIX threads and distributed
computation. We determine the minimum weight of the Best Known Linear
Code over GF(2) having block length 256 and dimension 56. We run
32 threads on each of a master and four worker 16-core machines.
The following job is started on the master machine node1:--
> SetNthreads(32);
> StartWorkers("node2", 32); // start worker with 32 threads on node2
> StartWorkers("node3", 32); // start worker with 32 threads on node3
> StartWorkers("node4", 32); // start worker with 32 threads on node4
> StartWorkers("node5", 32); // start worker with 32 threads on node5
> C := BestKnownLinearCode( GF(2), 256, 56 );
> ResetMinimumWeightBounds(C);
> d := MinimumWeight(C);
> d;
68
The runtime was 20,560 seconds. A second job that used only 32 threads
on a single machine took 94,082 seconds. The speedup using five
machines instead of one is a factor of 4.5 whereas 160 threads
compared to 32 threads gives a factor of 5. The difference of 0.5 is
explained by the fact that out of the five machines used for the 160
thread run, three of the machines are slower than the machine used
in the 32 thread run. Consequently, if the minimum of a code is
computed using the same number of threads on each of n identical
machines (compute nodes) the runtime can expected to be a factor of
n faster than if the computation is run on a single machine
(compute node).
The weight distribution of a code C is found using the intrinsic
WeightDistribution (C).
Related algorithms that are also parallelised:-
- (i)
- WeightEnumerator (C) : Weight distribution presented in polynomial form
- (ii)
- DualWeightDistribution (C): Weight distribution of the dual code of C
We construct the weight distribution for a binary [97, 49]
quadratic residue code using the following Magma statements.
The computation was run on a machine with 16 cores using Pthreads
parallelisation combined with distribution of the work over two
machines (one manager and one worker).
Manager (running on node1):
> SetNthreads(32);
> StartWorkers("node2", 32); // start worker with 32 threads on node2
> SetVerbose("Code", 1);
> C := QRCode(GF(2), 97);
> time wd := WeightDistribution(C); wd;
The computation took 10,840 seconds real time and 345,508 seconds CPU
time. The weight distribution is:-
[ <0, 1>, <15, 4656>, <16, 23862>, <17, 14841>, <18, 65960>, <19, 190120>,
<20, 741468>, <21, 3375988>, <22, 11662504>, <23, 40893648>, <24, 126088748>,
<25, 360406410>, <26, 998048520>, <27, 2614461952>, <28, 6536154880>,
<29, 15589859400>, <30, 35337014640>, <31, 76345991760>, <32, 157463608005>,
<33, 310186322386>, <34, 583880136256>, <35, 1050952990464>,
<36, 1809974594688>, <37, 2983811972296>, <38, 4711282061520>,
<39, 7127688680200>, <40, 10335148586290>, <41, 14368570181112>,
<42, 19158093574816>, <43, 24503812839176>, <44, 30072861211716>,
<45, 35419208941404>, <46, 40039105759848>, <47, 43447332367896>,
<48, 45257637883225>, <49, 45257637883225>,
<50, 43447332367896>, <51, 40039105759848>, <52, 35419208941404>,
<53, 30072861211716>, <54, 24503812839176>, <55, 19158093574816>,
<56, 14368570181112>, <57, 10335148586290>, <58, 7127688680200>,
<59, 4711282061520>, <60, 2983811972296>, <61, 1809974594688>,
<62, 1050952990464>, <63, 583880136256>, <64, 310186322386>,
<65, 157463608005>, <66, 76345991760>, <67, 35337014640>, <68, 15589859400>,
<69, 6536154880>, <70, 2614461952>, <71, 998048520>, <72, 360406410>,
<73, 126088748>, <74, 40893648>, <75, 11662504>, <76, 3375988>, <77, 741468>,
<78, 190120>, <79, 65960>, <80, 14841>, <81, 23862>, <82, 4656>, <97, 1> ]
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|