3-bit binary cube for finding hamming distance |
Two example distances: 100->011 has distance 3 (red path); 010->111 has distance 2 (blue path) |
4-bit binary hypercube for finding hamming distance |
Two example distances: 0100->1001 has distance 3 (red path); 0110->1110 has distance 1 (blue path) | 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 minimum number of substitutions required to change one into the other, or the number of errors that transformed one string into the other. Image File history File links This is a lossless scalable vector image. ...
Image File history File links This is a lossless scalable vector image. ...
A cube[1] is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex. ...
Image File history File links This is a lossless scalable vector image. ...
Image File history File links This is a lossless scalable vector image. ...
Image File history File links This is a lossless scalable vector image. ...
Image File history File links This is a lossless scalable vector image. ...
A square A projection of a cube (into a two-dimensional image) A projection of a hypercube (into a two-dimensional image) In geometry, a hypercube is an n-dimensional analogue of a square (n = 2) and a cube (n = 3). ...
Image File history File links This is a lossless scalable vector image. ...
Image File history File links This is a lossless scalable vector image. ...
A bundle of optical fiber. ...
In computer programming and formal language theory, (and other branches of mathematics), a string is an ordered sequence of symbols. ...
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.
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. In mathematics a metric or distance function is a function which defines a distance between elements of a set. ...
Strong induction, also known as complete induction, is a variant on the principle of mathematical induction. ...
In mathematics, triangle inequality is the theorem stating that for any triangle, the measure of a given side must be less than the sum of the other two sides but greater than the difference between the two sides. ...
The Hamming weight of a string of bits is the number of 1s in it. ...
For binary strings a and b the Hamming distance is equivalent to the number of ones in a xor b. The metric space of length-n binary strings, with the Hamming distance, is known as the Hamming cube; it is equivalent as a metric space to the set of distances between vertices in a hypercube graph. One can also view a binary string of length n as a vector in by treating each symbol in the string as a real coordinate; with this embedding, the strings form the vertices of an n-dimensional hypercube, and the Hamming distance of the strings is equivalent to the Manhattan distance between the vertices. Exclusive disjunction (usual symbol xor) is a logical operator that results in true if one of the operands (not both) is true. ...
The hypercube graph Q4. ...
A square A projection of a cube (into a two-dimensional image) A projection of a hypercube (into a two-dimensional image) In geometry, a hypercube is an n-dimensional analogue of a square (n = 2) and a cube (n = 3). ...
Taxicab geometry, considered by Hermann Minkowski in the 19th century, is a form of geometry in which the usual metric of Euclidean geometry is replaced by a new metric in which the distance between two points is the sum of the (absolute) differences of their coordinates. ...
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 (1950). 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 not just substitutions but also insertions or deletions have to be expected, a more sophisticated metric like the Levenshtein distance is more appropriate. Richard Wesley Hamming (February 11, 1915 – January 7, 1998) was a mathematician whose work had many implications for computer science and telecommunications. ...
Copy of the original phone of Alexander Graham Bell at the Musée des Arts et Métiers in Paris Telecommunication is the transmission of signals over a distance for the purpose of communication. ...
A bundle of optical fiber. ...
Coding theory is a branch of mathematics and computer science dealing with the error-prone process of transmitting data across noisy channels, via clever means, so that a large number of errors that occur can be corrected. ...
The German Lorenz cipher machine, used in World War II for encryption of very high-level general staff messages Cryptography (or cryptology; derived from Greek κÏυπτός kryptós hidden, and the verb γÏάφω gráfo write) is the study of message secrecy. ...
In information theory and computer science, the Levenshtein distance is a string metric which is one way to measure edit distance. ...
Algorithm example The Python function hamdist() computes the Hamming distance between two strings (or "sequential objects" mapped into strings) of equal length. Python is a high-level programming language first released by Guido van Rossum in 1991. ...
def hamdist(s1, s2): assert len(s1) == len(s2) return sum(ch1 != ch2 for ch1, ch2 in zip(s1, s2)) The following C++ function will compute the Hamming distance of two integers (considered as binary values, that is, as sequences of bits). The time is proportional to the Hamming distance rather than to the number of bits in the inputs. C++ (pronounced see plus plus, IPA: ) is a general-purpose, high-level programming language with low-level facilities. ...
int hamdist(int x, int y) { int dist = 0, val = x^y; while(val) { ++dist; val &= val - 1 } return dist; }
References Adapted in part from Federal Standard 1037C. Federal Standard 1037C, entitled Telecommunications: Glossary of Telecommunication Terms is a United States Federal Standard, issued by the General Services Administration pursuant to the Federal Property and Administrative Services Act of 1949, as amended. ...
Richard W. Hamming. Error Detecting and Error Correcting Codes, Bell System Technical Journal 26(2):147-160, 1950. Richard Wesley Hamming (February 11, 1915 – January 7, 1998) was a mathematician whose work had many implications for computer science and telecommunications. ...
In information theory and coding, an error-correcting code or ECC is a code in which each data signal conforms to specific rules of construction so that departures from this construction in the received signal can generally be automatically detected and corrected. ...
Year 1950 (MCML) was a common year starting on Sunday (link will display the full calendar) of the Gregorian calendar. ...
See also |
Feeds |
Contact