Opening your learning space
Starting the app …
Opening your learning space
Starting the app …
Hamming distance counts positions at which two equal-length strings differ.
Free to browse · flashcards or a multiple-choice quiz · import from Essential
Formula
dimensionless integer count of positions, from 0 to n
| Symbol | Meaning | Unit |
|---|---|---|
| Two equal-length words over the same alphabet | bit strings or symbols | |
| Word length | positions | |
| Indicator equal to 1 when the condition is true and 0 otherwise | dimensionless |
d_H(x,y)=\sum_{i=1}^{n}\mathbf{1}[x_i\ne y_i]The metric assumes equal-length words over the same alphabet and counts unequal positions. For binary words it equals the Hamming weight of their bitwise XOR. A code with minimum Hamming distance dmin can detect up to dmin−1 errors and uniquely correct up to floor((dmin−1)/2) errors, provided the received error pattern stays within that limit. This guarantee does not itself provide an efficient decoder.
The metric assumes equal-length words over the same alphabet and counts unequal positions. For binary words it equals the Hamming weight of their bitwise XOR. A code with minimum Hamming distance dmin can detect up to dmin−1 errors and uniquely correct up to floor((dmin−1)/2) errors, provided the received error pattern stays within that limit. This guarantee does not itself provide an efficient decoder.
Hamming distance counts positions at which two equal-length strings differ.
Guaranteed number of correctable errors
The guarantee assumes a code with minimum distance dmin.
Use the example for Hamming distance between bit strings to explain which inputs determine the requested output.
The example connects concrete inputs to its result.
Hamming distance counts positions at which two equal-length strings differ.
The relation applies only under its stated assumptions.
Applying the relation to a different case without checking its stated assumptions.
Check the validity range before substituting values: The metric assumes equal-length words over the same alphabet and counts unequal positions. For binary words it equals the Hamming weight of their bitwise XOR. A code with minimum Hamming.
Formula cluster
Hamming distance counts positions at which two equal-length strings differ.
x=1011101 and y=1001001 differ at positions 3 and 5, so dH=2. A code with dmin=3 can guarantee correction of one bit error.
Measure bit errors, compare codewords and assess minimum-distance guarantees for detection or correction.
Here is how to work through a typical Hamming distance between bit strings (dH(x,y) = Zahl unterschiedlicher Stellen) task step by step:
Task
Use the example for Hamming distance between bit strings to explain which inputs determine the requested output.
Solution path
The example connects concrete inputs to its result.
Hamming distance counts positions at which two equal-length strings differ.
The relation applies only under its stated assumptions.
Compare two words position by position and count every place where symbols differ. For x=1011101 and y=1001001, positions three and five differ, so dH=2. Equal length is required; the metric does not count insertions or deletions. For bit strings, XOR them and count the resulting ones. Distance compares positions, not numeric values. Error-correction guarantees use the minimum distance of the whole code and apply only within the stated error bound. Insertions and deletions require a different distance definition. Check these assumptions before applying the guarantee.
If dmin is the smallest Hamming distance between distinct valid codewords, the code can detect up to dmin−1 errors. Unique correction is guaranteed when 2t<dmin. Thus dmin=3 corrects one bit error, but does not guarantee correction of two. This is a worst-case guarantee, not a statement about how often errors occur. Distance compares positions, not numeric values. Error-correction guarantees use the minimum distance of the whole code and apply only within the stated error bound. Insertions and deletions require a different distance definition. Check these assumptions before applying the guarantee.
An XOR bit is 1 exactly where the two input bits differ. The Hamming distance of equal-length binary words is therefore the Hamming weight of their bitwise XOR, the number of ones. For 1011101 XOR 1001001, the result is 0010100 with two ones. This is convenient computationally but requires equal-length strings. Distance compares positions, not numeric values. Error-correction guarantees use the minimum distance of the whole code and apply only within the stated error bound. Insertions and deletions require a different distance definition. Check these assumptions before applying the guarantee.
The guaranteed correction count is floor((dmin−1)/2). For dmin=5, floor(4/2)=2: any received word at most two bit positions from a valid codeword is uniquely assigned to it. Three errors can move the received word closer to another codeword. The guarantee follows because the corresponding Hamming balls do not overlap. Distance compares positions, not numeric values. Error-correction guarantees use the minimum distance of the whole code and apply only within the stated error bound. Insertions and deletions require a different distance definition. Check these assumptions before applying the guarantee.
The usual Hamming distance is defined for equal-length strings. With different lengths, it is unclear whether missing positions, insertions or shifts count as errors. Do not silently pad with zeros because that changes the sequence’s meaning. Edit distance or other metrics handle insertion and deletion errors. Choose a metric matching the error channel rather than the easiest calculation. Distance compares positions, not numeric values. Error-correction guarantees use the minimum distance of the whole code and apply only within the stated error bound. Insertions and deletions require a different distance definition. Check these assumptions before applying the guarantee.
Quanta exam set
Curated exam set for "Hamming distance between bit strings":
Question (front)
Which formula describes Hamming distance between bit strings?
Answer in your set
Question (front)
How do you rearrange Hamming distance between bit strings for Guaranteed number of correctable errors?
Answer in your set
Question (front)
Which common mistake happens with Hamming distance between bit strings?
Answer in your set
+ 7 more cards: units, variables, derivation, example, exam task
The formula set contains 10 cards. After importing, review them and start practicing; your ratings determine later review intervals.
This list names subject references and further reading. A page or section number appears when it is part of the reference; these are not verbatim quotations.
Create a curated FSRS exam set for dH(x,y) = Zahl unterschiedlicher Stellen: formula recall, variables, derivation, rearrangement, worked example, common mistakes and exam context.
Curated formula set · LaTeX · FSRS spaced repetition · import from Essential