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 currently has databases for best known linear codes over GF(q) for q=2, 3, 4, 5, 7, 8, 9. There is also a database of best known quantum codes that can be found in Chapter QUANTUM CODES. The database for codes over GF(2) contains constructions of best codes of length up to nmax=256. The codes of length up to nopt=31 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.
The database for codes over GF(3) contains constructions of best codes of up to length nmax=243. The codes of length up to nopt=21 are optimal. The database is complete up to length ncomplete=120. Many of the codes constructed in this database are vast improvements on the previously known bounds for best codes over GF(3). The database of codes over GF(3) is a contribution of Markus Grassl, Karlsruhe then Gdansk.
The database for codes over GF(4) contains constructions of best codes of up to length nmax=256. The codes of length up to nopt=18 are optimal. The database is over 67% complete with the first missing code coming at length 99. Many of the codes constructed in this database are vast improvements on the previously known bounds for best codes over GF(4).
Similar databases for other small fields were added in V2.14 and extended in V2.23. They are contributions of Markus Grassl, Karlsruhe then Gdansk. The statistics of all databases are summarised in the following table.
| F2 | F3 | F4 | F5 | F7 | F8 | F9 | |
| nmax | 256 | 243 | 256 | 130 | 100 | 130 | 130 |
| nopt | 31 | 21 | 18 | 15 | 14 | 15 | 17 |
| ncomplete | 256 | 100 | 97 | 80 | 68 | 78 | 93 |
| total | 33,152 | 29,889 | 33,152 | 8,645 | 5,150 | 8,645 | 8,645 |
| missing | 0 | 6,405 | 11,145 | 502 | 336 | 1,739 | 600 |
| filled | 100 | 78.57 | 66.38 | 94.20 | 93.48 | 79.88 | 93.06 |
Compared to previous released versions of the Magma BKLC database, 1201 missing codes have been added, and the lower bound on the minimum distance has been improved for 5155 codes.
Best known 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 [Bro98]. The online version of these tables [Bro] has been discontinued. Similar tables are now maintained by Markus Grassl [Gra]. Any improvements, errors, or problems with the Magma BKLC database should be reported to codes@codetables.de.
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 Brouwer's 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: Nuh Aydin, Anton Betten, Michael Braun, Iliya Bouyukliev, Andries Brouwer, Tat Chan, Zhi Chen, Rumen Daskalov, Scott Duplichan, Iwan Duursma, Yves Edel, Sebastian Egner, Peter Farkas, Damien Fisher, Philippe Gaborit, Willi Geiselmann, Stephan Grosse, Aaron Gulliver, Masaaki Harada, Ray Hill, Plamen Hristov, David Jaffe, Axel Kohnert, San Ling, Simon Litsyn, Pawel Lizak, Tatsuya Maruta, Masami Mohri, Masakatu Morii, Harald Niederreiter, Ayoub Otmani, Fernanda Pambianco, James B. Shearer, Neil Sloane, Roberta Sabin, Cen Tjhai, Ludo Tolhuizen, Martin Tomlinson, Gerard van der Geer, Henk van Tilborg, Chaoping Xing, Karl-Heinz Zimmermann, Johannes Zwanzger.
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. Given a specified length and minimum weight, for example, will result in a corresponding code of maximal possible dimension.
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.
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. A second boolean return value signals whether or not the desired code exists in the database.The databases currently available are over GF(q) for q=2, 3, 4, 5, 7, 8, 9 of length up to nmax as given in the table above.
If the verbose flag BestCode is set to true then the method used to construct the code will be printed.
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. A second boolean return value signals whether or not the desired code exists in the database.The databases currently available are over GF(q) for q=2, 3, 4, 5, 7, 8, 9 of length up to nmax as given in the table above.
If the verbose flag BestCode is set to true then the method used to construct the code will be printed.
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. A second boolean return value signals whether or not the desired code exists in the database.The databases currently available are over GF(q) for q=2, 3, 4, 5, 7, 8, 9 of length up to nmax as given in the table above.
If the verbose flag BestCode is set to true then the method used to construct the code will be printed.
> C := BKLC(GF(2),23,12); > C; [23, 12, 7] Cyclic Linear Code over GF(2) Generator matrix: [1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 0] [0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1] [0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 0 0] [0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 0] [0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1] [0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 1 1 0 0] [0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 1 1 0] [0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 1 1] [0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 1 1 1 0 0 0 1 1] [0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1] [0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1] [0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 0 1] > WeightDistribution(C); [ <0, 1>, <7, 253>, <8, 506>, <11, 1288>, <12, 1288>, <15, 506>, <16, 253>, <23, 1> ] > BKLCLowerBound(GF(2),23,12), BKLCUpperBound(GF(2),23,12); 7 7So we see that this code is optimal, in the sense that it meets the best known upper bound on its minimum weight. (All best known binary codes of length up to 31 are optimal).
However larger best known codes are not optimal, making it theoretically possible that better codes exist.
> C := BKLC(GF(2),145,36); > C:Minimal; [145, 36, 42] Linear Code over GF(2) > BKLCLowerBound(GF(2),145,36), BKLCUpperBound(GF(2),145,36); 42 52
> F<w> := GF(4); > C, has_code := BKLC(F, 14, 9); > has_code; true > C; [14, 9, 4] Linear Code over GF(2^2) Generator matrix: [ 1 0 0 0 0 0 0 0 0 0 0 w^2 w 1] [ 0 1 0 0 0 0 0 0 0 0 1 1 1 w^2] [ 0 0 1 0 0 0 0 0 0 0 w^2 w 0 w] [ 0 0 0 1 0 0 0 0 0 0 w 1 1 w] [ 0 0 0 0 1 0 0 0 0 0 w 0 w w^2] [ 0 0 0 0 0 1 0 0 0 0 w^2 1 1 1] [ 0 0 0 0 0 0 1 0 0 0 1 w w^2 0] [ 0 0 0 0 0 0 0 1 0 0 0 1 w w^2] [ 0 0 0 0 0 0 0 0 1 0 w^2 w^2 0 1] > BKLCLowerBound(F, 14, 9), BKLCUpperBound(F, 14, 9); 4 4Since the database over GF(4) is completely filled up to length 97 the boolean value was in fact unnecessary in this case. We see that the minimum weight of this code reaches the theoretical upper bound, as do all best known codes over GF(4) up to length 18.
> C, has_code := BestLengthLinearCode(GF(2),85,23); > has_code; true > C:Minimal; [166, 85, 23] Linear Code over GF(2) > > C, has_code := BestLengthLinearCode(GF(2),85,45); > has_code; true > C:Minimal; [233, 85, 45] Linear Code over GF(2) > > C, has_code := BestLengthLinearCode(GF(2),85,58); > has_code; false
For lengths <98 we know the database is filled so we do not need to check the second boolean return value.
> F<w> := GF(4); > C := BDLC(F, 12, 8); > C; [12, 3, 8] Linear Code over GF(2^2) Generator matrix: [ 1 0 0 w w^2 w w^2 w w 1 w w] [ 0 1 0 w w^2 1 0 w^2 w 0 w^2 w^2] [ 0 0 1 0 1 w^2 w^2 w^2 0 w^2 w w] > > C := BDLC(F, 27, 8); > C:Minimal; [27, 15, 9] Linear Code over GF(2^2) > C := BDLC(F, 67, 8); > C:Minimal; [67, 52, 8] Linear Code over GF(2^2)But for lengths ≥98 there may be gaps in the database so to be safe we check the second value.
> C, has_code := BDLC(F, 99, 8); > has_code; true > C:Minimal; [99, 81, 8] Linear Code over GF(2^2) > C, has_code := BDLC(F, 195, 8); > has_code; true > C:Minimal; [195, 174, 8] Linear Code over GF(2^2)
> SetPrintLevel("Minimal");
> SetVerbose("BestCode",true);
> P<x> := PolynomialRing(GF(2));
> a := BKLC(GF(2), 54, 36);
Construction of a [ 54 , 36 , 8 ] Code:
[1]: [63, 46, 7] Cyclic Code over GF(2)
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
[2]: [64, 46, 8] Linear Code over GF(2)
ExtendCode [1] by 1
[3]: [54, 36, 8] Linear Code over GF(2)
Shortening of [2] at { 55 .. 64 }
> a;
[54, 36, 8] Linear Code over 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, {55 .. 64});
> C3;
[54, 36, 8] Linear Code over GF(2)
>
> C3 eq a;
true