Johnson bound
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 [math]\displaystyle{ C }[/math] be a q-ary code of length [math]\displaystyle{ n }[/math], i.e. a subset of [math]\displaystyle{ \mathbb{F}_q^n }[/math]. Let [math]\displaystyle{ d }[/math] be the minimum distance of [math]\displaystyle{ C }[/math], i.e.
- [math]\displaystyle{ d = \min_{x,y \in C, x \neq y} d(x,y), }[/math]
where [math]\displaystyle{ d(x,y) }[/math] is the Hamming distance between [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math].
Let [math]\displaystyle{ C_q(n,d) }[/math] be the set of all q-ary codes with length [math]\displaystyle{ n }[/math] and minimum distance [math]\displaystyle{ d }[/math] and let [math]\displaystyle{ C_q(n,d,w) }[/math] denote the set of codes in [math]\displaystyle{ C_q(n,d) }[/math] such that every element has exactly [math]\displaystyle{ w }[/math] nonzero entries.
Denote by [math]\displaystyle{ |C| }[/math] the number of elements in [math]\displaystyle{ C }[/math]. Then, we define [math]\displaystyle{ A_q(n,d) }[/math] to be the largest size of a code with length [math]\displaystyle{ n }[/math] and minimum distance [math]\displaystyle{ d }[/math]:
- [math]\displaystyle{ A_q(n,d) = \max_{C \in C_q(n,d)} |C|. }[/math]
Similarly, we define [math]\displaystyle{ A_q(n,d,w) }[/math] to be the largest size of a code in [math]\displaystyle{ C_q(n,d,w) }[/math]:
- [math]\displaystyle{ A_q(n,d,w) = \max_{C \in C_q(n,d,w)} |C|. }[/math]
Theorem 1 (Johnson bound for [math]\displaystyle{ A_q(n,d) }[/math]):
If [math]\displaystyle{ d=2t+1 }[/math],
- [math]\displaystyle{ 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)} }. }[/math]
If [math]\displaystyle{ d=2t+2 }[/math],
- [math]\displaystyle{ 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)} }. }[/math]
Theorem 2 (Johnson bound for [math]\displaystyle{ A_q(n,d,w) }[/math]):
(i) If [math]\displaystyle{ d \gt 2w, }[/math]
- [math]\displaystyle{ A_q(n,d,w) = 1. }[/math]
(ii) If [math]\displaystyle{ d \leq 2w }[/math], then define the variable [math]\displaystyle{ e }[/math] as follows. If [math]\displaystyle{ d }[/math] is even, then define [math]\displaystyle{ e }[/math] through the relation [math]\displaystyle{ d=2e }[/math]; if [math]\displaystyle{ d }[/math] is odd, define [math]\displaystyle{ e }[/math] through the relation [math]\displaystyle{ d = 2e - 1 }[/math]. Let [math]\displaystyle{ q^* = q - 1 }[/math]. Then,
- [math]\displaystyle{ 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 }[/math]
where [math]\displaystyle{ \lfloor ~~ \rfloor }[/math] is the floor function.
Remark: Plugging the bound of Theorem 2 into the bound of Theorem 1 produces a numerical upper bound on [math]\displaystyle{ A_q(n,d) }[/math].
See also
- Elias Bassalygo bound
- Gilbert–Varshamov bound
- Griesmer bound
- Hamming bound
- Plotkin bound
- Singleton bound
References
- Johnson, Selmer Martin (April 1962). "A new upper bound for error-correcting codes". IRE Transactions on Information Theory: 203–207.
- Huffman, William Cary; Pless, Vera S. (2003). Fundamentals of Error-Correcting Codes. Cambridge University Press. ISBN 978-0-521-78280-7. https://archive.org/details/fundamentalsofer0000huff.
 |  |
