(7,4) Hamming Code with 2 bit errors

Question

I need help proving that a HammingCode with 2 bits flipped can create a new codeword by flipping just one more bit.

I worked through the problem and created an example of my own but am having trouble generalizing it.

My example: The original codeword: (1101000) 2 bits flipped: (0111000) new codeword: (0111010)

Answer 1

The $(7,4)$ Hamming code has minimum distance $3$. Therefore, if you flip $2$ bit in a codeword you can not obtain a codeword.

Now use the fact that the $(7,4)$ Hamming code is a perfect code. It means, in this case, that the Hamming balls of radius $1$ surrounding the codewords fill the Hamming space without overlap. Hence, if $r$ is not a codeword, there exists a codeword $c$ with distance exactly $1$ from $r$.

Answer 2

The (7,4) Hamming code is (as Sfarla notes) perfect, which in this case means: each one of the 16 codewords can be associated with a cluster (or ball) of 8 messages: the one corresponding to zero errors , plus the 7 messages corresponding to one error (one bit flipped). Because the code has distance 3, these cluster don't overlap. Furthermore, the total number of messages is $2^7=128$ which equals $16 \times (1+7)$, so all the possible messages belong to one of the 16 clusters (they "fill" the space).

Hence, when you flip two bits, you are not in the cluster of the original codeword, but you must be in some other cluster - which means that you are at distance 1 from another codeword. Hence, you can reach that other codeword by just flipping one bit.