Hamming distance
|
|
In information theory, the Hamming distance, named after Richard Hamming, is the number of positions in two strings of equal length for which the corresponding elements are different. Put another way, it measures the number of substitutions required to change one into the other.
For example:
- The Hamming distance between 1011101 and 1001001 is 2.
- The Hamming distance between 2143896 and 2233796 is 3.
- The Hamming distance between "toned" and "roses" is 3.
The Hamming weight of a string is its Hamming distance from the zero string (string consisting of all zeros) of the same length. That is, it is the number of elements in the string which are not zero: for a binary string this is just the number of 1's, so for instance the Hamming weight of 11101 is 4.
The Hamming distance between two words a and b, viewed as elements of a vector space, can then be seen as the Hamming weight of a-b. If a and b are binary strings this is equivalent to a+b and to a XOR b. The Hamming distance is also equivalent to the Manhattan distance between two vertices in an n-dimensional hypercube, where n is the length of the words.
The Hamming distance is used in telecommunication to count the number of flipped bits in a fixed-length binary word, an estimate of error, and so is sometimes called the signal distance. Hamming weight analysis of bits is used in several disciplines including information theory, coding theory, and cryptography. For comparing strings of different lengths, or strings where insertions or deletions are expected, not just substitutions, a more sophisticated metric like the Levenshtein distance is more appropriate.
Adapted in part from Federal Standard 1037C.
References
Richard W. Hamming. Error-detecting and error-correcting codes, Bell System Technical Journal 29(2):147-160, 1950.
See also
de:Hamming-Abstand fr:Distance de Hamming ja:ãƒãƒŸãƒ³ã‚°è·é›¢ pl:Odległość Hamminga