Hamming distance counts the bit positions where two pieces of data disagree. The idea takes one sentence to state, and it is the number that decides how many errors a code can detect and how many it can correct. This page works through the counting first, then shows what the count is actually used for.

• What is Hamming Distance ?
• How do you actually compute it ?
• Why does it matter in error correction ?

What is Hamming Distance ?

Conceptually, Hamming Distance is a very simple concept. It indicates the number of bit differences between two binary data. I think just a couple of examples would be better than long lines of explanation.

For example, let's suppose that we are given two binary data A and B as shown in Figure 1.

Figure 1. Two binary strings of the same length, one above the other. Nothing is marked yet, and finding the difference by eye is the exercise.

Now you are asked to figure out how many bits are different between the data A and the data B. You can easily figure out the difference just comparing bit by bit. In this case, you would figure out only one bit difference as shown in Figure 2.

Figure 2. The one position where the two strings disagree, boxed in red. Data A carries 0 there and Data B carries 1, and every other column matches.

Now let's figure out Hamming Distance between the two data. It is so simple. Just replace the term 'The number of bits that are different' with the term 'Hamming Distance' as shown in Figure 3.

Figure 3. The same picture with the label changed. 'The number of bits that are different' and 'Hamming Distance' are two names for the same count.

In may text book or technical journals, they often use even more scary terms (mathematical expression) as shown in Figure 4. This indicates Hamming Distance between codeword w(i) and w(j).

Figure 4. The same count again in the notation a textbook would use. D(w_i, w_j) = 1 says exactly what the sentence underneath Figure 3 said.

As another example, you are given another data w(i) and w(j) as follows. The hamming distance can be calculated as follows.

Figure 5. A second pair with three disagreeing positions, each boxed. Counting the boxes gives 3, so D(w_i, w_j) = 3.

Those pictures assume two conditions, and both matter once you leave the example behind. The first is that the two strings must be the same length. Hamming distance compares position against position, so there is no answer at all for a 28 bit string and a 30 bit one. The second is that only the positions matter, never the values. A 0 against a 1 counts as one difference, and so does a 1 against a 0.

The name is worth a line of its own. Richard Hamming worked at Bell Labs and published the idea in 1950, in the paper that also gave us the Hamming codes. He called it a distance because it behaves like one, and that is more than a figure of speech. The count is never negative, it is 0 only when the two strings are identical, and it gives the same answer whichever string you start from.

The fourth property is the one that earns the word. Take a detour through a third string and you never use fewer bit flips than going straight there. So distances add up the way distances on a map do, and that is what lets you reason about codewords as points spread out in a space.

• It is a count of positions, not a comparison of values : line the two strings up and tally the columns that disagree. The tally is the distance.
• Both strings have to be the same length : the measure is undefined otherwise, which is why it applies to codewords of a fixed block size rather than to arbitrary data.
• D(w_i, w_j) is the same count in formal notation : a paper that writes it that way is saying nothing the boxed columns in Figures 2 and 3 do not already say.
• It really is a distance : never negative, zero only for identical strings, symmetric, and it obeys the triangle inequality. Codewords can therefore be treated as points with gaps between them.

How do you actually compute it ?

Counting by eye works for one example and stops working immediately after. A receiver compares codewords millions of times a second, so the count has to come from an operation a processor already has. It does, and the operation is XOR.

XOR is the operation that does it. 1 XOR 1 is 0 and 0 XOR 0 is 0, while 1 XOR 0 and 0 XOR 1 both give 1. That is the addition table of GF(2), and it returns a 1 in exactly the positions where two strings disagree. Apply it to the whole pair and the result marks every difference.

That leaves one thing to do. Count the 1 bits in the result, and the count is the Hamming distance. Counting the 1 bits in a word has its own name, the Hamming weight, and most processors have a single instruction for it called popcount. So the whole calculation is two instructions.

Figure 6 runs the two steps on a short example, with the disagreeing columns shaded so you can check the result against the definition.

Figure 6. XOR marks every disagreeing position with a 1, and the Hamming weight of that result is the Hamming distance. Two instructions replace the column by column comparison.

Writing the relationship down gives D(a, b) = w(a XOR b), where w is the Hamming weight. The two ideas are the same measurement under two names. Hamming weight is the distance from a string to the all zero string, because XOR with zero changes nothing.

• XOR marks the disagreements : it returns 1 exactly where the two strings differ, so the result is a map of every position that has to be counted.
• Hamming weight is the count of 1 bits : D(a, b) = w(a XOR b), and w(a) is just D(a, 0). The two terms describe one measurement.
• The whole thing is two instructions : XOR then popcount. That is why a decoder can afford to measure the distance to many candidate codewords rather than to one.

Why does it matter in error correction ?

So far the distance has been a property of two particular strings. The useful quantity is a property of a whole code, and it is the smallest distance between any two of its codewords. That one number decides what the code can do, and everything a datasheet claims about detection and correction comes from it.

Call it d_min. A code is a chosen set of legal codewords out of all the possible bit patterns, and d_min is the closest any two of them get. Errors move a received word away from the codeword that was sent, one bit flip per unit of distance. So recovery is a question of two distances. How far has the word moved, and how far apart were the codewords to begin with?

Two rules follow, and they are the reason this page exists. A code with minimum distance d_min detects up to d_min - 1 errors, because that many flips can never reach another legal codeword. It corrects up to (d_min - 1) / 2 errors, rounded down, because within that radius the nearest codeword is still the one that was sent. Correction costs roughly twice the distance that detection costs.

The table below applies both rules to four codes that appear early in any coding course.

The first row explains why a single parity bit cannot correct anything. A single parity bit has d_min of 2, so it detects one error and corrects none, and two errors in the same block always pass. The repetition code sends each bit three times, which pushes d_min to 3 and buys one correctable error. The Hamming code reaches the same d_min of 3 while sending 7 bits for every 4, where the repetition code spends 3 for every 1. That efficiency is why the Hamming code is the more useful of the two.

The last row shows what one extra bit buys. Adding an overall parity bit to the Hamming code lifts d_min from 3 to 4. Correction does not improve, because 3 divided by 2 and 4 divided by 2 both round down to 1. Detection does improve, from 2 errors to 3. One bit therefore buys a code that fails safely rather than guessing wrongly.

This is also the point where the term connects to the rest of the site. The rules quoted above are the ones on the Error Detection/Correction page, and the distance they depend on is the one counted here.

• The code is described by its smallest gap : d_min is the closest any two legal codewords come. Every claim about detection and correction traces back to that single number.
• Detect d_min - 1, correct half of that : detection only asks whether the word is illegal, and correction has to name which codeword was meant. Naming costs twice as much.
• More distance is bought with more bits : the repetition code and the Hamming code reach the same d_min, and one of them spends far fewer bits doing it. That comparison is what code design is about.
• An even d_min helps detection, not correction : going from 3 to 4 adds a detected error and no corrected one, because the correction rule rounds down.