Second 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 $C$ be a ''q''-ary code of length $n$, i.e. a subset of $\mathbb_q^n$. Let $d$ be the minimum distance of $C$, i.e.

:$d = \min_ 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, .$

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, .$

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

If $d=2t+1$,

:$A_q(n,d) \leq \frac.$

If $d=2t+2$,

:$A_q(n,d) \leq \frac.$

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 \left\lfloor \frac \left\lfloor \cdots \left\lfloor \frac \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)$.

See also

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

References

*
*{{cite book , first1=William Cary , last1=Huffman , first2=Vera S. , last2=Pless , author-link2=Vera Pless , title=Fundamentals of Error-Correcting Codes , url=https://archive.org/details/fundamentalsofer0000huff , url-access=registration , publisher=Cambridge University Press , year=2003 , isbn=978-0-521-78280-7

Coding theory