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 { 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 2 n over the finite field F 2 . Let d be the minimum distance of C , i.e.
d = min x , y ∈ C , 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 , then
A 2 ( n , d ) ≤ 2 ⌊ d 2 d − n ⌋ . ii) If d is odd and 2 d + 1 > n , then
A 2 ( n , d ) ≤ 2 ⌊ d + 1 2 d + 1 − n ⌋ . iii) If d is even, then
A 2 ( 2 d , d ) ≤ 4 d . iv) If d is odd, then
A 2 ( 2 d + 1 , d ) ≤ 4 d + 4 where ⌊ ⌋ denotes the floor function.
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 ∑ ( x , y ) ∈ 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 ) ≥ d for all x and y ( x ≠ y ), it follows that
∑ ( x , y ) ∈ C 2 , x ≠ y d ( x , y ) ≥ M ( M − 1 ) d . On the other hand, let A be an M × 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 ∑ x , y ∈ C d ( x , y ) and therefore
∑ x , y ∈ C d ( x , y ) = ∑ i = 1 n 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
∑ x , y ∈ C d ( x , y ) ≤ 1 2 n M 2 . Combining the upper and lower bounds for ∑ x , y ∈ C d ( x , y ) that we have just derived,
M ( M − 1 ) d ≤ 1 2 n M 2 which given that 2 d > n is equivalent to
M ≤ 2 d 2 d − n . Since M is even, it follows that
M ≤ 2 ⌊ d 2 d − n ⌋ . This completes the proof of the bound.
