# Thread: Error Correcting Codes - Plotkin Bound

1. ## Error Correcting Codes - Plotkin Bound

Hi

I would really appreciate some help in proving the so called plotkin bound

$\displaystyle d\leq \frac{2^{k-1}\cdot n}{2^{k}-1}$

holds for C where C is a binary (n,k,d)-code.

I have been asked to show this by arguing as follows:

For a given position j, show that the number of codewords that have 0 at position j is either $\displaystyle 2^{k}$ or $\displaystyle 2^{k-1}$

I have done this by induction but its a realllyyy long proof so I am looking for a better one if it exists!

Thanks

2. o_O I thought the Plotkin bound was a bound for $\displaystyle A_2 (n,d)$. Are you sure you have this right? Here you're bounding (above) the minimum distance between codewords... what's the point? xD

Edit: ok, I guess I can see some interest in doing it However, the bound you present here appears to be wrong: take the code $\displaystyle \{00,11\}$, which is a binary $\displaystyle (2,2,2)$ code. Your bound states that

$\displaystyle d=2\leq \frac{2^1\cdot 2}{2^2-1}=\frac{4}{3}$

which is false.

3. Originally Posted by Nyrox
the bound you present here appears to be wrong: take the code $\displaystyle \{00,11\}$, which is a binary $\displaystyle (2,2,2)$ code. Your bound states that

$\displaystyle d=2\leq \frac{2^1\cdot 2}{2^2-1}=\frac{4}{3}$

which is false.
Is $\displaystyle C=\{00,11\}$ not a $\displaystyle (2,1,2)$ code (since $\displaystyle C=Span\{11\}$ and hence the dimension is 1?

4. Ah, so you mean a binary linear $\displaystyle [n,k,d]$-code, which is a binary $\displaystyle (n,2^k,d)$-code. Sorry for the confusion then.

Well, as far as I see it, you don't need induction. Try it as follows: call $\displaystyle C$ the code, pick a position $\displaystyle j$ and consider the set

$\displaystyle \Gamma \equiv \{w\in C:w_j=0\}$

If $\displaystyle \Gamma =C$, we have $\displaystyle 2^k$ codewords with $\displaystyle 0$ at position $\displaystyle j$. Otherwise, there exists a codeword $\displaystyle x\in C$ such that $\displaystyle x_j=1$. Consider the set

$\displaystyle \Delta \equiv \Gamma +x\subseteq C$ (since $\displaystyle C$ is linear)

and observe that $\displaystyle |\Delta|=|\Gamma|$. Since $\displaystyle \Gamma \cup \Delta =C$, we must have

$\displaystyle |\Delta |=|\Gamma |=\frac{1}{2}|C|$

Let me know if you are stuck on the conclusion