Counting the elements in a Hamming sphere using Combinatorics

Question

We have the following Hamming sphere

$$\mathcal B_3= ((0,0,0,0),(\mathbb F_7)^4)$$

with $\mathbb F_7=\{0,1,2,3,4,5,6\}$

So we want to know all possible elements with Hamming distance $\le3$ to $(0,0,0,0)$

$$\{u\in\mathbb F^4_7:dist((0,0,0,0),u)\le3\}$$

It is obvious that we have to use combinatorics to solve this problem.

First we notice that three elements in u have to be $\neq 0$

$$u=(v1,v2,v3,0) \ v_i \neq 0 $$

to get the Hamming distance of $3$.

The next step would be to count all the possible combinations to choose $3$ positions of a vector with length $4$.

$$ \frac {4!}{(4-1)!\cdot1!}=24$$

We know that $v_1,v_2,v_3\in\{1,2,3,4,5,6\}$

So for each $v_i$ we have $6$ possible combinations. How do I combine this with the $24$ from above?

Answer 1

If what you say is true about hamming distance, then it is $4*6^3$ It is not 24 but 4

Answer 2

A Hint: The question was about words at Hamming distance $\le 3$, but you seem to have concentrated on those at distance exactly $3$. But the maximum distance in this space is $4$. So you can simply

• Observe that there are $6^4=1296$ words at distance exactly four from $(0,0,0,0)$.
• Then observe that the total number of words in this space is $7^4=2401$.
• That leaves $2401-1296=1105$ vectors that are at distance $\le3$.