Misplaced Pages

Revision as of 16:11, 29 October 2016

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 ${\displaystyle \{0,1\}}$. 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 ${\displaystyle \mathbb {F} _{2}^{n}}$ over the finite field ${\displaystyle \mathbb {F} _{2}}$. 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}$. The expression ${\displaystyle A_{2}(n,d)}$ represents the maximum number of possible codewords in a binary code of length ${\displaystyle n}$ and minimum distance ${\displaystyle d}$. The Plotkin bound places a limit on this expression.

Theorem (Plotkin bound):

i) If ${\displaystyle d}$ is even and ${\displaystyle 2d>n}$, then

${\displaystyle A_{2}(n,d)\leq 2\left\lfloor {\frac {d}{2d-n}}\right\rfloor .}$

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

${\displaystyle A_{2}(n,d)\leq 2\left\lfloor {\frac {d+1}{2d+1-n}}\right\rfloor .}$

iii) If ${\displaystyle d}$ is even, then

${\displaystyle A_{2}(2d,d)\leq 4d.}$

iv) If ${\displaystyle d}$ is odd, then

${\displaystyle A_{2}(2d+1,d)\leq 4d+4}$

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

Proof of case i)

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

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

${\displaystyle \sum _{(x,y)\in C^{2},x\neq y}d(x,y)\geq M(M-1)d.}$

On the other hand, let ${\displaystyle A}$ be an ${\displaystyle M\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 M-s_{i}}$ ones. Each choice of a zero and a one in the same column contributes exactly ${\displaystyle 2}$ (because ${\displaystyle d(x,y)=d(y,x)}$) 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}(M-s_{i}).}$

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

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

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

${\displaystyle M(M-1)d\leq {\frac {1}{2}}nM^{2}}$

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

${\displaystyle M\leq {\frac {2d}{2d-n}}.}$

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

${\displaystyle M\leq 2\left\lfloor {\frac {d}{2d-n}}\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

References

• Plotkin, M. (1960), "Binary codes with specified minimum distance", IRE Transactions on Information Theory, 6: 445–450, doi:10.1109/TIT.1960.1057584

• Coding theory