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:
![{\displaystyle n\geqslant \sum _{i=0}^{k-1}\left\lceil {\frac {d}{2^{i}}}\right\rceil .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dcef6fa70f456a48ad78b65efe42deefa0d68d93)
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
![{\displaystyle N(k,d)\geqslant \sum _{i=0}^{k-1}\left\lceil {\frac {d}{2^{i}}}\right\rceil .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3884d2b217b2ea42cde95574bf2840660b94ac8b)
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.
![{\displaystyle G={\begin{bmatrix}1&\dots &1&0&\dots &0\\\ast &\ast &\ast &&G'&\\\end{bmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/85c705eff18ad1e306d1cfecfd9146107b05073f)
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
![{\displaystyle w((v|u)+r)=w(((1,\cdots ,1)+v)|u)=d-w(v)+w(u),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/978661195e5eed96f97a4264df8ac6ffc02f81e1)
so this becomes
. By summing this with
we obtain
. But
so we get
As
is integral, we get
This implies
![{\displaystyle n'\geqslant N\left(k-1,\left\lceil {\tfrac {d}{2}}\right\rceil \right),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/821a81be6e18a157d85a8290c70b0c52778788bc)
so that
![{\displaystyle N(k,d)\geqslant d+N\left(k-1,\left\lceil {\tfrac {d}{2}}\right\rceil \right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/20444bd41d392e43a645d68be2666e6cc7802fce)
By induction over k we will eventually get
![{\displaystyle N(k,d)\geqslant \sum _{i=0}^{k-1}\left\lceil {\frac {d}{2^{i}}}\right\rceil .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3884d2b217b2ea42cde95574bf2840660b94ac8b)
Note that at any step the dimension decreases by 1 and the distance is halved, and we use the identity
![{\displaystyle \left\lceil {\frac {\left\lceil a/2^{k-1}\right\rceil }{2}}\right\rceil =\left\lceil {\frac {a}{2^{k}}}\right\rceil }](https://wikimedia.org/api/rest_v1/media/math/render/svg/acd7402768190f878dc09c48fda3733ff4ea4b6a)
for any integer a and positive integer k.
Bound for the general case[edit]
For a linear code over
, the Griesmer bound becomes:
![{\displaystyle n\geqslant \sum _{i=0}^{k-1}\left\lceil {\frac {d}{q^{i}}}\right\rceil .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d5fea6d5b01d70a0c1440060c3cbcdfb0ae5ca8e)
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.