# q-ary code proof using spheres

• Oct 9th 2008, 06:56 AM
wik_chick88
q-ary code proof using spheres
Show that there is no q-ary code of length 5 and distance 3 with more than $\displaystyle \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 $\displaystyle \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 $\displaystyle \frac{q^5}{5q-4}$ codewords, there are $\displaystyle \frac{6q^5}{5q-4}$ distinct words in these spheres. However there are only $\displaystyle q^5$ distince q-ary words of length 5. therefore we have to show that
$\displaystyle \frac{6q^5}{5q-4}$ = $\displaystyle 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 $\displaystyle \frac{q^5}{5q-4}$ codewords exists. also, with q = 2 the no of codewords = $\displaystyle \frac{16}{3}$ can anyone tell me why this isnt a whole number?

• Oct 9th 2008, 10:11 AM
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
$\displaystyle (5q-4)N\leq q^5$. There fore $\displaystyle N\leq \frac{q^5}{5q-4}$ as desired.
• Oct 9th 2008, 04:05 PM
wik_chick88
Quote:

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
$\displaystyle (5q-4)N\leq q^5$. There fore $\displaystyle N\leq \frac{q^5}{5q-4}$ as desired.

thanks i sort of understand what ur saying, but how do i solve $\displaystyle N\leq \frac{q^5}{5q-4}$? or how do i prove that there is no such answer $\displaystyle N$ when i dont even know $\displaystyle q$?
• Oct 9th 2008, 04:37 PM
watchmath
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 $\displaystyle N(5q-4)\leq q^5$. From this we conclude that $\displaystyle N\leq \frac{q^5}{5q-4}$. Therefore N, the number of N words is not more than $\displaystyle \frac{q^5}{5q-4}$.
• Oct 9th 2008, 04:52 PM
wik_chick88
Thanks so much!! Proof by contradiction i love it (Clapping)