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 {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 \left\lfloor {\frac {nq^{*}}{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.

Remark: Plugging the bound of Theorem 2 into the bound of Theorem 1 produces a numerical upper bound on $A_{q}(n,d)$ .

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.

Johnson bound

Definition

See also

References