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+2$ ,

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,