Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

My question is about bounds and linear codes:

a) Use sphere packing bound (Hamming bound) to get an upper bound on $A_2(15,3)$. What linear code meets this bound? Is this code perfect?

b)can we do the same for $A_2(16,4)$?

share|improve this question
1  
If a code realizes the sphere-packing bound, it is perfect. –  Chris Godsil Apr 7 '13 at 19:05
1  
If a linear code is to meet an upper bound, it has to be pretty good. What good codes of length 15 and minimum distance 3 do you know? Does that code work? –  Jyrki Lahtonen Apr 7 '13 at 19:55

1 Answer 1

up vote 2 down vote accepted

The size of a Hamming ball in this case is $\binom{15}{0} + \binom{15}{1} = 1 + 15 = 16$. So for any code $C$ of length $15$ and distance $3$, the sphere packing yields $16\cdot \left| C\right| \leq 2^{15}$ and therefore $A_2(15,3) \leq 2^{11}$. A code meeting this bound has the parameters $(15,2^{11},3)$ and is perfect (by definition). Indeed, such a code exists, namely the binary Hamming code of length $15$.

For $A_2(16,4)$, you can't do the same thing, since perfect codes must have an odd minimum distance: Assume $C$ is perfect with minimum distance $d$. Since it is perfect, the $t = \lfloor (d-1)/2\rfloor$ balls centered at the codewords cover ${0,1}^n$. Since $d$ is even, $t = (d-2)/2$ or $d = 2t + 2$. Now consider a vector $v$ at distance $t$ from some codeword $c$ and another vector $v'$ at distance $1$ from $t$ and at distance $t+1$ from $c$ (they always exist). Then $v'$ is contained in a Hamming ball of radius $t$ centered at a codeword $c'$. Since the distance of $v'$ from $c$ is $t+1$, $c\neq c'$. Now $$d(c,c') \leq d(c,t) + d(t,t') + d(t',c') \leq t + 1 + t = 2t + 1 < 2t + 2 = d.$$ Contradiction.

share|improve this answer
    
thank you for your solution with detailed explanations azimut.but i could not find the answer that why must a perfect code has odd minimum distance? –  ötarcan Apr 12 '13 at 9:04
    
@ötarcan: I've added the details. –  azimut Apr 12 '13 at 11:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.