Hamming distance
From Free net encyclopedia
Contents |
Definition
In information theory, the Hamming distance between two strings of equal length is the number of positions for which the corresponding symbols are different. Put another way, it measures the number of substitutions required to change one into the other, or the number of errors that transformed one string 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.
Special properties
For a fixed length n, the Hamming distance is a metric on the vector space of the words of that length, as it obviously fulfills the conditions of non-negativity, identity of indiscernibles and symmetry, and it can be shown easily by complete induction that it satisfies the triangle inequality as well.
The Hamming distance between two words a and b can also be seen as the Hamming weight of a−b for an appropriate choice of the − operator.
For binary strings a and b this is equivalent to a xor b. The Hamming distance of binary strings is also equivalent to the Manhattan distance between two vertices in an n-dimensional hypercube, where n is the length of the words.
History and Applications
The Hamming distance is named after Richard Hamming, who introduced it in his fundamental paper about error-detecting and error-correcting codes. It is used in telecommunication to count the number of flipped bits in a fixed-length binary word as an estimate of error, and therefore is sometimes called the signal distance. Hamming weight analysis of bits is used in several disciplines including information theory, coding theory, and cryptography. However, for comparing strings of different lengths, or strings where besides substitutions also insertions or deletions have to be expected, a more sophisticated metric like the Levenshtein distance is more appropriate.
References
Adapted in part from Federal Standard 1037C.
Richard W. Hamming. Error-detecting and error-correcting codes, Bell System Technical Journal 29(2):147-160, 1950.
See also
ca:Distància de Hamming de:Hamming-Abstand es:Distancia de Hamming fr:Distance de Hamming ja:ハミング距離 ko:해밍_거리 nl:Hammingafstand pl:Odległość Hamminga fi:Hammingin etäisyys