1
$\begingroup$

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?

$\endgroup$

2 Answers 2

4
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ If it is a q letter alphabet, should q not be decreasing? So for example first it is (q-1) then (q-2) etc... $\endgroup$
    – Al jabra
    Commented Feb 5, 2016 at 11:00
  • $\begingroup$ No, $(q-1)^k$ is correct for the number of words that differ from $w$ in exactly $k$ letter positions. Suppose the alphabet is $\{0,1,2,3\}$. Then there are $3^2=9$ words that differ from the word $000000$ in the first two positions, not $3\cdot2$ such words. These nine words are $110000$, $120000$, $130000$, $210000$, $220000$, $230000$, $310000$, $320000$, $330000$. And for any of the $\binom{6}{2}$ choices of two letter positions, you will have nine words that differ from $000000$ in those positions. $\endgroup$ Commented Feb 5, 2016 at 12:16
0
$\begingroup$

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."

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .