Results 1 to 4 of 4

Thread: Error Correcting Codes - Plotkin Bound

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    6

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Feb 2010
    From
    Lisbon
    Posts
    51
    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.
    Last edited by Nyrox; Feb 11th 2010 at 04:04 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2010
    Posts
    6
    Quote Originally Posted by Nyrox View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Feb 2010
    From
    Lisbon
    Posts
    51
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. The [5,2] error correcting code
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Jul 25th 2010, 08:03 AM
  2. error correcting code
    Posted in the Advanced Math Topics Forum
    Replies: 5
    Last Post: Feb 19th 2010, 02:37 AM
  3. Error Correcting Codes - Plotkin Bound
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: Feb 11th 2010, 09:47 AM
  4. Error Correcting Code
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: Jan 25th 2010, 07:44 PM
  5. Error-correcting code proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Sep 18th 2008, 10:21 PM

Search Tags


/mathhelpforum @mathhelpforum