Johnson bound

The Johnson bound is a limit on the size of error-correcting codes, as used in coding theory for data transmission or communications.
Definition

Let C be a q-ary code of length n, i.e. a subset of \( \mathbb{F}_q^n \). Let d be the minimum distance of C, i.e.

\( d = \min_{x,y \in C, x \neq y} d(x,y) , \)

where d(x,y) is the Hamming distance between x and y.

Let\( C_q(n,d) \) be the set of all q-ary codes with length n and minimum distance d and let \(C_q(n,d,w) \) denote the set of codes in \(C_q(n,d) \) such that every element has exactly w nonzero entries.

Denote by |C| the number of elements in C. Then, we define A_q(n,d) to be the largest size of a code with length n and minimum distance d:

\( A_q(n,d) = \max_{C \in C_q(n,d)} |C|. \)

Similarly, we define \(A_q(n,d,w) to be the largest size of a code in \( C_q(n,d,w): \)

\( A_q(n,d,w) = \max_{C \in C_q(n,d,w)} |C|. \)

Theorem 1 (Johnson bound for \(A_q(n,d)): \)

If d=2t+1,

\( A_q(n,d) \leq \frac{q^n}{\sum_{i=0}^t {n \choose i} (q-1)^i + \frac{{n \choose t+1} (q-1)^{t+1} - {d \choose t} A_q(n,d,d)}{A_q(n,d,t+1)} }. \)

If d=2t,

\( A_q(n,d) \leq \frac{q^n}{\sum_{i=0}^t {n \choose i} (q-1)^i + \frac{{n \choose t+1} (q-1)^{t+1} }{A_q(n,d,t+1)} }. \)

Theorem 2 (Johnson bound for \( A_q(n,d,w)): \)

(i) If d > 2w,

\( A_q(n,d,w) = 1. \)

(ii) If \(d \leq 2w \), then define the variable e as follows. If d is even, then define e through the relation d=2e; if d is odd, define e through the relation d = 2e - 1. Let \( q^* = q - 1 \). Then,

\( A_q(n,d,w) \leq \lfloor \frac{n q^*}{w} \lfloor \frac{(n-1)q^*}{w-1} \lfloor \cdots \lfloor \frac{(n-w+e)q^*}{e} \rfloor \cdots \rfloor \rfloor \)

where \(\lfloor ~~ \rfloor \) is the floor function.

Remark: Plugging the bound of Theorem 2 into the bound of Theorem 1 produces a numerical upper bound on \( A_q(n,d). \)
See also

Singleton bound
Hamming bound
Plotkin bound
Elias Bassalygo bound
Gilbert–Varshamov bound
Griesmer bound

References

S. M. Johnson, "A new upper bound for error-correcting codes," IRE Transactions on Information Theory, pp. 203–207, April 1962.
W. Cary Huffman, Vera Pless, Fundamentals of Error-Correcting Codes, Cambridge University Press, 2003.