Facebook
Google
GitHub
Linkedin
Hamming Distance
- Thread starter zulfi100
- Start date
Come on, Zulfi, you know how this works by now. Take your best shot at it by describing what you know so far and what you think the issues are. We will then help guide you along a path that will help you discover the answer.
First consider what the Hamming distance would have to be to correct any single bit error.
First consider what the Hamming distance would have to be to correct any single bit error.
If you can't understand the question and you don't know what is meant by a block code, how are you coming up with the assertion that the Hamming distance should be 1 in order to correct any single bit error?
Can you explain what is meant by the "Hamming distance"?
Hi,
I saw it on wiki
http://en.wikipedia.org/wiki/Hamming_distance
It has got an example cube.
Your question was simple. If we have 1 bit, and in case of error, we have to correct only this one bit.
This i got after thinking on your question.
Plz guide me.
Zulfi.
I saw it on wiki
http://en.wikipedia.org/wiki/Hamming_distance
It has got an example cube.
Your question was simple. If we have 1 bit, and in case of error, we have to correct only this one bit.
This i got after thinking on your question.
Plz guide me.
Zulfi.
First we need to get some terminology established. The type of codes you are talking about are "block codes", meaning that they work on "blocks" of bits. So, for instance, we have a block size of eight. That means that we work in chucks of eight bits. Each possible collection of eight bits (there are 256 of them) is a "vector". The "Hamming distance" between two vectors is simply the number of positions in which the two vectors differ. So the Hamming distance between the vectors
V1 = 00101101
V2 = 01101001
is 2 because they differ in two places.
Now, if all eight bits represent valid data, then any vector is a valid pattern that has meaning. But this also means that if I change a single bit in one vector that I transform that vector into another valid pattern and I can't tell that an error actually occurred.
So, instead, what we do is we choose a subset of the vectors as out set of valid patterns. This set is referred to as our "code book". Let's take the extreme case and choose just two patterns from out eight-bit block to be in our codebook. We'll choose all zeros and all ones. Hence our codebook is
00000000
11111111
Any other pattern that we receive means that errors have occurred. So now let's say that we receive the pattern
11101101
What was the pattern that was most probably transmitted? Pretty obviously, it was probably the 11111111 pattern since it only requires two bits to be received erroneously compared to the six bits that would have to be received incorrectly had it been the 00000000 pattern. So if we detect 11101101 we choose to correct it to 11111111.
But now what if we receive the pattern
10011010
Would could have gotten this pattern starting with the all zeros pattern and receiving four of the bits incorrectly as ones, or we could have gotten this pattern starting with the all ones pattern and receiving four bits incorrectly as zeros. If we assume that a zero->one error is as likely as a one->zero error, the both of these possibilities are equally likely and we can't make a reasonable correct. Thus, receiving a pattern that has 4 bit errors is beyond our ability to correct. But any pattern that has at most 3 bit errors we can correct.
Our ability to correct a given received pattern to one of the valid patterns in our codebook relies on a very simply requirement. Their must be a single pattern in the codebook that is closer, in terms of Hamming distance, to the received pattern than any other pattern in the codebook. Thus, if the nearest pattern in the codebook would require that I flip 3 bits in the received pattern, then all other patterns must require that I flip at least 4. If I am going to be able to correct ANY three errors in the received pattern, then this requires that ALL patterns in the codebook be at least 7 bit flips away from each other. Hence, the minimum Hamming distance between ANY pair of codewords has to be 7 if I am going to correct any 3 errors.
V1 = 00101101
V2 = 01101001
is 2 because they differ in two places.
Now, if all eight bits represent valid data, then any vector is a valid pattern that has meaning. But this also means that if I change a single bit in one vector that I transform that vector into another valid pattern and I can't tell that an error actually occurred.
So, instead, what we do is we choose a subset of the vectors as out set of valid patterns. This set is referred to as our "code book". Let's take the extreme case and choose just two patterns from out eight-bit block to be in our codebook. We'll choose all zeros and all ones. Hence our codebook is
00000000
11111111
Any other pattern that we receive means that errors have occurred. So now let's say that we receive the pattern
11101101
What was the pattern that was most probably transmitted? Pretty obviously, it was probably the 11111111 pattern since it only requires two bits to be received erroneously compared to the six bits that would have to be received incorrectly had it been the 00000000 pattern. So if we detect 11101101 we choose to correct it to 11111111.
But now what if we receive the pattern
10011010
Would could have gotten this pattern starting with the all zeros pattern and receiving four of the bits incorrectly as ones, or we could have gotten this pattern starting with the all ones pattern and receiving four bits incorrectly as zeros. If we assume that a zero->one error is as likely as a one->zero error, the both of these possibilities are equally likely and we can't make a reasonable correct. Thus, receiving a pattern that has 4 bit errors is beyond our ability to correct. But any pattern that has at most 3 bit errors we can correct.
Our ability to correct a given received pattern to one of the valid patterns in our codebook relies on a very simply requirement. Their must be a single pattern in the codebook that is closer, in terms of Hamming distance, to the received pattern than any other pattern in the codebook. Thus, if the nearest pattern in the codebook would require that I flip 3 bits in the received pattern, then all other patterns must require that I flip at least 4. If I am going to be able to correct ANY three errors in the received pattern, then this requires that ALL patterns in the codebook be at least 7 bit flips away from each other. Hence, the minimum Hamming distance between ANY pair of codewords has to be 7 if I am going to correct any 3 errors.
Hi,
Thanks for your work. It helped me to understand what is codeword, codebook and the concept of hamming distance. But sorry, i am not able to understand:
Kindly guide me. Sorry for taking your time.
Zulfi.
Thanks for your work. It helped me to understand what is codeword, codebook and the concept of hamming distance. But sorry, i am not able to understand:
In your example pattern size is 8. If 3 bits are in error and i correct this then how come its possible to have this pattern differ by 7 bits from other patterns in the code book because 7 +3 =10.
Kindly guide me. Sorry for taking your time.
Zulfi.
Why are you adding the 3 to the 7. The 7 is the minimum distance between any two codewords if I am going to be able to correct any 3 bit errors. The error pattern (the received vector) can be up to a Hamming distance of 3 from the correct codeword but must be at least a Hamming distance of 4 from any other codeword, hence 7.
Consider a 7-bit pattern in which the only two codewords are, again, all zeros and all ones.
The minimum distance between any two codewords is seven (because the distance between the only two codewords is seven).
Say I transmit 000000 and three bit errors occur. Pick any three. Say
0101100
Which valid codeword is that closest to? It's closer to 0000000 than 1111111 so I correct it and call it 0000000. That will happen for any 1, 2, or 3 bit error. The same is true for up to a three bit error had I sent 1111111 instead.
But what happens if I send 0000000 and four bits get flipped? Say
0110110
Now it is closer to 1111111 than 0000000 and so I would correct it to 1111111, which is the wrong pattern. I can't correct a 4 bit error. Worse, if there are four or more errors I will think I corrected it but I will correct it to the wrong pattern. I have no way of knowing that it was actually a 4-bit error and not a 3-bit error from the other pattern.
Consider a 7-bit pattern in which the only two codewords are, again, all zeros and all ones.
The minimum distance between any two codewords is seven (because the distance between the only two codewords is seven).
Say I transmit 000000 and three bit errors occur. Pick any three. Say
0101100
Which valid codeword is that closest to? It's closer to 0000000 than 1111111 so I correct it and call it 0000000. That will happen for any 1, 2, or 3 bit error. The same is true for up to a three bit error had I sent 1111111 instead.
But what happens if I send 0000000 and four bits get flipped? Say
0110110
Now it is closer to 1111111 than 0000000 and so I would correct it to 1111111, which is the wrong pattern. I can't correct a 4 bit error. Worse, if there are four or more errors I will think I corrected it but I will correct it to the wrong pattern. I have no way of knowing that it was actually a 4-bit error and not a 3-bit error from the other pattern.
Hi,
Thanks for your time. Plz consider this example:
codebook: 00000000 00001111 10011000
Pattern sent: 00000000
Pattern received: 11100000
should be a difference of 1) but i cant prove it. Even i cant prove what you are saying if i consider the above eg. If i correct
this pattern by correcting 3 bits then there is not a 7 bit difference between this corrected pattern and other patterns in
the code book??
Zulfi.
Thanks for your time. Plz consider this example:
codebook: 00000000 00001111 10011000
Pattern sent: 00000000
Pattern received: 11100000
sorry, theoretically i understand that in worst case its possible to have a difference of 7 ( and in best case it
should be a difference of 1) but i cant prove it. Even i cant prove what you are saying if i consider the above eg. If i correct
this pattern by correcting 3 bits then there is not a 7 bit difference between this corrected pattern and other patterns in
the code book??
Zulfi.
If you have a random, ad-hoc codebook then what you would do is compute the Hamming distance between the received pattern and each codeword. You would then correct the received pattern to whichever codeword is closest. So, in this case, the distances from your received pattern are:
00000000: D=3
00001111: D=7
10011000: D=4
So you would correct it to 00000000
But what if your received pattern was 10000000?
You would naturally a conclude that there was just a single error in the first bit and correct it to the all zero pattern. But what if it was the third pattern and there were actually two errors in the 4th and 5th positions? If that were the case, you would have a 2-bit error that you could not properly correct.
It is important to note that the error correcting strength of a code is based on the number of bits errors that can occur in ANY position and still be properly corrected. In this case, you can correct ANY 1 bit error, but because there is at least one 2-bit error that you cannot correct, the code cannot correct 2-bit errors. There may be specific error patterns that can be corrected that have 2 or more bits that are received incorrectly, but that doesn't matter because not ALL 2-bit errors can be corrected.
The key to determining this is the minimum distance of the codebook, which is the minimum Hamming distance between ANY pair of codewords in the codebook.
With three codewords, there are three ways to pair the codewords.
00000000 and 00001111: D=4
00000000 and 10011000: D=3
00001111 and 10011000: D=4
Thus, the minimum distance in this codebook is D=3 and we know that we can correct ANY 1-bit error, but we also know that there is at least one 2-bit error that we cannot correct.
We can also detect ANY 2-bit error AS LONG AS we make no attempt to correct ANY errors at all. That's a common misconception that even some textbooks make. They will will assert that a code like this can correct 1-bit errors and detect 2-bit errors. I can do one or the other, it cannot do both at the same time.
Which example are you talking about?
Try thinking of a visual example. Let's say that you have a bunch of farm houses spread out on a large, flat region of the country side. Packages for them are delivered by air mail - meaning that the packages are thrown out of an airplane and come down on a parachute. To save on money, the packages aren't marked with any information about who it is intended for; instead, it is assumed that the package belonds to whoever's house it landed closest to.
Now, let's assume that the pilot can always get the package no more than 3km from the intended house. How far apart do the houses have to be in order to ensure that all of the packages get to the intended recipients.
Do you see that if ANY two houses are, say, 5 miles apart that a package meant for one could be interpretted as a package meant, incorrectly, for the other? What if the houses were exactly six miles apart? Then there is the chance that the package could come down exactly inbetween the two and now it's 50/50 whether the correct person gets the package. So if we want to GUARANTEE that any package that arrives no more than three miles from the intended recipient will be received by the correct person, then ALL houses have to be located MORE than 6 miles from ANY other house.
If you want to correct up to 3 bit errors, then ALL codewords have to be located MORE than 6 errors away from ANY other codeword. Since we can't have a difference of 6.01, MORE than 6 means 7.
[0:sent]-->[1]-->[2]-->[3:received]-->[4]-->[5]-->[6]-->[7:another]
Each arrow above represents a one-bit change from the previous vector.
In order to correct ANY 3-bit error, then the above diagram must apply, asa minimum, to ANY and ALL pairs of codewords.
Try thinking of a visual example. Let's say that you have a bunch of farm houses spread out on a large, flat region of the country side. Packages for them are delivered by air mail - meaning that the packages are thrown out of an airplane and come down on a parachute. To save on money, the packages aren't marked with any information about who it is intended for; instead, it is assumed that the package belonds to whoever's house it landed closest to.
Now, let's assume that the pilot can always get the package no more than 3km from the intended house. How far apart do the houses have to be in order to ensure that all of the packages get to the intended recipients.
Do you see that if ANY two houses are, say, 5 miles apart that a package meant for one could be interpretted as a package meant, incorrectly, for the other? What if the houses were exactly six miles apart? Then there is the chance that the package could come down exactly inbetween the two and now it's 50/50 whether the correct person gets the package. So if we want to GUARANTEE that any package that arrives no more than three miles from the intended recipient will be received by the correct person, then ALL houses have to be located MORE than 6 miles from ANY other house.
If you want to correct up to 3 bit errors, then ALL codewords have to be located MORE than 6 errors away from ANY other codeword. Since we can't have a difference of 6.01, MORE than 6 means 7.
[0:sent]-->[1]-->[2]-->[3:received]-->[4]-->[5]-->[6]-->[7:another]
Each arrow above represents a one-bit change from the previous vector.
In order to correct ANY 3-bit error, then the above diagram must apply, asa minimum, to ANY and ALL pairs of codewords.
Hi,
Thanks for your package example. I am able to understand this sentence:
I have found answer to my question
Zulfi.
Thanks for your package example. I am able to understand this sentence:
Though i have not understood the following
But anyway, thanks for your patience and time and your examples and logics.
I have found answer to my question
should be 11.
Zulfi.
Yes, 11 is the minimum distance in the codebook required to correct 5 errors.
The description you didn't understand is actually pretty straight forward. Each step represents a change in one bit position from the previous step. We can put an actual example to it very easily. Again using our 7-bit code with just the all zeros and all ones codewords, let's assume that 0000000 is sent and 0110010 is received. Then one way to describe it (there are many other equivalent paths) would be
[0:sent] = 0000000
-->[1] = 0100000
-->[2] = 0110000
-->[3:received] = 0110010
-->[4] = 1110010
-->[5] = 1111010
-->[6] = 1111110
-->[7:another] = 1111111
This is one path to get from one codeword to another codeword. Along this path, there are six vectors that could be received that contain errors. The first three would be corrected to 0000000 while the second three would be corrected to 1111111.
The description you didn't understand is actually pretty straight forward. Each step represents a change in one bit position from the previous step. We can put an actual example to it very easily. Again using our 7-bit code with just the all zeros and all ones codewords, let's assume that 0000000 is sent and 0110010 is received. Then one way to describe it (there are many other equivalent paths) would be
[0:sent] = 0000000
-->[1] = 0100000
-->[2] = 0110000
-->[3:received] = 0110010
-->[4] = 1110010
-->[5] = 1111010
-->[6] = 1111110
-->[7:another] = 1111111
This is one path to get from one codeword to another codeword. Along this path, there are six vectors that could be received that contain errors. The first three would be corrected to 0000000 while the second three would be corrected to 1111111.
Hi,
Thanks. I am summarizing what i understood from your thankful work:
CW1=000000
CW2=111111
sent (000000)=111000 (received) (50%). We cant tell which code word is this. 3 bit error cant be detected if the codewords differ by 6 bits.
Now
CW1=0000000
CW2=1111111
sent (0000000)= 1110000 (received). Again 3 bit error but it can be corrected to 0000000 because the codewords differ by 7 bits.
Thanks for this method of explaining things.
Zulfi.
Thanks. I am summarizing what i understood from your thankful work:
CW1=000000
CW2=111111
sent (000000)=111000 (received) (50%). We cant tell which code word is this. 3 bit error cant be detected if the codewords differ by 6 bits.
Now
CW1=0000000
CW2=1111111
sent (0000000)= 1110000 (received). Again 3 bit error but it can be corrected to 0000000 because the codewords differ by 7 bits.
Thanks for this method of explaining things.
Zulfi.
You've go the right idea but a bit of a problem in terminology. We can definitely detect a three bit error. In fact, we can detect up to a fivebit error. But detecting that an error exists is not the same as being able to correct it.
Correct. However, note that if we choose to correct the errors then we can no longer detect bigger errors. If all we cared about was simply detectoring errors, this here we could detect up to six errors. But if we choose to correct errors then we can only correct up to three bit errors. Larger errors would be corrected to the wrong value and, hence, not detected.
| Thread starter | Similar threads | Forum | Replies | Date |
|---|---|---|---|---|
| C | MATLAB Soft-output decoder | Programming & Languages | 0 | |
| D | decode hamming code with added noise | Analog & Mixed-Signal Design | 8 | |
| G | Hamming Codes from Octal Numbers | General Science, Physics & Math | 15 | |
| B | hamming sound noise | Analog & Mixed-Signal Design | 9 | |
| D | minimum hamming distance in parity check | Homework Help | 0 |
