## Improved Johnson Bound

In [1] the original Johnson bound is improved based on ideas already stated in Theorem 4 and the appendix of [2]. A concise formulation of this bound can also be found in [3].

Assuming that C is a binary (*s*, *N*, 2*u*)-even-weight-code with 0 ∈ C (every (*s*, *N*, 2*u*)- and (*s*−1, *N*, 2*u*−1)-code over ℤ_{2} is equivalent to such a code due to code truncation and adding a parity check bit), the improved Johnson bound states that

*N*max

*K*

_{2i},

*K*

_{2i+1}≤ 2

^{s−1}.

In this formula *K*_{r} = for *r* ≤ *u* and

*K*

_{r}≥ max,

for *r* > *u*. Furthermore, the integer *C*_{r} is the number of vectors in ℤ_{2}^{s} with weight *r* and distance *r* from C, which can be bounded from below by

*C*

_{r}≥ max0, –

*A*

_{2}(

*s*,

*d*, 2

*v*).

The integer *D*_{r} is the sum of the number of code words in C ∖ { 0} with distance *r* from each of these vectors, which can be bounded from above by

*D*

_{r}≤

*A*

_{2}(

*s*,

*d*, 2

*r*−2

*v*).

The integer *m*_{r} is defined as

*m*

_{r}:= 1 + ⌊

*D*

_{r}/

*C*

_{r}⌋.

Finally, *A*_{2}(*s*, *d*, *w*) denotes the maximum number of code words of a constant-weight code.

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

### See Also

The original Johnson bound

### References

[1] | Selmer M. Johnson. On upper bounds for unrestricted binary error-correcting codes. IEEE Transactions on Information Theory, 17(4):466–478, July 1971. |

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

[3] | Selmer M. Johnson. Upper bounds for constant weight error correcting codes. Discrete Mathematics, 3:109–124, 1972.doi:10.1016/0012-365X(72)90027-1 |

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