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} n M^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} n M^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.

See also

References

This article is issued from Wikipedia - version of the Saturday, December 26, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.