Plotkin bound
title: "Plotkin bound" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["coding-theory", "articles-containing-proofs"] topic_path: "general/coding-theory" source: "https://en.wikipedia.org/wiki/Plotkin_bound" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0
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 {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
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, x \neq y} d(x,y) and therefore
: \sum_{(x,y) \in C, x \neq y} d(x,y) = \sum_{i=1}^n 2s_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) \in C, x \neq y} d(x,y) \leq \frac{1}{2} n M^2.
Combining the upper and lower bounds for \sum_{(x,y) \in C, x \neq y} d(x,y) that we have just derived,
: M(M-1) d \leq \frac{1}{2} n M^2
which given that 2dn 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.
This completes the proof of the bound.
References
::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::