Hamming spheres

Question

I have the following task with hamming spheres. Need to get some feedback on my idea? Don't know if it is correct can't find much information on it.

Let $C$ be a code of length $n$ and distance at least $d$. For $w$ in $K^n$, let $B_w(r)=\{w' \in K^n \mid d(w,w`) \leq r \}$

1. For a codeword $v$ in $C$ show that $B_w(d-1) \cap C = \{v\}$

So $C \cap B_v(t) \neq \emptyset $ iff $t(C) \leq t $ so in this case $ t(C) = \frac{d-1}{2}$ and $ t=\frac{d-2}{2}$ so $t(C) \leq t $ is never possible, so the statement is false?

Don't know if this is 100% correct? - found that in this paper

1. Show that there exists a code $C$ of length $n$ and distance at least $d$ such that $ max_{length(C) = n, d(C) \geq d} \mid C\mid \leq \frac{2^n}{\binom{n}{0} + \binom{n}{1} + ...+\binom{n}{d-1} } $

any hints how to bite the second question?

Answer 1

My impression is that the statements of both questions are not stated entirely correct. I'm going to answer the following.

1)

For a codeword $v$ in $C$ show that $B_v(d-1)\cap C = \{v\}$.

Let $w\in B_v(d-1)\cap C$. Then $d(v,w) \leq d-1$. Since $v$ and $w$ are codewords of the code $C$, and $C$ has minimum distance at most $d$, it follows that $v = w$.

2) I guess you want to show the sphere packing bound (aka Hamming bound):

For any binary code $C$ of length $n$ and minimum distance $d$,$$\lvert C\rvert \leq \frac{2^n}{\binom{n}{0} + \binom{n}{1} + \ldots + \binom{n}{t}}$$ where $t = \lfloor (d-1)/2\rfloor$ is the number of errors the code $C$ can correct.

Let $K = \{0,1\}$ and $w\in K^n$. The number of words in distance $d'$ to $w$ is $\binom{n}{d'}$, since this is the number of choices for the differing positions (the entries are fixed then). This shows $\lvert B_w(d')\rvert = \binom{n}{1} + \binom{n}{2} + \ldots + \binom{n}{d'}$.

Since $C$ has minimum distance $d$, the Hamming balls $B_v(t)$ about the codewords $v$ are disjoint. So in the ambient Hamming space $K^n$, there may not exist more that $$\frac{\lvert K^n\rvert}{\lvert B_v(t)\rvert} = \frac{2^n}{\binom{n}{0} + \binom{n}{1} + \ldots + \binom{n}{t}}$$ such Hamming balls.