Hamming distance between two bit-strings of equal length is the number of bit positions at which they are different. In other words, Hamming distance is the number of mismatches at the same bit position between two same-length words.
For example:
Consider two 3-bit code words, 000 and 001. Here, the Hamming distance is 1, as both the words differ at only one-bit position from each other (at the LSB bit). In general, we use the following cubical figure to determine the Hamming distances between any pair of code words for 3-bit word size. In this figure, all such words that are having Hamming distance of 1 are situated at the adjacent vertices.
Considering 000 and 011, here, the Hamming distance is 2, as both the words differ at two-bit positions (two right bits). In the above figure, the code words that have Hamming distance of 2 can be reached by traversing two edges from one code word to the other one.
Distance of a Code
The Distance of a code is known as the minimum Hamming distance between any two valid code words. The Hamming distance, or the Distance of a code, is an important concept in error detection and correction. This determines the error detection as well as correction capability of the code.
Example – Code with 4 codewords – {001,010,100,111} : This code has a distance of 2, as any pair of code words differ by 2 bits from each other. Since the distance is 2, it can detect any single-bit error.
Example – Code with 2 codewords – {000,111} : This code has a distance of 3. In this case, any single or double-bit error can be detected. If double-bit errors are not likely to happen, then this code can correct any single-bit error along with any single-bit error detection.
| To detect up to k-bit errors, the code distance should be at least k+1 To correct up to k-bit errors, the code distance should be at least 2k+1 |