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.
For a binary linear code, the Griesmer bound is:
n ⩾ ∑ i = 0 k − 1 ⌈ d 2 i ⌉ . 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 ) ⩾ ∑ i = 0 k − 1 ⌈ d 2 i ⌉ . 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 = [ 1 … 1 0 … 0 ∗ ∗ ∗ G ′ ] 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 ∈ C ′ be such that w ( u ) = d ′ . There exists a vector v ∈ F 2 d such that the concatenation ( v | u ) ∈ C . Then w ( v ) + w ( u ) = w ( v | u ) ⩾ d . On the other hand, also ( v | u ) + r ∈ C , since r ∈ C and C is linear: w ( ( v | u ) + r ) ⩾ d . But
w ( ( v | u ) + r ) = w ( ( ( 1 , ⋯ , 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 + 2 w ( u ) ⩾ 2 d . But w ( u ) = d ′ , so we get d ′ ⩾ d 2 . This implies
n ′ ⩾ N ( k − 1 , d 2 ) , therefore due to the integrality of n ′
n ′ ⩾ ⌈ N ( k − 1 , d 2 ) ⌉ , so that
N ( k , d ) ⩾ ⌈ N ( k − 1 , d 2 ) ⌉ + d . By induction over k we will eventually get
N ( k , d ) ⩾ ∑ i = 0 k − 1 ⌈ d 2 i ⌉ . Note that at any step the dimension decreases by 1 and the distance is halved, and we use the identity
⌈ ⌈ a / 2 k − 1 ⌉ 2 ⌉ = ⌈ a 2 k ⌉ for any integer a and positive integer k.
For a linear code over F q , the Griesmer bound becomes:
n ⩾ ∑ i = 0 k − 1 ⌈ d q i ⌉ . The proof is similar to the binary case and so it is omitted.
