Hamming distance

Also called: bit distance, Hamming distance between codes

The number of bit positions in which two equal-length binary codes differ. K-map neighbors and consecutive Gray codes have a Hamming distance of 1.

The Hamming distance between two binary codes of the same length is the number of positions where their bits differ. 1011 and 1001 differ only in the third bit, so their distance is 1. 0111 and 1000 differ in all four, so their distance is 4.

To compute it, XOR the two codes bit by bit and count the 1s in the result. Each 1 marks a position where they differ.

Why it matters in this course:

K-maps. Two cells are adjacent exactly when their codes have Hamming distance 1. That is the condition for combining two minterms into one term.
Gray code. A gray code is a sequence where each code is at distance 1 from the next. That is why K-map axes use it.
Group size. Inside a group of 2ᵏ cells, the farthest-apart pair is at distance k.

It matters beyond K-maps too. In error detection, a parity bit makes every valid code word at least distance 2 from every other, so any single flipped bit produces an invalid word. Codes with a minimum distance of 3 or more can even locate and correct a single error.

Note that Hamming distance has nothing to do with numeric difference: 7 and 8 are 1 apart as numbers but 4 apart in Hamming distance.

Worked examples

Example

Are these cells adjacent?

Use Hamming distance to test two pairs of 4-variable minterms.

1.
m6 = 0110 and m4 = 0100: XOR gives 0010, one 1. Distance 1, so adjacent.
2.
m11 = 1011 and m14 = 1110: XOR gives 0101, two 1s. Distance 2, so not adjacent.
3.
m7 = 0111 and m8 = 1000: XOR gives 1111. Distance 4, even though 7 and 8 are consecutive numbers.

Example

Distances along a 3-bit sequence

Compare the steps of the 3-bit Gray code 000, 001, 011, 010, 110, 111, 101, 100 with plain binary counting.

1.
Gray code: every step changes one bit, and the wrap from 100 back to 000 does too. All distances are 1.
2.
Binary: 001 → 010 has distance 2, 011 → 100 has distance 3, and the wrap 111 → 000 has distance 3.
3.
Only the Gray sequence keeps every pair of neighbors at distance 1.

Common mistakes

Confusing Hamming distance with numeric difference.
Comparing codes of different lengths. Pad them to the same width first.
Counting the 0s of the XOR instead of the 1s.

Practice Hamming distance

Interactive questions with instant feedback and a worked solution for every wrong answer.

Karnaugh Maps lesson full course

Learn it step by step

Hamming distance is taught in Karnaugh Maps and Number Systems.

Karnaugh Maps →Number Systems →

All terms