What is Hamming distance?
The number of positions at which two bit strings (or character strings) of the same length differ. It equals the number of 1s in the exclusive OR of the two bit strings. For example, the Hamming distance between 1011010 and 0110011 is 4. The smallest distance between any two codewords of a code is its minimum Hamming distance; a code with minimum Hamming distance d can detect errors of up to d − 1 bits and correct errors of up to (d − 1) ÷ 2 bits, rounded down.
Japanese name: ハミング距離
Hamming distance appears in 3 practice questions across 1 topic, including Information Theory and Coding Basics.
Field: Information Theory and Coding Basics
Error detection and correction capability
The farther apart the codewords, the less likely an error is to turn one into another. In a code with minimum Hamming distance d, an error of d − 1 bits or fewer cannot produce another codeword, so it can be detected, and if the error is at most (d − 1) ÷ 2 bits, the codeword nearest to the received word is the original, so it can be corrected. For example, the repetition code that sends each bit three times has d = 3 and corrects a 1-bit error by majority vote.
FAQ
Are Hamming distance and Hamming code the same thing?
No. Hamming distance is a measure that counts the differences between two bit strings, while a Hamming code is a code built to have a minimum Hamming distance of 3, which can correct a 1-bit error. Both are named after Hamming.
Can the Hamming distance between bit strings of different lengths be found?
Hamming distance is defined only between strings of the same length. To count differences including inserted and deleted characters, the edit distance (Levenshtein distance) is used.