Error-correcting capability of (7,4) Hamming code

Question

I know that that a (7,4) binary Hamming code can definitely correct a single error. However, how do I prove that it definitely cannot correct 2 or more errors? Thanks in advance!

Answer 1

There are $2^4 = 16$ codewords, and $7$ vectors that are at distance $1$ from each codeword. The set of $8$ vectors consisting of a codeword $\mathbf c$ plus the $7$ vectors at distance $1$ from it is called the Hamming sphere of radius $1$ centered at $\mathbf c$. If the received vector $\mathbf r$ lies in $S(\mathbf c)$, the decoder output is $\mathbf c$, and if $\mathbf c$ is indeed the transmitted codeword, then the decoder output is correct, that is, $0$ or $1$ errors can be corrected by this code.

Denote this sphere by $S(\mathbf c)$ and note that since the code can correct single errors, $S(\mathbf c)$ and $S(\mathbf c^\prime)$ must be disjoint if $\mathbf c \neq \mathbf c^\prime$. Thus, we have accounted for $8\times 16 = 128 = 2^7$ binary vectors, that is, these $16$ (disjoint) Hamming spheres of radius $1$ collectively constitute the entire set of binary vectors of length $7$. Now, any received vector $\mathbf r$ must lie in one of these spheres, and if it is at distance $2$ or more from the transmitted codeword $\mathbf c$, it is necessarily in some $S(\mathbf c^\prime)$ for $\mathbf c^\prime \neq \mathbf c$ and thus will be decoded into $\mathbf c^\prime$, that is, the decoding will be in error. In other words, two or more errors cannot be corrected by the $(7,4)$ Hamming code.

More generally, the $(2^n-1, 2^n-1-n)$ Hamming code has $1 + 2^n-1 = 2^n$ vectors in each of the $2^{2^n-1-n}$ disjoint Hamming spheres of radius $1$ centered at the codewords, and these spheres collectively constitute the entire set of $2^{2^n-1}$ binary vectors of length $2^n-1$, and the above argument applies to the general case as well.

Answer 2

There are 4 significant bits in a message so are 16 signals without errors

In a signal there are 7 bits so there are 7 errors per signal possible so if one error there are 7 x 16 = 104 signals with one error

There are 6x7/2 (21) ways having 2 errors in a 7 bit signal so that is 336 possible signals.

But there are only 128 different posible signals, so at least some some signals of the group with 2 errors have to be the same signal and cannot be distinghuised or decided what the message was.

simple example

1100000 is a signal with two errors

what was the message?
if error free signal was -> message was
0000000 -> 0000
1110000 -> 1000 (ok there is only one error in this one)
1100110 -> 0110
or
1101001 -> 0001