Johnson bound#2

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

:$d\; =\; \backslash min\_\{x,y\; \backslash in\; C,\; x\; \backslash 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)\; =\; \backslash max\_\{C\; \backslash 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)\; =\; \backslash max\_\{C\; \backslash in\; C\_q(n,d,w)\}\; |C|.$

Theorem 1 (Johnson bound for $A\_q(n,d)$):

If $d=2t+1$,

:$A\_q(n,d)\; \backslash leq\; \backslash frac\{q^n\}\{\backslash sum\_\{i=0\}^t\; \{n\; \backslash choose\; i\}\; (q-1)^i\; +\; \backslash frac\{\{n\; \backslash choose\; t+1\}\; (q-1)^\{t+1\}\; -\; \{d\; \backslash choose\; t\}\; A\_q(n,d,d)\}\{A\_q(n,d,t+1)\}\; \}.$

If $d=2t+2$,

:$A\_q(n,d)\; \backslash leq\; \backslash frac\{q^n\}\{\backslash sum\_\{i=0\}^t\; \{n\; \backslash choose\; i\}\; (q-1)^i\; +\; \backslash frac\{\{n\; \backslash 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\; \backslash 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)\; \backslash leq\; \backslash left\backslash lfloor\; \backslash frac\{n\; q^*\}\{w\}\; \backslash left\backslash lfloor\; \backslash frac\{(n-1)q^*\}\{w-1\}\; \backslash left\backslash lfloor\; \backslash cdots\; \backslash left\backslash lfloor\; \backslash frac\{(n-w+e)q^*\}\{e\}\; \backslash right\backslash rfloor\; \backslash cdots\; \backslash right\backslash rfloor\; \backslash right\backslash rfloor\; \backslash right\backslash rfloor$

where $\backslash lfloor\; ~~\; \backslash 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)$.

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

• {{cite journal |first=Selmer Martin |last=Johnson |author-link=Selmer Martin Johnson |title=A new upper bound for error-correcting codes |journal=IRE Transactions on Information Theory |pages=203–207 |date=April 1962}}
• {{cite book |first1=William Cary |last1=Huffman |first2=Vera S. |last2=Pless |author-link2=Vera Pless |title=Fundamentals of Error-Correcting Codes |url=https://archive.org/details/fundamentalsofer0000huff |url-access=registration |publisher=Cambridge University Press |year=2003 |isbn=978-0-521-78280-7}}

Category:Coding theory