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=\underset{x,y\in C,x\ne y}{\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)=\underset{C\in C_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)=\underset{C\in C_q(n,d,w)}{\max }|C|.$

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

If $d=2t+1$,

$A_q(n,d)\le \frac{q^n}{\sum _{i=0}^t(\genfrac{}{}{0ex}{}{n}{i})(q-1{)}^i+\frac{(\genfrac{}{}{0ex}{}{n}{t+1})(q-1{)}^{t+1}-(\genfrac{}{}{0ex}{}{d}{t})A_q(n,d,d)}{A_q(n,d,t+1)}}.$

If $d=2t+2$,

$A_q(n,d)\le \frac{q^n}{\sum _{i=0}^t(\genfrac{}{}{0ex}{}{n}{i})(q-1{)}^i+\frac{(\genfrac{}{}{0ex}{}{n}{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\le 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)\le \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 \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

• 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.