Understanding the hamming bound

Question

I have a theorem for the hamming bound or the sphere packing bound.

A q-ary $(n, m, 2e+1)$ code satisfies $$M \bigg\{ \binom {n}{0} + \binom{n}{1} (q-1)+...+\binom{n}{e}(q-1)^e\bigg\} \leq q^n $$

What is $q^n$?

What is this theorem trying to say?

Answer 1

Here $q$ stands for the number of symbols in the alphabet and $q^n$ is the number of $n$-letter words that can be constructed from those symbols. The sum $$ \binom {n}{0} + \binom{n}{1} (q-1)+...+\binom{n}{e}(q-1)^e $$ is the volume of a "Hamming ball", that is, it's the number of $n$-letter words that differ in no more than $e$ positions from a specified word, $w$. The first term in the sum is the number of words that differ from $w$ in no positions, that is, the number of words that equal $w$. So this term is $1$. The second term is the number of words that differ from $w$ in one position. There are $\binom{n}{1}=n$ positions in which a word might differ from $w$, and, in a $q$-letter alphabet, $q-1$ letters that the actual letter of $w$ occurring at the position might be replaced with. The other terms are similar, but more letters of $w$ are altered in each successive term.

In a code with minimum distance $2e+1$, any word that differs from a codeword $w$ in $e$ or fewer positions will decode to $w$. Notice that the volume of the Hamming ball, given by your sum, is the number of words that differ from $w$ in at most $e$ positions, that is, the number of words that will decode to $w$. Minimum distance $2e+1$ implies that the Hamming balls of all the codewords are pairwise nonoverlapping. So if you add up the sizes of all the Hamming balls, you should not get more than $q^n$, the number of possible words in a $q$-letter alphabet. If there are $m$ codewords, then $$ m\left\{ \binom {n}{0} + \binom{n}{1} (q-1)+...+\binom{n}{e}(q-1)^e\right\} $$ cannot not exceed $q^n$.

Answer 2

You have a $q$-ary $(n,m,2e+1)$ code, so you should know what $q$ and $n$ represent ($q$ is the size of the alphabet, $n$ is the length of the codewords, $m$ is the number of codewords, and $2e+1$ is the minimum distance between codewords). So $q^n$ is just this value, $q$ to the $n$th power.

You are using both $m$ and $M$ in your question, you should decide on one or the other, because you are using them both to represent the number of words in your code. Also your use of braces ($\{ \}$) in the equation is odd, because this should be a multiplication. It is saying the number of codewords $m$ satisfies the equation $$m \left( \sum_{i=0}^{e} {n \choose i}(q-1)^{i}\right) \leq q^{n},$$ or better yet $$m \leq \frac{q^{n}}{\sum_{i=1}^{e} {n \choose i}(q-1)^{i}}.$$

Will's answer gives a good description of the Hamming Balls, which shows where this equation comes from and why it is often called the "sphere-packing bound."