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. A code is considered "binary" if the codewords use symbols from the binary alphabet

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

over the finite field

be the minimum distance of

is the Hamming distance between

represents the maximum number of possible codewords in a binary code of length

and minimum distance

The Plotkin bound places a limit on this expression.

Theorem (Plotkin bound): i) If

, then ii) If

is odd and

, then iii) If

denotes the floor function.

be the Hamming distance of

be the number of elements in

The bound is proved by bounding the quantity

choices for

and for each such choice, there are

choices for

matrix whose rows are the elements of

be the number of zeros contained in the

'th column of

This means that the

'th column contains

Each choice of a zero and a one in the same column contributes exactly

) to the sum

and therefore The quantity on the right is maximized if and only if

(at this point of the proof we ignore the fact, that the

are integers), then Combining the upper and lower bounds for

is even, it follows that This completes the proof of the bound.