Johnson Bound

The Johnson bound states that every (s, N, d)-code over Fb satisfies

N$\displaystyle \left(\vphantom{V_{b}^{s}(r)+\frac{v_{b}^{s}(r+1)-\binom{d}{r}A_{b}(s,d,d)}{A_{b}(s,d,r+1)}}\right.$Vbs(r) + $\displaystyle {\frac{{v_{b}^{s}(r+1)-\binom{d}{r}A_{b}(s,d,d)}}{{A_{b}(s,d,r+1)}}}$$\displaystyle \left.\vphantom{V_{b}^{s}(r)+\frac{v_{b}^{s}(r+1)-\binom{d}{r}A_{b}(s,d,d)}{A_{b}(s,d,r+1)}}\right)$ ≤ bs

where r := ⌊(d – 1)/2⌋, Vbs(r) and vbs(r) denote the volume of a ball and spherical shell with radius r in the Hamming space Sbs, and Ab(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

NVbs(r) ≤ bs,

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

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: 2015-09-03. http://mint.sbg.ac.at/desc_CBoundJohnson.html

Show usage of this method