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 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'$ 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'$ 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 $d'\geqslant {\tfrac {d}{2}}.$ This implies

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

therefore due to the integrality of $n'$

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

so that

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

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.

The 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.

References

J. H. Griesmer, "A bound for error-correcting codes," IBM Journal of Res. and Dev., vol. 4, no. 5, pp. 532-542, 1960.

This article is issued from Wikipedia - version of the 8/31/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Griesmer bound

Statement of the bound

Proof

The bound for the general case

See also

References