Best Known Linear Codes

An [n, k] linear code C is said to be a best known linear [n, k] code (BKLC) if C has the highest minimum weight among all known [n, k] linear codes.

An [n, k] linear code C is said to be an optimal linear [n, k] code if the minimum weight of C achieves the theoretical upper bound on the minimum weight of [n, k] linear codes.

Magma V2.8 incorporates a database containing constructions of the best known linear codes over F_2 of length up to 256. The codes of length up to 36 are optimal. The database is complete in the sense that it contains a construction for every set of parameters. Thus the user has access to 33, 152 best-known binary codes. Similar databases for other small fields will be added in the near future. Upper and lower bounds on the minimum weight for [n, k] linear codes are also available (see section Best Known Bounds for Linear Codes).

The Magma BKLC database makes use of the tables of bounds compiled by A.E. Brouwer, which are available at [Bro]. It should be noted that the Magma BKLC database is unrelated to the similar (but rather incomplete) BKLC database forming part of GUAVA, a share package in GAP3. A significant number of entries in the Magma BKLC database provide better codes than the corresponding ones listed in the Brouwer tables.

The construction of the Magma BKLC database has been undertaken by John Cannon (Sydney), Markus Grassl (Karlsruhe) and Greg White (Sydney). The authors wish to express their appreciation to the following people who generously supplied codes, constructions or other assistance: Andries Brouwer, Tat Chan, Zhi Chen, Damien Fisher, Stephan Grosse, Aaron Gulliver, Ray Hill, David Jaffe, Simon Litsyn, James B. Shearer and Henk van Tilborg.

Given any two of the parameters: length, dimension, and minimum weight, then Magma will return the code with the best possible value of the omitted parameter. For the parameters length and minimum weight, the code with the highest possible value is returned, while a code with minimum possible length is returned for a given dimension and minimum weight.

The user can display the method used to construct a particular BKLC code through use of a verbose mode, triggered by the verbose flag BestCode. When it is set to true, all of the functions in this section will output the steps involved in each code they construct. While some codes are defined by stored generator matrices, and some use constructions which are not general enough, or safe enough, to be available to the user, most codes are constructed using standard Magma functions. Note that having the verbose flag Code set to true at the same time can produce mixed and confusing output, since the database uses functions which have verbose outputs dependent on this flag.

BKLC(K, n, k) : FldFin,RngIntElt,RngIntElt -> Code

BestKnownLinearCode(K, n, k) : FldFin,RngIntElt,RngIntElt -> Code

Given a finite field K, a positive integer n, and a non-negative integer k such that k <= n, return an [n, k] linear code over K which has the largest minimum weight among all known [n, k] linear codes. This function is currently restricted to K = F_2 and 1 <= n <= 256.

BLLC(K, k, d) : FldFin,RngIntElt,RngIntElt -> Code, BoolElt

BestLengthLinearCode(K, k, d) : FldFin,RngIntElt,RngIntElt -> Code, BoolElt

Given a finite field K, and positive integers k and d, return a linear code over K with dimension k and minimum weight at least d which has the shortest length among known codes. If the required code has length greater than 256 then it is not available and the second return value, a Boolean, will return false (along with an irrelevant zero code). Otherwise the boolean return value will be true. This function is currently restricted to K = F_2 and 1 <= k <= 256.

BDLC(K, n, d) : FldFin,RngIntElt,RngIntElt -> Code

BestDimensionLinearCode(K, n, d) : FldFin,RngIntElt,RngIntElt -> Code

Given a finite field K, a positive integer n, and a positive integer d such that d <= n, return a linear code over K with length n and minimum weight >= d which has the largest dimension among known codes. This function is currently restricted to K = F_2 and 1 <= n <= 256.

Example CodeFld_BestLengthDimension (H97E40)

> SetPrintLevel("Minimal");
> C1 := BestLengthLinearCode(GF(2),45,33);
> C1;
[145, 45, 33] Linear Code over GF(2)
> C2 := BestKnownLinearCode(GF(2), Length(C1)-1 ,45);
> C2;
[144, 45, 32] Linear Code over GF(2)
> MinimumWeight(C2) ge 33;
false

Example CodeFld_VerboseBestCode (H97E41)

> SetPrintLevel("Minimal");
> SetVerbose("BestCode",true);
> a := BKLC(GF(2),54,36);
Construction of a [54, 36, 8] Code:
 Shortening of: {
    ExtendCode: {
       CyclicCode of length 63 with Generating Polynomial:
       x^17 + x^16 + x^15 + x^13 + x^12 + x^8 + x^6 + x^4 + x^3 + x^2 + 1
       -> [63, 46, 7] Cyclic Code over GF(2)
    } by 1
    -> [64, 46, 8] Linear Code over GF(2)
 }
 at { 1 .. 10 }
 -> [54, 36, 8] Linear Code over GF(2)
> a;
[54, 36, 8] Linear Code over GF(2)
>  
> P<x> := PolynomialRing(GF(2));
> p := x^17 + x^16 + x^15 + x^13 + x^12 + x^8 + x^6 + x^4 + x^3 + x^2 + 1;
> C1 := CyclicCode(63,p);
> C1;
[63, 46] Cyclic Code over GF(2)
> C2 := ExtendCode( C1 );
> C2;
[64, 46] Linear Code over GF(2)
> C3 := ShortenCode( C2 , {1..10} );
> C3;
[54, 36, 8] Linear Code over GF(2)
>  
> C3 eq a;
true