Griesmer Bound for Linear Codes over Finite Fields

 

Griesmer Bound

An [n,k,d]q code means a linear code of length n, dimension k and minimum Hamming distance d over the field of q elements GF(q).

nq(k,d) = the minimum length n for which an [n,k,d]q code exists.

The Griesmer bound says that an [n,k,d]q code satisfies

Griesmer bound


Linear Codes of Dimension k over GF(q) with k = 1 or 2

The Griesmer bound is attained for all d and q for k = 1, 2.


Binary Linear Codes

All values of n2(k,d) have been determined for k < 9, see
I. Bouyukliev, D.B. Jaffe, Z. Vabrek, The smallest length of eight-dimensional binary linear codes with prescribed minimum distance, IEEE Trans. Inform. Theory 46(4) (2000) 1539--1544.


Linear Codes of Dimension Three over GF(q), 2 < q <= 9

The Griesmer bound is attained for all d except the following, for which nq(3,d) = gq(3,d) + 1:

q=3; d=3

q=4; d=7, 8

q=5; d=5, 9, 10, 13, 14, 15

q=7; d=7, 13, 14, 19-21, 25-28, 31-35

q=8; d=13-16, 29-32, 37-40, 43-48

q=9; d=9, 15-18, 25-27, 33-36, 43-45, 49-54, 58-63.

See also Ball's table.


Ternary Linear Codes for k = 4, 5, 6

When k = 4, the Griesmer bound is attained for all d except the following 7 cases:

n3(4,d) = g3(4,d) + 1 for d = 3, 7-9, 13-15.

n3(5,d) table (The Griesmer bound is attained for the missing d in the table.)

n3(6,d) table


Quaternary Linear Codes for k = 4, 5

When k = 4, the Griesmer bound is attained for all d except the following 30 cases:

n4(4,d) = g4(4,d) + 1 for d = 3, 4, 7, 8, 13-16, 23-32, 37-44, 77-80.

n4(5,d) table (The Griesmer bound is attained for the missing d in the table.)


Linear Codes over GF(5) for k = 4, 5

When k = 4, the Griesmer bound is attained for all d except the following cases:

n5(4,d) = g5(4,d) + 1 for d = 4, 5, 9, 10, 12-15, 21-24, 31-50, 61-75, 83-95, 146-150, 163-175.

n5(4,d) = g5(4,d) + 2 for d = 25.

n5(4,d) = g5(4,d) or g5(4,d) + 1 for d = 81, 82, 161, 162. <--- only four open cases!

Note (2009):
The nonexistence of [g5(4,d),4,d]5 codes for d = 31, 32, 36, 37 was proved by Edel and Landjev.

Note (2015):
The nonexistence of [g5(4,d),4,d]5 codes for d = 82, 162 was announced by Rousseva and Landjev at ALCOMA15.

n5(5,d) table (n5(5,d) = g5(5,d) for all d > 1375. )


Linear Codes over GF(8) for k = 4

n8(4,d) table after On optimal linear codes over F8


Linear Codes over GF(9) for k = 4

n9(4,d) table (n9(4,d) = g9(4,d) for all d > 1215. )


See Markus Grassl's table for other cases.

If you get a new result improving the tables in this site, please inform it to Tatsuya Maruta.
 


- Last change: 08/21/2019