# Johnson bound

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Johnson_bound
> Markdown URL: https://mediated.wiki/source/Johnson_bound.md
> Source: https://en.wikipedia.org/wiki/Johnson_bound
> Source revision: 1188380060
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In applied mathematics, the **Johnson bound** (named after [Selmer Martin Johnson](/source/Selmer_Martin_Johnson)) is a limit on the size of [error-correcting codes](/source/Error-correcting_code), as used in [coding theory](/source/Coding_theory) for [data transmission](/source/Data_transmission) or communications.

## Definition

Let C be a *q*-ary [code](/source/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](/source/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](/source/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

- [Elias Bassalygo bound](/source/Elias_Bassalygo_bound)
- [Gilbert–Varshamov bound](/source/Gilbert%E2%80%93Varshamov_bound)
- [Griesmer bound](/source/Griesmer_bound)
- [Hamming bound](/source/Hamming_bound)
- [Plotkin bound](/source/Plotkin_bound)
- [Singleton bound](/source/Singleton_bound)

## References

- Johnson, Selmer Martin (April 1962). "A new upper bound for error-correcting codes". *[IRE Transactions on Information Theory](/source/IRE_Transactions_on_Information_Theory)*
- Huffman, William Cary & Pless, Vera S. (2003). [*Fundamentals of Error-Correcting Codes*](https://archive.org/details/fundamentalsofer0000huff). [Cambridge University Press](/source/Cambridge_University_Press). ISBN 978-0-521-78280-7.

---
Adapted from the Wikipedia article [Johnson bound](https://en.wikipedia.org/wiki/Johnson_bound) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Johnson_bound?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.