Griesmer bound

In the mathematics of coding theory, the Griesmer bound, named after James Hugo Griesmer, is a bound on the length of linear 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: Let

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 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. The matrix

generates a code

, which is called the residual code of

{\displaystyle C.}

obviously has dimension

and length

has a distance

but we don't know it.

There exists a vector

such that the concatenation

On the other hand, also

is linear:

{\displaystyle d-w(v)+w(u)\geqslant d}

By summing this with

we obtain

is integral, we get

This implies so that By induction over k we will eventually get Note that at any step the dimension decreases by 1 and the distance is halved, and we use the identity for any integer a and positive integer k. For a linear code over

, the Griesmer bound becomes: The proof is similar to the binary case and so it is omitted.