Plotkin bound

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

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[edit]

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

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[edit]

References[edit]

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