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.
Statement of the bound
edit edit sourceA 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 𝔽2n over the finite field 𝔽2. Let d be the minimum distance of C, i.e.
- d=minx,y∈C,x≠yd(x,y)
where d(x,y) is the Hamming distance between x and y. The expression A2(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
- A2(n,d)≤2⌊d2d−n⌋.
ii) If d is odd and 2d+1>n, then
- A2(n,d)≤2⌊d+12d+1−n⌋.
iii) If d is even, then
- A2(2d,d)≤4d.
iv) If d is odd, then
- A2(2d+1,d)≤4d+4
where ⌊ ⌋ denotes the floor function.
Proof of case i
edit edit sourceLet 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 A2(n,d)). The bound is proved by bounding the quantity ∑(x,y)∈C2,x≠yd(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)∈C2,x≠yd(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 si be the number of zeros contained in the i'th column of A. This means that the i'th column contains M−si 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,x≠yd(x,y) and therefore
- ∑(x,y)∈C,x≠yd(x,y)=∑i=1n2si(M−si).
The quantity on the right is maximized if and only if si=M/2 holds for all i (at this point of the proof we ignore the fact, that the si are integers), then
- ∑(x,y)∈C,x≠yd(x,y)≤12nM2.
Combining the upper and lower bounds for ∑(x,y)∈C,x≠yd(x,y) that we have just derived,
- M(M−1)d≤12nM2
which given that 2d>n is equivalent to
- M≤2d2d−n.
Since M is even, it follows that
- M≤2⌊d2d−n⌋.
This completes the proof of the bound.
See also
edit edit source- Diamond code
- Elias Bassalygo bound
- Gilbert–Varshamov bound
- Griesmer bound
- Hamming bound
- Johnson bound
- Singleton bound
References
edit edit source- Plotkin, Morris (1960). "Binary codes with specified minimum distance". IRE Transactions on Information Theory. 6 (4): 445–450. doi:10.1109/TIT.1960.1057584.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1249382245 under CC BY-SA 4.0; modifications have been made.