In the mathematics of coding theory, the Griesmer bound, named after James Hugo Griesmer, is a bound on the length of binary codes of dimension k and minimum distance d. There is also a very similar version for non-binary codes.
For a binary linear code, the Griesmer bound is:
n
⩾
∑
i
=
0
k
−
1
⌈
d
2
i
⌉
.
Let
N
(
k
,
d
)
denote the minimum length of a binary code of dimension k and distance d. Let C be such a code. We want to show that
N
(
k
,
d
)
⩾
∑
i
=
0
k
−
1
⌈
d
2
i
⌉
.
Let G be a generator matrix of C. We can always suppose that the first row of G is of the form r = (1, ..., 1, 0, ..., 0) with weight d.
G
=
[
1
…
1
0
…
0
∗
∗
∗
G
′
]
The matrix
G
′
generates a code
C
′
, which is called the residual code of
C
.
C
′
has obviously dimension
k
′
=
k
−
1
and length
n
′
=
N
(
k
,
d
)
−
d
.
C
′
has a distance
d
′
,
but we don't know it. Let
u
∈
C
′
be such that
w
(
u
)
=
d
′
. There exists a vector
v
∈
F
2
d
such that the concatenation
(
v
|
u
)
∈
C
.
Then
w
(
v
)
+
w
(
u
)
=
w
(
v
|
u
)
⩾
d
.
On the other hand, also
(
v
|
u
)
+
r
∈
C
,
since
r
∈
C
and
C
is linear:
w
(
(
v
|
u
)
+
r
)
⩾
d
.
But
w
(
(
v
|
u
)
+
r
)
=
w
(
(
(
1
,
⋯
,
1
)
+
v
)
|
u
)
=
d
−
w
(
v
)
+
w
(
u
)
,
so this becomes
d
−
w
(
v
)
+
w
(
u
)
⩾
d
. By summing this with
w
(
v
)
+
w
(
u
)
⩾
d
,
we obtain
d
+
2
w
(
u
)
⩾
2
d
. But
w
(
u
)
=
d
′
,
so we get
d
′
⩾
d
2
.
This implies
n
′
⩾
N
(
k
−
1
,
d
2
)
,
therefore due to the integrality of
n
′
n
′
⩾
⌈
N
(
k
−
1
,
d
2
)
⌉
,
so that
N
(
k
,
d
)
⩾
⌈
N
(
k
−
1
,
d
2
)
⌉
+
d
.
By induction over k we will eventually get
N
(
k
,
d
)
⩾
∑
i
=
0
k
−
1
⌈
d
2
i
⌉
.
Note that at any step the dimension decreases by 1 and the distance is halved, and we use the identity
⌈
⌈
a
/
2
k
−
1
⌉
2
⌉
=
⌈
a
2
k
⌉
for any integer a and positive integer k.
For a linear code over
F
q
, the Griesmer bound becomes:
n
⩾
∑
i
=
0
k
−
1
⌈
d
q
i
⌉
.
The proof is similar to the binary case and so it is omitted.
