Sphere packing bound for binary linear codes of length 15 and minimum distance 3

Question

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)$?

Answer 1

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.