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:

$n⩾\sum _{i=0}^{k-1}\lceil \frac{d}{2^i}\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)⩾\sum _{i=0}^{k-1}\lceil \frac{d}{2^i}\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=\left[\begin{array}{cccccc}1& \dots & 1& 0& \dots & 0\\ \ast & \ast & \ast & & G^{\prime }& \\ \end{array}\right]$

The matrix $G^{\prime }$ generates a code $C^{\prime }$, which is called the residual code of $C.$ $C^{\prime }$ obviously has dimension $k^{\prime }=k-1$ and length $n^{\prime }=N(k,d)-d.$ $C^{\prime }$ has a distance $d^{\prime },$ but we don't know it. Let $u\in C^{\prime }$ be such that $w(u)=d^{\prime }$. There exists a vector $v\in {\mathbb{𝔽}}_2^d$ such that the concatenation $(v|u)\in C.$ Then $w(v)+w(u)=w(v|u)⩾d.$ On the other hand, also $(v|u)+r\in C,$ since $r\in C$ and $C$ is linear: $w((v|u)+r)⩾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)⩾d$. By summing this with $w(v)+w(u)⩾d,$ we obtain $d+2w(u)⩾2d$. But $w(u)=d^{\prime },$ so we get $2d^{\prime }⩾d.$ As $d^{\prime }$ is integral, we get $d^{\prime }⩾\lceil \frac{d}{2}\rceil .$ This implies

$n^{\prime }⩾N(k-1,\lceil \frac{d}{2}\rceil ),$

so that

$N(k,d)⩾d+N(k-1,\lceil \frac{d}{2}\rceil ).$

By induction over k we will eventually get

$N(k,d)⩾\sum _{i=0}^{k-1}\lceil \frac{d}{2^i}\rceil .$

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

$\lceil \frac{\lceil a/2^{k-1}\rceil }{2}\rceil =\lceil \frac{a}{2^k}\rceil$

for any integer a and positive integer k.

Bound for the general case

For a linear code over ${\mathbb{𝔽}}_q$, the Griesmer bound becomes:

$n⩾\sum _{i=0}^{k-1}\lceil \frac{d}{q^i}\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.