Results 1 to 5 of 5

Math Help - q-ary code proof using spheres

  1. #1
    Member
    Joined
    Apr 2008
    Posts
    204

    q-ary code proof using spheres

    Show that there is no q-ary code of length 5 and distance 3 with more than \frac{q^5}{5q-4} codewords. You should prove this from first principles using spheres and without using known bounds on the number of codewords.

    This is my working so far:
    First prove that there is a q-ary code of length 5 and distance 3 with exactly \frac{q^5}{5q-4} codewords. consider the spheres of radius 1 centred on codewords. Each such sphere contains 1 + 5 = 6 words. Since the code has distance 3, no two such spheres intersect. Otehrwise we would have a pair of codewords at distance 2 or less. Since there are \frac{q^5}{5q-4} codewords, there are \frac{6q^5}{5q-4} distinct words in these spheres. However there are only q^5 distince q-ary words of length 5. therefore we have to show that
    \frac{6q^5}{5q-4} = q^5 for some q that is a natural non-zero number.

    i worked out q = 2 therefore such a code exists. but now im having problems proving that no q-ary code with MORE THAN \frac{q^5}{5q-4} codewords exists. also, with q = 2 the no of codewords = \frac{16}{3} can anyone tell me why this isnt a whole number?

    PLEASE HELP!!! any help or advice would be GREATLY appreciated!!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Oct 2008
    Posts
    64
    There is some mistake in your argument.
    If you look at a sphere with radius one, then in order a word has distance 1 to the center if they differ in one place. Since it is of length 5 then we can choose one of this place. BUT for each place we have a (q-1) way to change it . So the number of codes in this sphere is 1+5(q-1)=5q-4.
    As you said all of this sphere are disjoint. If there are N codes then we need the total word to be less or equal to q^5. Then we need
    (5q-4)N\leq q^5. There fore N\leq \frac{q^5}{5q-4} as desired.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Apr 2008
    Posts
    204
    Quote Originally Posted by watchmath View Post
    There is some mistake in your argument.
    If you look at a sphere with radius one, then in order a word has distance 1 to the center if they differ in one place. Since it is of length 5 then we can choose one of this place. BUT for each place we have a (q-1) way to change it . So the number of codes in this sphere is 1+5(q-1)=5q-4.
    As you said all of this sphere are disjoint. If there are N codes then we need the total word to be less or equal to q^5. Then we need
    (5q-4)N\leq q^5. There fore N\leq \frac{q^5}{5q-4} as desired.
    thanks i sort of understand what ur saying, but how do i solve N\leq \frac{q^5}{5q-4}? or how do i prove that there is no such answer N when i dont even know q?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Oct 2008
    Posts
    64
    Maybe my wording is not quite nice.

    Another attempt.
    Let N be the number of codewords. As I proved earlier in each ball there are 1+5(q-1)=5q-4 q-ary words. Since we have N balls (because the center is the codewords) and the union of all of these balls is a subset of the set of all q-ary (some q-ary words can be outside the balls) then N(5q-4) (the number of all q-ary words in the balls) can not be bigger than the number of all q-ary, that is N(5q-4)\leq q^5. From this we conclude that N\leq \frac{q^5}{5q-4}. Therefore N, the number of N words is not more than \frac{q^5}{5q-4}.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Apr 2008
    Posts
    204
    Thanks so much!! Proof by contradiction i love it
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. spheres
    Posted in the Geometry Forum
    Replies: 7
    Last Post: June 13th 2011, 05:08 PM
  2. Spheres
    Posted in the Trigonometry Forum
    Replies: 5
    Last Post: April 4th 2010, 01:03 AM
  3. Coding theory - proof from spheres
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 13th 2009, 04:02 AM
  4. Help with spheres - calc 3
    Posted in the Calculus Forum
    Replies: 1
    Last Post: September 12th 2009, 09:27 PM
  5. Error-correcting code proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 18th 2008, 10:21 PM

Search Tags


/mathhelpforum @mathhelpforum