Griesmer Bound

The Griesmer bound states that for all linear [s, n, d]-codes over Fb we have

s ≥ $\displaystyle \sum_{{i=0}}^{{n−1}}$$\displaystyle \left\lceil\vphantom{ \frac{d}{b^{i}}}\right.$$\displaystyle {\frac{{d}}{{b^{i}}}}$$\displaystyle \left.\vphantom{ \frac{d}{b^{i}}}\right\rceil$.

This bound is only valid for linear codes; it does not have a generalization for arbitrary codes or orthogonal arrays.

The result is due to [1] for binary codes and to [2] for the general case. It is established by constructing the residual code n−1 times and the fact that every [s, 1, d]-code has s ≥ d.

See Also

References

[1]James H. Griesmer.
A bound for error-correcting codes.
IBM Journal of Research and Development, 4:532–542, 1960.
[2]Gustave Solomon and Jack J. Stiffler.
Algebraically punctured cyclic codes.
Information and Control, 8(2):170–179, April 1965.
doi:10.1016/S0019-9958(65)90080-X
[3]F. Jessie MacWilliams and Neil J. A. Sloane.
The Theory of Error-Correcting Codes.
North-Holland, Amsterdam, 1977.
[4]Jürgen Bierbrauer.
Introduction to Coding Theory.
Discrete Mathematics and its Applications. Chapman & Hall/CRC, Boca Raton, London, New York, Washington D.C., 2004.
MR2079734 (2005f:94001)

Copyright

Copyright © 2004, 2005, 2006, 2007, 2008, 2009, 2010 by Rudolf Schürer and Wolfgang Ch. Schmid.
Cite this as: Rudolf Schürer and Wolfgang Ch. Schmid. “Griesmer Bound.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2024-09-05. http://mint.sbg.ac.at/desc_CBoundGriesmer.html

Show usage of this method