---
title: Plotkin bound
slug: plotkin-bound
qid: 
snapshot: enwiki-001249382245
content_hash: 
license: CC BY-SA 4.0
source: https://en.wikipedia.org/w/index.php?oldid=1249382245
tags: [20476821, 22899737, 23400961, 24043274, 24261919, 61225801]
---

# Plotkin bound

> [!note] Provenance
> Snapshot `enwiki-001249382245` · content root `…`
> Derived from <https://en.wikipedia.org/w/index.php?oldid=1249382245> · Licensed CC BY-SA 4.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.

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. 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&nbsp; 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 2d>n 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. ==See also== Diamond code Elias Bassalygo bound Gilbert–Varshamov bound Griesmer bound Hamming bound Johnson bound Singleton bound ==References==
