Investigating the generalised Hamming distance of some code and information transmission of a binary code.

Question

Letting $A$ be an alphabet of size $a$ and $S = A^{n}$. Meaning the set of all worlds of length $n$ with bits chosen from the alphabet $A$. We now take $w ∈ S$.

Assume $n = 14$. How many words in $S$ are of Hamming distance less than or equal to $4$ from $w?$

Secondly, assume $n = 14$ and $a = 2$ and that $w ∈ S$ is transmitted through a Binary Symmetric Channel with probability $p$ of correct transmission for each individual bit. How would you generalise a formula for the probability that $5$ or fewer errors will occur during transmission of $w?$

The idea I've had so far is generalising some form of binomial probability from zero errors up to 5. Something like:

$p^{14} + 14p^{13}(1-p)^{1}+...$

Appreciate any of your time/thoughts in advance.

Answer 1

• To have Hamming distance $\le4$, we pick those positions that are intended to be different from $w$ and purposely choose them to be different from $w$ at that position, of which we have $a-1$ choices, hence the desired answer is

$$\sum_{i=0}^4 \binom{14}{i}(a-1)^i.$$

• Similarly, for the case where $n=14$, $a=2$, and $p$ being the probability of success, we choose the position of mistakes. At those positions, we multiply by probability $1-p$ and at the correct positions, we multiply by $p$. Hence the expression:

$$\sum_{i=0}^5 \binom{14}{i}p^{14-i}(1-p)^i.$$

That is your idea was right, just write down $6$ terms.