Thread: q-ary code proof using spheres

Show that there is no q-ary code of length 5 and distance 3 with more than 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 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 codewords, there are distinct words in these spheres. However there are only distince q-ary words of length 5. therefore we have to show that
= 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 codewords exists. also, with q = 2 the no of codewords = can anyone tell me why this isnt a whole number?

PLEASE HELP!!! any help or advice would be GREATLY appreciated!!!

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
. There fore as desired.

Originally Posted by watchmath

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
. There fore as desired.

thanks i sort of understand what ur saying, but how do i solve ? or how do i prove that there is no such answer when i dont even know ?

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 . From this we conclude that . Therefore N, the number of N words is not more than .

Thanks so much!! Proof by contradiction i love it