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.

Statement of the bound

For a binary linear code, the Griesmer bound is:

${\displaystyle n\geqslant \sum _{i=0}^{k-1}\left\lceil {\frac {d}{2^{i}}}\right\rceil .}$ 

Proof

Let ${\displaystyle 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

${\displaystyle 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.

${\displaystyle G={\begin{bmatrix}1&\dots &1&0&\dots &0\\\ast &\ast &\ast &&G'&\\\end{bmatrix}}}$ 

The matrix ${\displaystyle G'}$  generates a code ${\displaystyle C'}$ , which is called the residual code of ${\displaystyle C.}$  ${\displaystyle C'}$  obviously has dimension ${\displaystyle k'=k-1}$  and length ${\displaystyle n'=N(k,d)-d.}$  ${\displaystyle C'}$  has a distance ${\displaystyle d',}$  but we don't know it. Let ${\displaystyle u\in C'}$  be such that ${\displaystyle w(u)=d'}$ . There exists a vector ${\displaystyle v\in \mathbb {F} _{2}^{d}}$  such that the concatenation ${\displaystyle (v|u)\in C.}$  Then ${\displaystyle w(v)+w(u)=w(v|u)\geqslant d.}$  On the other hand, also ${\displaystyle (v|u)+r\in C,}$  since ${\displaystyle r\in C}$  and ${\displaystyle C}$  is linear: ${\displaystyle w((v|u)+r)\geqslant d.}$  But

${\displaystyle w((v|u)+r)=w(((1,\cdots ,1)+v)|u)=d-w(v)+w(u),}$ 

so this becomes ${\displaystyle d-w(v)+w(u)\geqslant d}$ . By summing this with ${\displaystyle w(v)+w(u)\geqslant d,}$  we obtain ${\displaystyle d+2w(u)\geqslant 2d}$ . But ${\displaystyle w(u)=d',}$  so we get ${\displaystyle 2d'\geqslant d.}$  As ${\displaystyle d'}$  is integral, we get ${\displaystyle d'\geqslant \left\lceil {\tfrac {d}{2}}\right\rceil .}$  This implies

${\displaystyle n'\geqslant N\left(k-1,\left\lceil {\tfrac {d}{2}}\right\rceil \right),}$ 

so that

${\displaystyle 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

${\displaystyle 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

${\displaystyle \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.

The bound for the general case

For a linear code over ${\displaystyle \mathbb {F} _{q}}$ , the Griesmer bound becomes:

${\displaystyle 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

• Singleton bound
• Hamming bound
• Gilbert-Varshamov bound
• Johnson bound
• Plotkin bound
• Elias Bassalygo 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.