Griesmer bound

☆ Save On Wikipedia ↗

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 ⩾ ∑ i = 0 k − 1 ⌈ d 2 i ⌉ . {\displaystyle n\geqslant \sum _{i=0}^{k-1}\left\lceil {\frac {d}{2^{i}}}\right\rceil .} {\displaystyle n\geqslant \sum _{i=0}^{k-1}\left\lceil {\frac {d}{2^{i}}}\right\rceil .}

Proof

Let N ( k , d ) {\displaystyle N(k,d)} {\displaystyle 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 ⌉ . {\displaystyle N(k,d)\geqslant \sum _{i=0}^{k-1}\left\lceil {\frac {d}{2^{i}}}\right\rceil .} {\displaystyle 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 = [ 1 … 1 0 … 0 ∗ ∗ ∗ G ′ ] {\displaystyle G={\begin{bmatrix}1&\dots &1&0&\dots &0\\\ast &\ast &\ast &&G'&\\\end{bmatrix}}} {\displaystyle G={\begin{bmatrix}1&\dots &1&0&\dots &0\\\ast &\ast &\ast &&G'&\\\end{bmatrix}}}

The matrix G ′ {\displaystyle G'} {\displaystyle G'} generates a code C ′ {\displaystyle C'} {\displaystyle C'}, which is called the residual code of C . {\displaystyle C.} {\displaystyle C.} C ′ {\displaystyle C'} {\displaystyle C'} obviously has dimension k ′ = k − 1 {\displaystyle k'=k-1} {\displaystyle k'=k-1} and length n ′ = N ( k , d ) − d . {\displaystyle n'=N(k,d)-d.} {\displaystyle n'=N(k,d)-d.} C ′ {\displaystyle C'} {\displaystyle C'} has a distance d ′ , {\displaystyle d',} {\displaystyle d',} but we don't know it. Let u ∈ C ′ {\displaystyle u\in C'} {\displaystyle u\in C'} be such that w ( u ) = d ′ {\displaystyle w(u)=d'} {\displaystyle w(u)=d'}. There exists a vector v ∈ F 2 d {\displaystyle v\in \mathbb {F} _{2}^{d}} {\displaystyle v\in \mathbb {F} _{2}^{d}} such that the concatenation ( v | u ) ∈ C . {\displaystyle (v|u)\in C.} {\displaystyle (v|u)\in C.} Then w ( v ) + w ( u ) = w ( v | u ) ⩾ d . {\displaystyle w(v)+w(u)=w(v|u)\geqslant d.} {\displaystyle w(v)+w(u)=w(v|u)\geqslant d.} On the other hand, also ( v | u ) + r ∈ C , {\displaystyle (v|u)+r\in C,} {\displaystyle (v|u)+r\in C,} since r ∈ C {\displaystyle r\in C} {\displaystyle r\in C} and C {\displaystyle C} {\displaystyle C} is linear: w ( ( v | u ) + r ) ⩾ d . {\displaystyle w((v|u)+r)\geqslant d.} {\displaystyle w((v|u)+r)\geqslant d.} But

w ( ( v | u ) + r ) = w ( ( ( 1 , ⋯ , 1 ) + v ) | u ) = d − w ( v ) + w ( u ) , {\displaystyle w((v|u)+r)=w(((1,\cdots ,1)+v)|u)=d-w(v)+w(u),} {\displaystyle w((v|u)+r)=w(((1,\cdots ,1)+v)|u)=d-w(v)+w(u),}

so this becomes d − w ( v ) + w ( u ) ⩾ d {\displaystyle d-w(v)+w(u)\geqslant d} {\displaystyle d-w(v)+w(u)\geqslant d}. By summing this with w ( v ) + w ( u ) ⩾ d , {\displaystyle w(v)+w(u)\geqslant d,} {\displaystyle w(v)+w(u)\geqslant d,} we obtain d + 2 w ( u ) ⩾ 2 d {\displaystyle d+2w(u)\geqslant 2d} {\displaystyle d+2w(u)\geqslant 2d}. But w ( u ) = d ′ , {\displaystyle w(u)=d',} {\displaystyle w(u)=d',} so we get 2 d ′ ⩾ d . {\displaystyle 2d'\geqslant d.} {\displaystyle 2d'\geqslant d.} As d ′ {\displaystyle d'} {\displaystyle d'} is integral, we get d ′ ⩾ ⌈ d 2 ⌉ . {\displaystyle d'\geqslant \left\lceil {\tfrac {d}{2}}\right\rceil .} {\displaystyle d'\geqslant \left\lceil {\tfrac {d}{2}}\right\rceil .} This implies

n ′ ⩾ N ( k − 1 , ⌈ d 2 ⌉ ) , {\displaystyle n'\geqslant N\left(k-1,\left\lceil {\tfrac {d}{2}}\right\rceil \right),} {\displaystyle n'\geqslant N\left(k-1,\left\lceil {\tfrac {d}{2}}\right\rceil \right),}

so that

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

By induction over k we will eventually get

N ( k , d ) ⩾ ∑ i = 0 k − 1 ⌈ d 2 i ⌉ . {\displaystyle N(k,d)\geqslant \sum _{i=0}^{k-1}\left\lceil {\frac {d}{2^{i}}}\right\rceil .} {\displaystyle 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

⌈ ⌈ a / 2 k − 1 ⌉ 2 ⌉ = ⌈ a 2 k ⌉ {\displaystyle \left\lceil {\frac {\left\lceil a/2^{k-1}\right\rceil }{2}}\right\rceil =\left\lceil {\frac {a}{2^{k}}}\right\rceil } {\displaystyle \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.

Bound for the general case

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

n ⩾ ∑ i = 0 k − 1 ⌈ d q i ⌉ . {\displaystyle n\geqslant \sum _{i=0}^{k-1}\left\lceil {\frac {d}{q^{i}}}\right\rceil .} {\displaystyle 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.

See also

References

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