Misplaced Pages

Revision as of 17:18, 16 October 2006

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

Statement of the Bound

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

${\displaystyle d=\min _{x,y\in C,x\neq y}d(x,y)}$

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

Theorem (Plotkin bound):

If ${\displaystyle 2d>n}$, then

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

where ${\displaystyle \lfloor ~\rfloor }$ denotes the floor function.

Proof

Let ${\displaystyle d(x,y)}$ be the Hamming distance of ${\displaystyle x}$ and ${\displaystyle y}$. The bound is proved by bounding the quantity ${\displaystyle \sum _{x,y\in C}d(x,y)}$ in two different ways.

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

${\displaystyle \sum _{x,y\in C}d(x,y)\geq r(r-1)d}$

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

${\displaystyle \sum _{x,y\in C}d(x,y)=\sum _{i=1}^{N}2s_{i}(r-s_{i})}$

If ${\displaystyle r}$ is even, then the quantity on the right is maximized when ${\displaystyle s_{i}=r/2}$ and then,

${\displaystyle \sum _{x,y\in C}d(x,y)\leq {\frac {1}{2}}Nr^{2}}$

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

${\displaystyle r(r-1)d\leq {\frac {1}{2}}Nr^{2}}$

which given that ${\displaystyle 2d>n}$ is equivalent to

${\displaystyle r\leq {\frac {2d}{2d-n}}}$

Since ${\displaystyle r}$ is even, it follows that

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

On the other hand, if ${\displaystyle r}$ is odd, then ${\displaystyle \sum _{i=1}^{N}2s_{i}(r-s_{i})}$ is maximized when ${\displaystyle s_{i}={\frac {r\pm 1}{2}}}$ which implies that

${\displaystyle \sum _{x,y\in C}d(x,y)\leq {\frac {1}{2}}N(r^{2}-1)}$

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

${\displaystyle r(r-1)d\leq {\frac {1}{2}}N(r^{2}-1)}$

or, using that ${\displaystyle 2d>n}$,

${\displaystyle r\leq {\frac {2d}{2d-n}}-1}$

Since r is an integer,

${\displaystyle r\leq \lfloor {\frac {2d}{2d-n}}-1\rfloor =\lfloor {\frac {2d}{2d-n}}\rfloor -1\leq 2\lfloor {\frac {d}{2d-n}}\rfloor }$

This completes the proof of the bound.

Reference

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

See also

• Singleton bound
• Hamming bound
• Gilbert-Varshamov bound
• Johnson bound

External links

• Lecture notes on coding theory including proof of the Plotkin bound.

• Coding theory