2
$\begingroup$

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!

$\endgroup$

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

Hint:

$$ \begin{align} \binom{n}{i} &= \text{# of weight $i$ words} \\ (i+1) A_{i+1} &= \text{# of weight $i$ non-codewords distance $1$ from a weight $i+1$ codeword} \\ A_i &= \text{# of weight $i$ codewords} \\ (n-(i-1)) A_{i-1} &= \text{# of weight $i$ non-codewords distance $1$ from a weight $i-1$ codeword} \end{align} $$

As the Hamming code is a perfect $1$-error-correcting code, any non-codeword is distance $1$ from a unique codeword.

$\endgroup$
1
  • $\begingroup$ Although I chose Jyrki's answer, this answer has been of great help to me too! Thanks! $\endgroup$ Commented Aug 25, 2014 at 17:43

You must log in to answer this question.

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