Hamming code detecting multiple errors

Question

Say I have the matrix

$M= \left[ {\begin{array}{cc} 0 & 0&0&1&1&1&1 \\ 0&1&1&0&0&1&1 \\ 1&0&1&0&1&0&1\\ \end{array} } \right]$

Now I know that this string $0101011$ has one wrong bit. So I do the matrix multiplication and calculate the syndrome to get $1 1 1$ which corresponds to the 7th bit.

NOW what if I change the first bit of B=$0101011$ so it becomes A=$1101011$ so now I have two error bits doing the matrix multiplication of $M*A$

I get a different syndrome that corresponds to a different bit, I thought hamming codes could detect two errors, could someone please explain?

Answer 1

The Hamming code can detect the two errors; the syndrome is non-zero, whence the conclusion it is not correct, there were error(s).

However, the Hamming code cannot correct two errors (only one). Thus, if there are two errors and one tries to recover the original codeword this can fail. Yet, again one can reliably detect that there were error(s).

Answer 2

The Hamming code is a collection of code words such that every two of them is at least 3 apart in Hamming weight, and every word that is not a codeword is one bitflip away from a valid one. So if you flip one bit of a valid code word, you're still one away from the codeword you modified but still at least 2 away from another codeword. The principle of least distance decoding (most probable original codeword) tells us to correct the received word back to the original code word. But if we flip $2$ bits of a valid codeword $w_1$ we have distance $1$ to another valid codeword $w_2$ and of course $2$ to $w_1$. The decoding algorithm decodes to the wrong word $w_2$ (which is closer) but we did detect that we had to correct an error and we assumed we only had one (as this is more probable than $2$). So the Hamming code still detects a non-zero syndrome (hence an error).

In your example, the syndrome of the second vector is $110$ so we decode to $1101001$ (flip 6 as the syndrome is the 6th column) instead of the correct $0101010$ (which is a code word as the sum of row 2 and 3). The two codewords are indeed $3$ apart.

The syndrome can only be one of the 7 columns (all possible 7 values). two errors just looks like 1 error, and this canot be helped. We do detect an error.