|
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.
BestKnownLinearCode(K, n, k) : FldFin, RngIntElt, RngIntElt -> Code, BoolElt
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.
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. 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.
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. 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.
We look at some best known linear codes over GF(2). Since the
database over GF(2) is completely filled, we can ignore the second
boolean return value.
> 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 7
So 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
We look at some best known codes over GF(4). Since this database is
only approximately 66% complete, it is necessary to check the second
boolean return value to know if the database contains the desired
code.
> 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 4
Since 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.
We search for best known codes using dimension and minimum weight,
looking at codes over GF(2) of dimension 85. Even though the
database over GF(2) is 100% filled up to length 256, the code
required may be longer than that so we have to check the second
boolean return value.
> 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 a given minimum weight, we find the maximal known possible
dimensions for a variety of code lengths over GF(4).
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)
We find the best known code of length 54 and dimension 36, then using
the output of the verbose mode we re-create this code manually.
> 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
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|