Restricted Johnson Bound
Let Ab(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 Ab(s, d, w):
Trivial Cases
Ab(s, s + 1, w) = 1 (a single code word with weight w).
Ab(s, d, s) = b−1 if d ≤ s (the [s, 1, s]-repetition code without the zero vector).
Ab(s, d, w) = 1 if d > 2w (see also [1, Ch. 17, Th. 1(c)]).
Ab(s, 2w, w) = ⌊s/w⌋ (see also [1, Ch. 17, Th. 1(d)]).
A2(s, d, w) = A2(s + 1, d + 1, w) if d is odd (similar to adding a parity check bit and truncation).
Special Results
A2(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]).
A2(13, 6, 5) = 18. (Stated in the appendix of [2]. See also [1, Ch. 17, Problem 8]).
A2(24, 8, 12) = 2576. [1, Ch. 17, p. 530]
Upper Bounds
In those cases where the exact value of Ab(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
Ab(s, d, w) ≤ ⌊
Ab(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
Ab(s, d, w) ≤ ⌊
Ab(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
Ab(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 = A2(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: 2015-09-03.
http://mint.sbg.ac.at/desc_CBoundRestrictedJohnson.html