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. 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, i.e.

is the Hamming distance and minimum distance. The Plotkin bound places a limit on this expression.

Theorem (Plotkin bound):

, then

, then

is even, then

is odd, then

denotes the floor function.

Proof of case i

be the Hamming distance in two different ways.

), it follows that

and therefore

are integers), then

that we have just derived,

is equivalent to

is even, it follows that

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