# Math Help - 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

$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 $2^{k}$ or $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 $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 $\{00,11\}$, which is a binary $(2,2,2)$ code. Your bound states that

$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 $\{00,11\}$, which is a binary $(2,2,2)$ code. Your bound states that

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

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

4. Ah, so you mean a binary linear $[n,k,d]$-code, which is a binary $(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 $C$ the code, pick a position $j$ and consider the set

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

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

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

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

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

Let me know if you are stuck on the conclusion