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 ${\displaystyle C}$ be a q-ary code of length ${\displaystyle n}$, i.e. a subset of ${\displaystyle \mathbb {F} _{q}^{n}}$. Let ${\displaystyle d}$ be the minimum distance of ${\displaystyle C}$, i.e.

${\displaystyle d=\min _{x,y\in C,x\neq y}d(x,y),}$

where ${\displaystyle d(x,y)}$ is the Hamming distance between ${\displaystyle x}$ and ${\displaystyle y}$.

Let ${\displaystyle C_{q}(n,d)}$ be the set of all q-ary codes with length ${\displaystyle n}$ and minimum distance ${\displaystyle d}$ and let ${\displaystyle C_{q}(n,d,w)}$ denote the set of codes in ${\displaystyle C_{q}(n,d)}$ such that every element has exactly ${\displaystyle w}$ nonzero entries.

Denote by ${\displaystyle |C|}$ the number of elements in ${\displaystyle C}$. Then, we define ${\displaystyle A_{q}(n,d)}$ to be the largest size of a code with length ${\displaystyle n}$ and minimum distance ${\displaystyle d}$:

${\displaystyle A_{q}(n,d)=\max _{C\in C_{q}(n,d)}|C|.}$

Similarly, we define ${\displaystyle A_{q}(n,d,w)}$ to be the largest size of a code in ${\displaystyle C_{q}(n,d,w)}$:

${\displaystyle A_{q}(n,d,w)=\max _{C\in C_{q}(n,d,w)}|C|.}$

Theorem 1 (Johnson bound for ${\displaystyle A_{q}(n,d)}$):

If ${\displaystyle d=2t+1}$,

${\displaystyle 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 ${\displaystyle d=2t+2}$,

${\displaystyle 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 ${\displaystyle A_{q}(n,d,w)}$):

(i) If ${\displaystyle d>2w,}$

${\displaystyle A_{q}(n,d,w)=1.}$

(ii) If ${\displaystyle d\leq 2w}$, then define the variable ${\displaystyle e}$ as follows. If ${\displaystyle d}$ is even, then define ${\displaystyle e}$ through the relation ${\displaystyle d=2e}$; if ${\displaystyle d}$ is odd, define ${\displaystyle e}$ through the relation ${\displaystyle d=2e-1}$. Let ${\displaystyle q^{*}=q-1}$. Then,

${\displaystyle 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 ${\displaystyle \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 ${\displaystyle A_{q}(n,d)}$.

See also

• Singleton bound
• Hamming bound
• Plotkin bound
• Elias Bassalygo bound
• Gilbert–Varshamov bound
• Griesmer 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.