[Math] Binary Hamming code – number of words weight $i$

coding-theorymatrices

Define $A_i$ as the number of words in binary Hamming code of weight $i$. Prove:
$$A_1=0, A_0=1$$
$$(i+1)A_{i+1}+A_i+(n-i+1)A_{i-1}= {n \choose i}$$

I am a tad clueless as to how to proceed. I can show that for a given weight $i$, the number of columns of such weight of the parity-check matrix $H$ are precisely $n\choose i$. Every codeword $c$ of Ham must hold $c*H^t$. Furthermore, I can describe the generating matrix $G$ as being a matrix of the form [$A|I_{n-r}$], where there are $n\choose i$ rows in $A$ of weight $i$, for $2\le i \le n$.

I am certain the proof has to do with these two properties, yet I am unable to connect the points. Perhaps a proof with induction could be of use?

Any hints/direction towards the right way and what I should be looking at or focusing on will be extremely appreciated!

Best Answer

Hint: Hamming code is a perfect single error correcting code. This means that any vector of weight $i$ is either

  • a codeword, or
  • at a Hamming distance 1 from a uniquely determined codeword of weight $i-1$, or
  • at a Hamming distance 1 from a uniquely determined codeword of weight $i+1$.

Also the three options are mutually exclusive because the minimum Hamming distance between two codewords is three.

Related Question