Johnson bound
title: "Johnson bound" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["coding-theory"] topic_path: "general/coding-theory" source: "https://en.wikipedia.org/wiki/Johnson_bound" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0
In applied mathematics, the Johnson bound (named after Selmer Martin Johnson) 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+2,
: 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 \left\lfloor \frac{n q^}{w} \left\lfloor \frac{(n-1)q^}{w-1} \left\lfloor \cdots \left\lfloor \frac{(n-w+e)q^*}{e} \right\rfloor \cdots \right\rfloor \right\rfloor \right\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).
References
::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::