Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
Have you seen proven the fact that any sequence of 7 bits is at a Hamming distance at most one from some codeword? In other words that the covering radius of the Hamming code is 1? Can you use that? –  Jyrki Lahtonen Aug 17 '13 at 10:11
    
Damn it, why did you delete your other coding theory question? I was just typing an answer explaining how to extend the $(8,4,4)$ code to a $(11,4,5)$ code. Also proving that tagging three extra redundant bits is the best we can do. :-) –  Jyrki Lahtonen Oct 29 '13 at 7:40
1  
I am sorry! Can you post your suggestion in link or link instead? @JyrkiLahtonen –  freak_warrior Oct 29 '13 at 8:19
2  
No worries! It is your call, whether you want to keep it. I was just mildly miffed by the accidental timing that I happened to be typing an answer exactly when you deleted. My answer was still in the buffer, so I only had to add a couple of sentences. It's posted in the first link now. –  Jyrki Lahtonen Oct 29 '13 at 8:25
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.