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

edit

For a binary linear code, the Griesmer bound is:

 

Proof

edit

Let   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

 

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.

 

The matrix   generates a code  , which is called the residual code of     obviously has dimension   and length     has a distance   but we don't know it. Let   be such that  . There exists a vector   such that the concatenation   Then   On the other hand, also   since   and   is linear:   But

 

so this becomes  . By summing this with   we obtain  . But   so we get   As   is integral, we get   This implies

 

so that

 

By induction over k we will eventually get

 

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

 

for any integer a and positive integer k.

Bound for the general case

edit

For a linear code over  , the Griesmer bound becomes:

 

The proof is similar to the binary case and so it is omitted.

See also

edit

References

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