Plotkin bound explained

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

\{ 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 F ^{n} _{2} over the finite field F _{2} . Let d be the minimum distance of C , i.e. d = min _{x,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 2 d > n , thenA _{2} (n,d) \leq 2 \left\lfloor (d)/(2 d - n) \right\rfloor.

ii) If

d is odd and 2 d +1 > n , thenA _{2} (n,d) \leq 2 \left\lfloor (d +1)/(2 d +1- n) \right\rfloor.

iii) If

d is even, thenA _{2} ( 2 d,d) \leq 4 d.

iv) If

d is odd, thenA _{2} ( 2 d +1 ,d) \leq 4 d +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 ≠ 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 ≠ y ), it follows that\sum _{(x,y) \in C ^{2,} x ≠ y} d(x,y) \geq M(M -1 ) d.

On the other hand, let

A be an M x 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)} d(x,y) and therefore\sum _{(x,y)} d(x,y) = \sum ^{n} _{i =1} 2 s _{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)} d(x,y) \leq (1)/(2) n M ^{2.}

Combining the upper and lower bounds for

\sum _{(x,y)} d(x,y) that we have just derived,M(M -1 ) d \leq (1)/(2) n M ^{2}

which given that

2 d>n is equivalent toM \leq (2 d)/(2 d - n) .

Since

M is even, it follows thatM \leq 2 \left\lfloor (d)/(2 d - n) \right\rfloor.

This completes the proof of the bound.

See also

• Diamond code
• Elias Bassalygo bound
• Gilbert–Varshamov bound
• Griesmer bound
• Hamming bound
• Johnson bound
• Singleton bound

References

• Binary codes with specified minimum distance . Morris . Plotkin . . 6 . 445–450 . 1960 . 4 . 10.1109/TIT.1960.1057584.