Plotkin bound
≈ 3 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 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
Text derived from https://en.wikipedia.org/w/index.php?oldid=1249382245 under CC BY-SA 4.0; modifications have been made.