Plotkin Bound

In the mathematics of coding theory, the Plotkin bound, named after Morris Plotkin, is a limit (or bound) on the maximum possible number of codewords in binary codes of given length ''n'' and given minimum distance ''d''.

Statement of the bound

A code is considered "binary" if the codewords use symbols from the binary alphabet $\$. In particular, if all codewords have a fixed length ''n'',
then the binary code has length ''n''. Equivalently, in this case the codewords can be considered elements of vector space $\mathbb_2^n$ over the finite field $\mathbb_2$. Let $d$ be the minimum
distance of $C$, i.e.
:$d = \min_ d(x,y)$
where $d(x,y)$ is the Hamming distance between $x$ and $y$. The expression $A_(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_(n,d) \leq 2 \left\lfloor\frac\right\rfloor.$

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

:$A_(n,d) \leq 2 \left\lfloor\frac\right\rfloor.$

iii) If $d$ is even, then

:$A_(2d,d) \leq 4d.$

iv) If $d$ is odd, then

:$A_(2d+1,d) \leq 4d+4$

where $\left\lfloor ~ \right\rfloor$ 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_(n,d)$). The bound is proved by bounding the quantity $\sum_ d(x,y)$ in two different ways.

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

:$\sum_ d(x,y) \geq M(M-1) d.$

On the other hand, let $A$ be an $M \times 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_ d(x,y)$ and therefore

:$\sum_ d(x,y) = \sum_^n 2s_i (M-s_i).$

The quantity on the right is maximized if and only if $s_i = M/2$ holds for all $i$ (at this point of the proof we ignore the fact, that the $s_i$ are integers), then

:$\sum_ d(x,y) \leq \frac n M^2.$

Combining the upper and lower bounds for $\sum_ d(x,y)$ that we have just derived,

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

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

:$M \leq \frac.$

Since $M$ is even, it follows that

:$M \leq 2 \left\lfloor \frac \right\rfloor.$

This completes the proof of the bound.

See also

* Singleton bound
* Hamming bound
* Elias-Bassalygo bound
* Gilbert-Varshamov bound
* Johnson bound
* Griesmer bound
* Diamond code

References

* {{cite journal , title=Binary codes with specified minimum distance , author-first=Morris , author-last=Plotkin , journal=IRE Transactions on Information Theory , volume=6 , pages=445–450 , date=1960 , issue=4 , doi=10.1109/TIT.1960.1057584

Coding theory
Articles containing proofs