Let . One of the Plotkin bounds states that a code with minimum distance has at most codewords. One nice proof (that actually gives a stronger result) uses some elementary geometry; the inequality in the following result is Exercise 2 in the linked notes.

Lemma. Suppose that are vectors in
such that for all . Then with equality if and only if where the are orthogonal vectors.

Proof. We may assume that and that . Let be a minimal subset of linearly dependent vectors chosen from the and let

Choose such that . By the first part of the lemma in the previous post, we may assume that for all . For each we have

Since and , we must have for all . Hence the spaces spanned by the and are orthogonal. The space spanned by the has dimension , so the lie in a subspace of dimension . By induction on the dimension we have

.

Moreover, if equality holds then so and continuing inductively with the , we see that the are as claimed.

Proof of the Plotkin bound. Let be a code with minimum distance . We can map each codeword to a vector in by sending to and to . Since each pair of vectors differs in at least places, this gives us vectors in , such that if are different vectors then . By the previous lemma, , with equality if and only if

where any two differ in exactly positions, and denotes the vector obtained from the codeword by interchanging with .

Advertisements

Like this:

LikeLoading...

Related

This entry was posted on Sunday, January 16th, 2011 at 7:02 pm and is filed under Coding theory. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.