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 $\{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 ${\mathbb {F}}_{2}^{n}$ over the finite field $\mathbb {F} _{2}$ . 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$ . 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\left\lfloor {\frac {d}{2d-n}}\right\rfloor .

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

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

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 $\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_{{2}}(n,d)$ ). The bound is proved by bounding the quantity $\sum _{{(x,y)\in C^{2},x\neq y}}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 _{{(x,y)\in C^{2},x\neq y}}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 _{{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}).

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 _{{x,y\in C}}d(x,y)\leq {\frac {1}{2}}nM^{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}}nM^{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\left\lfloor {\frac {d}{2d-n}}\right\rfloor .

This completes the proof of the 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

This article is issued from Wikipedia - version of the 10/31/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Plotkin bound

Statement of the bound

Proof of case i)

See also

References