Encyclopedia

Johnson bound

Wikipedia contributorsAdapted for Fathomly · View authors

1 min read
Source updated December 5, 2023

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.

01Definition

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,

$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)$ .

Watch videos about Johnson boundExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Johnson bound”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Johnson bound

01Definition

Sources and credits

Related topics

Elias Bassalygo bound

Gilbert-Varshamov bound

Griesmer bound