## Restricted Johnson Bound

Let *A*_{b}(*s*, *d*, *w*) denote the maximum number of code words of a constant-weight (*s*, *N*, *d*)-code.

MinT uses the following methods for obtaining an upper bound on *A*_{b}(*s*, *d*, *w*):

### Trivial Cases

*A*_{b}(*s*,*s*+ 1,*w*) = 1 (a single code word with weight*w*).*A*_{b}(*s*,*d*,*s*) =*b*−1 if*d*≤*s*(the [*s*, 1,*s*]-repetition code without the zero vector).*A*_{b}(*s*,*d*,*w*) = 1 if*d*> 2*w*(see also [1, Ch. 17, Th. 1(c)]).*A*_{b}(*s*, 2*w*,*w*) = ⌊*s*/*w*⌋ (see also [1, Ch. 17, Th. 1(d)]).*A*_{2}(*s*,*d*,*w*) =*A*_{2}(*s*+ 1,*d*+ 1,*w*) if*d*is odd (similar to adding a parity check bit and truncation).

### Special Results

*A*_{2}(12, 6, 5) = 12. (Stated in the appendix of [2]. A proof can be found in the appendix of [3]. See also [1, Ch. 17, Problem 7]).*A*_{2}(13, 6, 5) = 18. (Stated in the appendix of [2]. See also [1, Ch. 17, Problem 8]).*A*_{2}(24, 8, 12) = 2576. [1, Ch. 17, p. 530]

### Upper Bounds

In those cases where the exact value of *A*_{b}(*s*, *d*, *w*) is not known, MinT uses the strongest of the following bounds. Note that the first two of these bounds are recursive.

We have

*A*_{b}(*s*,*d*,*w*) ≤ ⌊*A*_{b}(*s*– 1,*d*,*w*– 1)⌋.The result for

*b*= 2 is given in [2, eq. (5)] (see also [1, Ch. 17, Th. 4]), the one for arbitrary*b*in [4, Section 2.2.1].If

*w*<*s*, then*A*_{b}(*s*,*d*,*w*) ≤ ⌊*A*_{b}(*s*– 1,*d*,*w*)⌋.The result for

*b*= 2 is given in [2, eq. (11)] (see also [1, Ch. 17, Problem 2]), the one for arbitrary*b*in [4, Section 2.2.1].We have

*A*_{b}(*s*,*d*,*w*) ≤ ⌊⌋provided that the denominator is positive. The result for

*b*= 2 is given in [2, Theorem 3] (see also [1, Ch. 17, Th. 2]), the one for arbitrary*b*in [4, Section 2.3.1].If

*b*= 2,*d*is even,*N*=*A*_{2}(*s*,*d*,*w*), and*wN*(the total number of 1s in all code words) is written as*wN*=*αs*+*β*with*α*,*β*∈ ℕ_{0}and 0 ≤*β*<*s*, then*sα*(*α*– 1) + 2*αβ*≤ (*w*−*d*/2)*N*(*N*−1)

### References

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

[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. On upper bounds for unrestricted binary error-correcting codes. IEEE Transactions on Information Theory, 17(4):466–478, July 1971. |

[4] | 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. |

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