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 ds (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

(α – 1) + 2αβ ≤ (wd /2)N(N−1)

must hold. [2, eq. (6)] (see also [1, Ch. 17, Th. 3])

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.