Inverse hyperbolic function

The Johnson bound 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$,

$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 \lfloor {\frac {nq^{*}}{w}}\lfloor {\frac {(n-1)q^{*}}{w-1}}\lfloor \cdots \lfloor {\frac {(n-w+e)q^{*}}{e}}\rfloor \cdots \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

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

References

• S. M. Johnson, "A new upper bound for error-correcting codes," IRE Transactions on Information Theory, pp. 203–207, April 1962.
• W. Cary Huffman, Vera Pless, Fundamentals of Error-Correcting Codes, Cambridge University Press, 2003.