Overview
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.
Statement of the bound
For a binary linear code, the Griesmer bound is: : n\geqslant \sum_ i=0 ^ k-1 \left\lceil\frac d 2^i \right\rceil.
Proof
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)\geqslant \sum_ i=0 ^ k-1 \left\lceil\frac d 2^i \right\rceil. 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= \begin bmatrix 1 & \dots & 1 & 0 & \dots & 0 \\ \ast & \ast & \ast & & G' & \\ \end bmatrix The matrix G' generates a code C' , which is called the residual code of C. C' obviously has dimension k'=k-1 and length n'=N(k,d)-d. C' has a distance d', but we don't know it. Let u\in C' be such that w(u)=d' . There exists a vector v\in \mathbb F _2^d such that the concatenation (v u)\in C. Then w(v)+w(u)=w(v u)\geqslant d. On the other hand, also (v u)+r\in C, since r\in C and C is linear: w((v u)+r)\geqslant d.
But : w((v u)+r)=w(((1,\cdots,1)+v) u)=d-w(v)+w(u), so this becomes d-w(v)+w(u)\geqslant d . By summing this with w(v)+w(u)\geqslant d, we obtain d+2w(u)\geqslant 2d . But w(u)=d', so we get 2d'\geqslant d. As d' is integral, we get d'\geqslant \left\lceil \tfrac d 2 \right\rceil. This implies : n'\geqslant N\left (k-1,\left\lceil \tfrac d 2 \right\rceil \right ), so that : N(k,d)\geqslant d + N\left (k-1, \left\lceil \tfrac d 2 \right\rceil \right ). By induction over k we will eventually get : N(k,d)\geqslant \sum_ i=0 ^ k-1 \left\lceil\frac d 2^i \right\rceil. Note that at any step the dimension decreases by 1 and the distance is halved, and we use the identity : \left\lceil\frac \left\lceil a/2^ k-1 \right\rceil 2 \right\rceil = \left\lceil\frac a 2^k \right\rceil for any integer a and positive integer k.
Bound for the general case
For a linear code over \mathbb F _q , the Griesmer bound becomes: : n\geqslant \sum_ i=0 ^ k-1 \left\lceil\frac d q^i \right\rceil. The proof is similar to the binary case and so it is omitted.
See also
*Elias Bassalygo bound *Gilbert-Varshamov bound *Hamming bound *Johnson bound *Plotkin bound *Singleton bound
References
*J. H. Griesmer, "A bound for error-correcting codes," IBM Journal of Res. and Dev., vol. 4, no. 5, pp. 532-542, 1960.