Plotkin bound

In the mathematics of coding theory, the Plotkin bound is a bound on the size of binary codes of length $n$ and minimum distance $d$.

Statement of the Bound

Let $C$ be a binary code of length $n$, i.e. a subset of $mathbb\{F\}\_2^n$. Let $d$ be the minimum distance of $C$, i.e.

:$d\; =\; min\_\{x,y\; in\; C,\; x\; eq\; y\}\; d(x,y)$

where $d(x,y)$ is the Hamming distance between $x$ and $y$. The expression $A\_\{2\}(n,d)$ represents the maximum number of possible codewords in a binary code of length $n$ and minimum distance $d$. The Plotkin bound places a limit on this expression.

Theorem (Plotkin bound):

i) If $d$ is even and $2d\; >\; n$, then

:$A\_\{2\}(n,d)\; leq\; 2\; leftlfloorfrac\{d\}\{2d-n\}\; ight\; floor$

ii) If $d$ is odd and $2d+1\; >\; n$, then

:$A\_\{2\}(n,d)\; leq\; 2\; leftlfloorfrac\{d+1\}\{2d+1-n\}\; ight\; floor$

iii) If $d$ is even, then

:$A\_\{2\}(2d,d)\; leq\; 4d$

iv) If $d$ is odd, then

:$A\_\{2\}(2d+1,d)\; leq\; 4d+4$

where $leftlfloor\; ~\; ight\; floor$ denotes the floor function.

Proof of case i

Let $d(x,y)$ be the Hamming distance of $x$ and $y$, and $M$ be the number of elements in $C$ (thus, $M$ is equal to $A\_\{2\}(n,d)$). The bound is proved by bounding the quantity $sum\_\{x,y\; in\; C\}\; d(x,y)$ in two different ways.

On the one hand, there are $r$ choices for $x$ and for each such choice, there are $r-1$ choices for $y$. Since by definition $d(x,y)\; geq\; d$ for all $x$ and $y$, it follows that

:$sum\_\{x,y\; in\; C\}\; d(x,y)\; geq\; M(M-1)\; d$

On the other hand, let $A$ be an $M\; imes\; n$ matrix whose rows are the elements of $C$. Let $s\_i$ be the number of zeros contained in the $i$'th column of $A$. This means that the $i$'th column contains $M-s\_i$ ones. Each choice of a zero and a one in the same column contributes exactly $2$ (because $d(x,y)=d(y,x)$) to the sum $sum\_\{x,y\; in\; C\}\; d(x,y)$ and therefore

:$sum\_\{x,y\; in\; C\}\; d(x,y)\; =\; sum\_\{i=1\}^n\; 2s\_i\; (M-s\_i)$

If $M$ is even, then the quantity on the right is maximized when $s\_i\; =\; M/2$ and then,

:$sum\_\{x,y\; in\; C\}\; d(x,y)\; leq\; frac\{1\}\{2\}\; n\; M^2$

Combining the upper and lower bounds for $sum\_\{x,y\; in\; C\}\; d(x,y)$ that we have just derived,

:$M(M-1)\; d\; leq\; frac\{1\}\{2\}\; n\; M^2$

which given that $2d>n$ is equivalent to

:$M\; leq\; frac\{2d\}\{2d-n\}$

Since $M$ is even, it follows that

:$M\; leq\; 2\; lfloor\; frac\{d\}\{2d-n\}\; floor$

On the other hand, if $M$ is odd, then $sum\_\{i=1\}^n\; 2s\_i\; (M-s\_i)$ is maximized when $s\_i\; =\; frac\{M\; pm\; 1\}\{2\}$ which implies that

:$sum\_\{x,y\; in\; C\}\; d(x,y)\; leq\; frac\{1\}\{2\}\; n\; (M^2-1)$

Combining the upper and lower bounds for $sum\_\{x,y\; in\; C\}\; d(x,y)$, this means that

:$M(M-1)\; d\; leq\; frac\{1\}\{2\}\; n\; (M^2-1)$

or, using that $2d\; >\; n$,

:$M\; leq\; frac\{2d\}\{2d-n\}\; -\; 1$

Since M is an integer,

:$M\; leq\; lfloor\; frac\{2d\}\{2d-n\}\; -\; 1\; floor\; =\; lfloor\; frac\{2d\}\{2d-n\}\; floor\; -1\; leq\; 2\; lfloor\; frac\{d\}\{2d-n\}\; floor$

This completes the proof of the bound.

References

*Binary codes with specified minimum distance, M. Plotkin, IRE Transactions on Information Theory, 6:445-450, 1960.

ee also

*Singleton bound
*Hamming bound
*Gilbert-Varshamov bound
*Johnson bound