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.

Statement of the bound

A code is considered "binary" if the codewords use symbols from the binary alphabet [math]\displaystyle{ \{0,1\} }[/math]. 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 [math]\displaystyle{ \mathbb{F}_2^n }[/math] over the finite field [math]\displaystyle{ \mathbb{F}_2 }[/math]. Let [math]\displaystyle{ d }[/math] be the minimum distance of [math]\displaystyle{ C }[/math], i.e.

[math]\displaystyle{ d = \min_{x,y \in C, x \neq y} d(x,y) }[/math]

where [math]\displaystyle{ d(x,y) }[/math] is the Hamming distance between [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math]. The expression [math]\displaystyle{ A_{2}(n,d) }[/math] represents the maximum number of possible codewords in a binary code of length [math]\displaystyle{ n }[/math] and minimum distance [math]\displaystyle{ d }[/math]. The Plotkin bound places a limit on this expression.

Theorem (Plotkin bound):

i) If [math]\displaystyle{ d }[/math] is even and [math]\displaystyle{ 2d \gt n }[/math], then

[math]\displaystyle{ A_{2}(n,d) \leq 2 \left\lfloor\frac{d}{2d-n}\right\rfloor. }[/math]

ii) If [math]\displaystyle{ d }[/math] is odd and [math]\displaystyle{ 2d+1 \gt n }[/math], then

[math]\displaystyle{ A_{2}(n,d) \leq 2 \left\lfloor\frac{d+1}{2d+1-n}\right\rfloor. }[/math]

iii) If [math]\displaystyle{ d }[/math] is even, then

[math]\displaystyle{ A_{2}(2d,d) \leq 4d. }[/math]

iv) If [math]\displaystyle{ d }[/math] is odd, then

[math]\displaystyle{ A_{2}(2d+1,d) \leq 4d+4 }[/math]

where [math]\displaystyle{ \left\lfloor ~ \right\rfloor }[/math] denotes the floor function.

Proof of case i

Let [math]\displaystyle{ d(x,y) }[/math] be the Hamming distance of [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math], and [math]\displaystyle{ M }[/math] be the number of elements in [math]\displaystyle{ C }[/math] (thus, [math]\displaystyle{ M }[/math] is equal to [math]\displaystyle{ A_{2}(n,d) }[/math]). The bound is proved by bounding the quantity [math]\displaystyle{ \sum_{(x,y) \in C^2, x\neq y} d(x,y) }[/math] in two different ways.

On the one hand, there are [math]\displaystyle{ M }[/math] choices for [math]\displaystyle{ x }[/math] and for each such choice, there are [math]\displaystyle{ M-1 }[/math] choices for [math]\displaystyle{ y }[/math]. Since by definition [math]\displaystyle{ d(x,y) \geq d }[/math] for all [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] ([math]\displaystyle{ x\neq y }[/math]), it follows that

[math]\displaystyle{ \sum_{(x,y) \in C^2, x\neq y} d(x,y) \geq M(M-1) d. }[/math]

On the other hand, let [math]\displaystyle{ A }[/math] be an [math]\displaystyle{ M \times n }[/math] matrix whose rows are the elements of [math]\displaystyle{ C }[/math]. Let [math]\displaystyle{ s_i }[/math] be the number of zeros contained in the [math]\displaystyle{ i }[/math]'th column of [math]\displaystyle{ A }[/math]. This means that the [math]\displaystyle{ i }[/math]'th column contains [math]\displaystyle{ M-s_i }[/math] ones. Each choice of a zero and a one in the same column contributes exactly [math]\displaystyle{ 2 }[/math] (because [math]\displaystyle{ d(x,y)=d(y,x) }[/math]) to the sum [math]\displaystyle{ \sum_{(x,y) \in C, x \neq y} d(x,y) }[/math] and therefore

[math]\displaystyle{ \sum_{(x,y) \in C, x \neq y} d(x,y) = \sum_{i=1}^n 2s_i (M-s_i). }[/math]

The quantity on the right is maximized if and only if [math]\displaystyle{ s_i = M/2 }[/math] holds for all [math]\displaystyle{ i }[/math] (at this point of the proof we ignore the fact, that the [math]\displaystyle{ s_i }[/math] are integers), then

[math]\displaystyle{ \sum_{(x,y) \in C, x \neq y} d(x,y) \leq \frac{1}{2} n M^2. }[/math]

Combining the upper and lower bounds for [math]\displaystyle{ \sum_{(x,y) \in C, x \neq y} d(x,y) }[/math] that we have just derived,

[math]\displaystyle{ M(M-1) d \leq \frac{1}{2} n M^2 }[/math]

which given that [math]\displaystyle{ 2d\gt n }[/math] is equivalent to

[math]\displaystyle{ M \leq \frac{2d}{2d-n}. }[/math]

Since [math]\displaystyle{ M }[/math] is even, it follows that

[math]\displaystyle{ M \leq 2 \left\lfloor \frac{d}{2d-n} \right\rfloor. }[/math]

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". IRE Transactions on Information Theory 6 (4): 445–450. 1960. doi:10.1109/TIT.1960.1057584.