Plotkin bound

From Wikipedia, the free encyclopedia

The Plotkin bound is a bound on the size of binary codes of length $n$ and minimum distance $d$ satisfying $2 d > n$ .

1 Statement of the Bound
2 Proof
3 Reference
4 See also

[edit] 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 \neq y} d(x,y)$

where $d (x, y)$ is the Hamming distance between $x$ and $y$ . Let $r$ be the number of elements in $C$ .

Theorem (Plotkin bound):

If $2 d > n$ , then

$r \leq 2 \left\lfloor\frac{d}{2d-n}\right\rfloor$

where $\left\lfloor ~ \right\rfloor$ denotes the floor function.

[edit] Proof

Let $d (x, y)$ be the Hamming distance of $x$ and $y$ . 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 r(r-1) d$

On the other hand, let $A$ be an $r \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 $r - s i$ ones. Each choice of a zero and a one in the same column contributes exactly $2$ to the sum $\sum_{x,y \in C} d(x,y)$ and therefore