Results 1 to 4 of 4

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

    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
    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 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.
    Last edited by Nyrox; February 11th 2010 at 05: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 \{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?
    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 [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
    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: July 25th 2010, 09:03 AM
  2. error correcting code
    Posted in the Advanced Math Topics Forum
    Replies: 5
    Last Post: February 19th 2010, 03:37 AM
  3. Error Correcting Codes - Plotkin Bound
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: February 11th 2010, 10:47 AM
  4. Error Correcting Code
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: January 25th 2010, 08:44 PM
  5. Error-correcting code proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 18th 2008, 11:21 PM

Search Tags


/mathhelpforum @mathhelpforum