Linear Codes

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); .

Contents

Minimum Weight

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.

Example Par_QRCodeMinimum (H5E23)

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.

Example Par_BKLC256Minimum (H5E24)

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).

Weight Distribution

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

Example Par_CodeWeightDistribution (H5E25)

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> ]
V2.28, 13 July 2023