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.

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

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

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

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

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

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

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

${\displaystyle A_{q}(n,d,w)=\max _{C\in C_{q}(n,d,w)}|C|.}${\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)}${\displaystyle A_{q}(n,d)}):

If ${\displaystyle d=2t+1}${\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)}}}}.}${\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 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)}}}}.}${\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)}${\displaystyle A_{q}(n,d,w)}):

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

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

(ii) If ${\displaystyle d\leq 2w}${\displaystyle d\leq 2w}, then define the variable ${\displaystyle e}${\displaystyle e} as follows. If ${\displaystyle d}${\displaystyle d} is even, then define ${\displaystyle e}${\displaystyle e} through the relation ${\displaystyle d=2e}${\displaystyle d=2e}; if ${\displaystyle d}${\displaystyle d} is odd, define ${\displaystyle e}${\displaystyle e} through the relation ${\displaystyle d=2e-1}${\displaystyle d=2e-1}. Let ${\displaystyle q^{*}=q-1}${\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 }${\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 }${\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)}${\displaystyle A_{q}(n,d)}.

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

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

• Coding theory