User:ECCclass/Plotkin

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In the mathematics of coding theory, the Plotkin bound, named after Morris Plotkin, is a 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]

We say a code is binary, if the codewords use symbols from the binary alphabet . In particular, if all codewords have a fixed length n, we speak of a binary code of length n. Equivalently, we may consider in this case the codewords as elements of vector space over the finite field . Let be the minimum distance of , i.e.

where is the Hamming distance between and . The expression represents the maximum number of possible codewords in a binary code of length and minimum distance . The Plotkin bound places a limit on this expression.

Theorem (Plotkin bound):

i) If is even and , then

ii) If is odd and , then

iii) If is even, then

iv) If is odd, then

where denotes the floor function.

Proof of case i[edit]

Let be the Hamming distance of and , and be the number of elements in (thus, is equal to ). The bound is proved by bounding the quantity in two different ways.

On the one hand, there are choices for and for each such choice, there are choices for . Since by definition for all and , it follows that

On the other hand, let be an matrix whose rows are the elements of . Let be the number of zeros contained in the 'th column of . This means that the 'th column contains ones. Each choice of a zero and a one in the same column contributes exactly (because ) to the sum and therefore

If is even, then the quantity on the right is maximized if and only if holds for all , then

Combining the upper and lower bounds for that we have just derived,

which given that is equivalent to

Since is even, it follows that

On the other hand, if is odd, then is maximized when which implies that

Combining the upper and lower bounds for , this means that

or, using that ,

Since is an integer,

This completes the proof of the bound.

See also[edit]

References[edit]

  • Binary codes with specified minimum distance, M. Plotkin, IRE Transactions on Information Theory, 6:445-450, 1960. doi:10.1109/TIT.1960.1057584

Category:Articles containing proofs