Griesmer bound

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

n\geq \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)\geq \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' has obviously 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^{\prime} s.t. w(u)=d'. There exists a vector v\in (F_2)^d s.t. the concatenation (v|u)\in C. Then w(v)+w(u)=w(v|u)\geq d. On the other hand, also (v|u)+r\in C, since r\in C and C is linear, so w((v|u)+r)\geq d. But

w((v|u)+r)=w(((1,1,...,1)+v)|u)=d-w(v)+w(u),

so this becomes d-w(v)+w(u)\geq d. By summing this with w(v)+w(u)\geq d, we obtain d+2w(u)\geq 2d. But w(u)=d', so we get d'\geq d/2. This implies n'\geq N(k-1,d/2), therefore n'\geq \left\lceil N(k-1,d/2)\right\rceil (due to the integrality of n'), so that N(k,d)\geq \left\lceil N(k-1,d/2)\right\rceil +d. By induction over k we will eventually get N(k,d)\geq \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).

The bound for the general case

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

n\geq \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

References

This article is issued from Wikipedia - version of the Wednesday, August 12, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.