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:

[math]\displaystyle{ n\geqslant \sum_{i=0}^{k-1} \left\lceil\frac{d}{2^i}\right\rceil. }[/math]

Proof

Let [math]\displaystyle{ N(k,d) }[/math] 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

[math]\displaystyle{ N(k,d)\geqslant \sum_{i=0}^{k-1} \left\lceil\frac{d}{2^i}\right\rceil. }[/math]

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.

[math]\displaystyle{ G= \begin{bmatrix} 1 & \dots & 1 & 0 & \dots & 0 \\ \ast & \ast & \ast & & G' & \\ \end{bmatrix} }[/math]

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

[math]\displaystyle{ w((v|u)+r)=w(((1,\cdots,1)+v)|u)=d-w(v)+w(u), }[/math]

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

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

so that

[math]\displaystyle{ N(k,d)\geqslant d + N\left (k-1, \left\lceil \tfrac{d}{2} \right\rceil \right ). }[/math]

By induction over k we will eventually get

[math]\displaystyle{ N(k,d)\geqslant \sum_{i=0}^{k-1} \left\lceil\frac{d}{2^i}\right\rceil. }[/math]

Note that at any step the dimension decreases by 1 and the distance is halved, and we use the identity

[math]\displaystyle{ \left\lceil\frac{\left\lceil a/2^{k-1}\right\rceil}{2}\right\rceil = \left\lceil\frac{a}{2^k}\right\rceil }[/math]

for any integer a and positive integer k.

Bound for the general case

For a linear code over [math]\displaystyle{ \mathbb{F}_q }[/math], the Griesmer bound becomes:

[math]\displaystyle{ n\geqslant \sum_{i=0}^{k-1} \left\lceil\frac{d}{q^i}\right\rceil. }[/math]

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.