Misplaced Pages

Plotkin bound: Difference between revisions

Article snapshot taken from[REDACTED] with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Browse history interactively← Previous editNext edit →Content deleted Content addedVisualWikitext
Revision as of 06:38, 28 March 2022 edit31.154.130.146 (talk) "Proof of case i" - the "i" was a italic i, as if it is a mathematical variable, whereas it is actually just a roman numeral and therefor should not be italic; and removed a round bracket near the numeral.← Previous edit Revision as of 01:31, 5 December 2023 edit undoMe, Myself, and I are Here (talk | contribs)Extended confirmed users105,931 edits See also: alphaTags: Mobile edit Mobile web edit Advanced mobile editNext edit →
Line 59: Line 59:


==See also== ==See also==
* ]
* ]
* ]
* ] * ]
* ] * ]
* ]
* ] * ]
* ]
* ]
* ]
* ]


==References== ==References==

Revision as of 01:31, 5 December 2023

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 } {\displaystyle \{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 F 2 n {\displaystyle \mathbb {F} _{2}^{n}} over the finite field F 2 {\displaystyle \mathbb {F} _{2}} . Let d {\displaystyle d} be the minimum distance of C {\displaystyle C} , i.e.

d = min x , y C , x y d ( x , y ) {\displaystyle d=\min _{x,y\in C,x\neq y}d(x,y)}

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

Theorem (Plotkin bound):

i) If d {\displaystyle d} is even and 2 d > n {\displaystyle 2d>n} , then

A 2 ( n , d ) 2 d 2 d n . {\displaystyle A_{2}(n,d)\leq 2\left\lfloor {\frac {d}{2d-n}}\right\rfloor .}

ii) If d {\displaystyle d} is odd and 2 d + 1 > n {\displaystyle 2d+1>n} , then

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

iii) If d {\displaystyle d} is even, then

A 2 ( 2 d , d ) 4 d . {\displaystyle A_{2}(2d,d)\leq 4d.}

iv) If d {\displaystyle d} is odd, then

A 2 ( 2 d + 1 , d ) 4 d + 4 {\displaystyle A_{2}(2d+1,d)\leq 4d+4}

where   {\displaystyle \left\lfloor ~\right\rfloor } denotes the floor function.

Proof of case i

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

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

( x , y ) C 2 , x y d ( x , y ) M ( M 1 ) d . {\displaystyle \sum _{(x,y)\in C^{2},x\neq y}d(x,y)\geq M(M-1)d.}

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

( x , y ) C , x y d ( x , y ) = i = 1 n 2 s i ( M s i ) . {\displaystyle \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 {\displaystyle s_{i}=M/2} holds for all i {\displaystyle i} (at this point of the proof we ignore the fact, that the s i {\displaystyle s_{i}} are integers), then

( x , y ) C , x y d ( x , y ) 1 2 n M 2 . {\displaystyle \sum _{(x,y)\in C,x\neq y}d(x,y)\leq {\frac {1}{2}}nM^{2}.}

Combining the upper and lower bounds for ( x , y ) C , x y d ( x , y ) {\displaystyle \sum _{(x,y)\in C,x\neq y}d(x,y)} that we have just derived,

M ( M 1 ) d 1 2 n M 2 {\displaystyle M(M-1)d\leq {\frac {1}{2}}nM^{2}}

which given that 2 d > n {\displaystyle 2d>n} is equivalent to

M 2 d 2 d n . {\displaystyle M\leq {\frac {2d}{2d-n}}.}

Since M {\displaystyle M} is even, it follows that

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

This completes the proof of the bound.

See also

References

Category:
Plotkin bound: Difference between revisions Add topic