Plotkin bound

From Wikipedia, the free encyclopedia

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}).

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

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. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.