User:ECCclass/Plotkin

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

Statement of the bound

We say a code is binary, if the codewords use symbols from the binary alphabet $\{0,1\}$. In particular, if all codewords have a fixed length n, we speak of a binary code of length n. Equivalently, we may consider in this case the codewords as 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}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$, it follows that

$\sum _{x,y\in C,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}).$

If $M$ is even, then the quantity on the right is maximized if and only if $s_{i}=M/2$ holds for all $i$, 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 .$

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

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

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

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

or, using that $2d>n$,

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

Since $M$ is an integer,

$M\leq \left\lfloor {\frac {2d}{2d-n}}-1\right\rfloor =\left\lfloor {\frac {2d}{2d-n}}\right\rfloor -1\leq 2\left\lfloor {\frac {d}{2d-n}}\right\rfloor .$

This completes the proof of the bound.

See also

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

References

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

Category:Articles containing proofs