## Johnson Bound

The Johnson bound states that every (*s*, *N*, *d*)-code over **F**_{b} satisfies

*N*

*V*

_{b}

^{s}(

*r*) + ≤

*b*

^{s}

where *r* := ⌊(*d* – 1)/2⌋, *V*_{b}^{s}(*r*) and *v*_{b}^{s}(*r*) denote the volume of a ball and spherical shell with radius *r* in the Hamming space *S*_{b}^{s}, and *A*_{b}(*s*, *d*, *w*) denotes the maximum number of code words of a constant-weight code.

The Johnson bound is a sharpened version of the sphere-packing bound

*NV*

_{b}

^{s}(

*r*) ≤

*b*

^{s},

which is obtained by using a lower bound on the number of vectors with distance *r* + 1 from C in addition to the vectors with distance ≤ *r* from C taken into account by the sphere-packing bound.

For *b* = 2 this result is due to [1, Theorem 1]. The generalization for arbitrary *b* is from [2, Section 2.1.1].

MinT includes all Johnson bounds up to *s* = 100000.

### See Also

[3, Ch. 17, Th. 13]

For

*b*= 2 the result can sharpened to the improved Johnson bound

### References

[1] | Selmer M. Johnson. A new upper bound for error-correcting codes. IEEE Transactions on Information Theory, 8(3):203–207, April 1962. |

[2] | Andries E. Brouwer. Bounds on the size of linear codes. In Vera S. Pless and W. Cary Huffman, editors, Handbook of Coding Theory, volume 1, pages 295–461. Elsevier Science, 1998. |

[3] | F. Jessie MacWilliams and Neil J. A. Sloane.The Theory of Error-Correcting Codes.North-Holland, Amsterdam, 1977. |

### 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. “Johnson Bound.”
From MinT—the database of optimal net, code, OA, and OOA parameters.
Version: 2008-04-04.
http://mint.sbg.ac.at/desc_CBoundJohnson.html