Hamming Distance

Q: How many errors can a code with minimum distance 3 correct?

One error, because $\lfloor (3 - 1)/2 \rfloor = 1$. The same code detects up to two errors. The Hamming (7,4) code is a well-known example with minimum distance 3.

In one sentence: Hamming distance counts the spots where two same-length codes differ, such as the bits in two binary words, and that count shows how many errors a code can catch.

$d(x, y) = \sum_{i=1}^{n} [x_i \ne y_i]$

Read it out loud: “d of x, y, the Hamming distance between x and y, equals the sum over i from 1 to n of a bracket. The bracket is 1 when x sub i is not equal to y sub i, and 0 when they are equal. The letter i counts the positions, and n is the number of positions.”

Before you start

The ideas and signs this page uses, explained from zero. For powers of ten, Greek letters and other notation in general, see Math basics.

Bits and binary words: A bit is a single binary digit, either 0 or 1. A string of bits, such as 1011101, is a row of 7 bits. Computers store and send everything as strings of bits, so comparing two bit strings is one of the most common tasks in computing. Each place in the string holds one of the two values.
Strings, length and position: A string is an ordered row of symbols, such as letters or bits. Its length is how many symbols it has. Each symbol has a position, counted from 1 at the left. In the string 1011101, the symbol in position 3 is the third 1 from the left, and the symbol in position 5 is 1 as well.
Subscripts, like $x_i$: A small number or letter written below a symbol is a subscript. $x_i$ is read ‘x sub i’ and means the symbol in position $i$ of the string $x$ . If $i = 3$ , then $x_3$ is the symbol in the third position. The letter $i$ is a placeholder that stands for any position number.
Not equal, $\ne$: The sign $\ne$ means ‘not equal to’. The statement $x_i \ne y_i$ is true when the two symbols in position $i$ are different and false when they are the same. In a count, a true statement is worth 1 and a false statement is worth 0.
The summation sign $\sum$: The Greek capital letter sigma, written $\sum$ , is the sign for adding up. $\sum_{i=1}^{n}$ means add the values for every position from $i = 1$ up to $i = n$ . It is a short way to write a long list of additions, such as one term for position 1, plus one for position 2, and so on up to position $n$ .
Square brackets, $[\ ]$ , and the Iverson bracket: Square brackets around a true or false statement turn it into a number. The bracket $[x_i \ne y_i]$ is 1 when the statement is true and 0 when it is false. This is called the Iverson bracket, and it lets us count the differences by adding the results.
The XOR sign $\oplus$: XOR, written $\oplus$ , takes two bits and gives 1 only when they are different. So $0 \oplus 1 = 1$ and $1 \oplus 1 = 0$ . Applied to two whole bit strings, XOR marks with a 1 each position where they differ, and with a 0 each position where they match.

What each symbol means

Symbol	Meaning
$d(x, y)$	The Hamming distance between the strings $x$ and $y$ , the count of positions where they differ. It is a plain whole number with no unit, from 0 up to $n$ . A distance of 0 means the two strings are identical.
$x$	The first string, a row of $n$ symbols such as bits (0 or 1). Its symbols are called $x_1, x_2$ and so on. It has no unit, because each symbol is a label such as a bit, not a measured amount.
$y$	The second string. It must have exactly the same length as $x$ , so that the positions line up one by one. Its symbols are $y_1, y_2$ and so on, and it also has no unit.
$n$	The length of both strings, which is the number of positions compared. It is a whole number, such as 7 for two 7-bit words. The distance can never be larger than this count, because there are only $n$ positions to differ in.
$i$	The position being checked, a counter that runs from 1 up to $n$ . It has no unit. The sum visits every position once, in order, from the left end to the right end of the strings.
$x_i$	The symbol in position $i$ of the first string $x$ , such as the bit 0 or 1 in that spot. It has no unit, because it is a label, not a measurement.
$y_i$	The symbol in position $i$ of the second string $y$ . Comparing $x_i$ with $y_i$ answers the question of whether the two strings differ in that one spot.
$[x_i \ne y_i]$	The Iverson bracket. It is 1 when the two symbols differ and 0 when they match. It turns a true or false statement into a number, so that adding the results counts the differences.
$\sum_{i=1}^{n}$	Add up the values for every position from $i = 1$ to $i = n$ . The result is one total for the whole string. It is the same as writing one term for each position and adding all the terms together.

The formula piece by piece

$x_i \ne y_i$: A true or false question about one position: are the symbols in position $i$ different? For $x = 1011101$ and $y = 1001001$ , position 1 has 1 in both, so the answer is false. Position 3 has 1 in $x$ and 0 in $y$ , so the answer is true.
$[x_i \ne y_i]$: The same question turned into a number. A true answer becomes 1 and a false answer becomes 0. So position 1 gives 0 and position 3 gives 1, and adding these numbers counts the differences.
$\sum_{i=1}^{n} [x_i \ne y_i]$: The total over all positions: add the 0s and 1s for positions 1 to $n$ . Each 1 is one difference, so the sum is the number of places where the two strings disagree.
$d(x, y) = \sum_{i=1}^{n} [x_i \ne y_i]$: The whole formula in one sentence: the Hamming distance between two strings equals the number of positions where their symbols differ, found by adding one for each difference.
$d(x, y) = \text{wt}(x \oplus y)$: A standard equivalent form. The distance equals the number of 1s in the XOR of the two strings, where $\text{wt}$ is the Hamming weight, which counts the 1s in a string. Computers often use this form because XOR and bit counting are fast operations.

What the formula is doing, and why

Hamming distance answers a simple question: how many positions do two strings differ in? The strings must be the same length, such as two 7-bit binary words. You line them up position by position and count each place where the symbols do not match. The answer is a plain count, with no unit.

What goes in and what comes out? Two strings $x$ and $y$ go in, each with $n$ symbols. The formula looks at each position $i$ from 1 to $n$ and asks whether the symbols differ there. The bracket turns each answer into a 0 or a 1, and the sum adds them up. The output is a whole number from 0 to $n$ .

Why add 0s and 1s? Adding is the easiest way to count. Each position that differs contributes 1 to the total, and each position that matches contributes 0, so the sum counts exactly the differences. The distance is 0 only when the two strings are identical. It is the same in both directions: the distance from $x$ to $y$ equals the distance from $y$ to $x$ . Two strings that differ in every position have distance $n$ .

Why does it matter for errors? When a message is sent, a few bits can flip along the way. A codeword is one of the valid strings a code allows. If every pair of valid codewords is at least $d$ apart, a code with minimum distance $d$ can detect up to $d - 1$ errors and correct up to $\lfloor (d-1)/2 \rfloor$ errors. The further apart the valid codewords are, the more damage a message can take before it turns into another valid message. The formula needs both strings to have the same length, because the positions must line up.

An everyday picture

Imagine two rows of square tiles, each tile showing one letter or bit, laid side by side. Slide one row over the other and count the columns where the tiles show different symbols. That count is the Hamming distance. Two identical rows give 0, and rows that differ in every column give the full row length.

Worked example: Distance between two 7-bit codewords

Compare the binary words $x = 1011101$ and $y = 1001001$ . Each one is a string of bits, and both have $n = 7$ positions. We want the number of positions where they differ, which is the Hamming distance $d(x, y)$ .

Line the two words up. Write them one above the other so that position 1 sits above position 1, and so on along the row. The first word is 1 0 1 1 1 0 1, and the second word is 1 0 0 1 0 0 1. Lining them up makes it possible to compare the same spot in each word.
Compare each position. Position 1 has 1 and 1, which match. Position 2 has 0 and 0, which match. Position 3 has 1 and 0, which differ. Position 4 has 1 and 1, which match. Position 5 has 1 and 0, which differ. Positions 6 and 7 both match, with 0 and 0, and 1 and 1.
Turn each comparison into 0 or 1. Each position that differs gives $[x_i \ne y_i] = 1$ , and each match gives 0. Only positions 3 and 5 give 1, so every other term is 0.
Add the terms. $d(x, y) = 0 + 0 + 1 + 0 + 1 + 0 + 0 = 2$ . The sum counts the two differing positions, and that count is the Hamming distance.
Cross-check with XOR. XOR gives 1 exactly where the bits differ, so $1011101 \oplus 1001001 = 0010100$ . The binary number 10100 equals 20 in decimal, because it is $16 + 4$ . It contains exactly two 1 bits, which matches the count of differing positions.
Try a pair that differs everywhere. The words 1100 and 0011 each contain two 1s, but they differ in all 4 positions. Position by position every comparison is a difference, so the distance is 4, not 0. Counting the 1s alone would miss this.
Read the result. The two words differ in 2 positions, so $d(x, y) = 2$ . A code with minimum distance 2 can detect a single flipped bit, but it cannot correct it, because the receiver cannot tell which of the two bits changed.

Answer: The two words differ in 2 positions, so $d(x, y) = 2$ . A code with minimum distance 2 can detect a single flipped bit, but it cannot correct it.

The numbers in this example are recomputed by script every time the site is built.

Common mistakes

Comparing strings of different lengths. Hamming distance is defined only when both strings have the same number of positions.
Counting the 1s in each word instead of comparing position by position. The words 1100 and 0011 both have two 1s, but they differ in all 4 positions, so $d = 4$ .
Measuring the difference in value. The binary numbers 1000 and 0111 are only one apart as numbers, but they differ in all 4 positions, so $d = 4$ .
Saying a code with distance 2 corrects one error. Distance 2 only detects one error. Correction needs a minimum distance of at least 3.

Where you will meet it

Error-correcting memory, where extra check bits let a computer spot and fix a single flipped bit.
Data transmission and storage, where codes are designed so that valid messages are far apart in Hamming distance.
Comparing aligned DNA or protein sequences of equal length, where each position holds one base or one amino acid.
Matching binary fingerprints, such as image hashes, to find near-duplicates by counting the bits that differ.

Questions people ask

What is the difference between Hamming distance and Hamming weight?

Hamming weight counts the 1s in one string. Hamming distance compares two strings. The distance between $x$ and $y$ equals the weight of $x \oplus y$ , which marks the positions where they differ.

Why is it called a distance?

It behaves like a distance. It is zero only when two strings are identical, it is never negative, and the distance from $x$ to $y$ is the same as the distance from $y$ to $x$ .

How many errors can a code with minimum distance 3 correct?

One error, because $\lfloor (3 - 1)/2 \rfloor = 1$ . The same code detects up to two errors. The Hamming (7,4) code is a well-known example with minimum distance 3.

Binary Number Value: Binary uses only the digits 0 and 1, and this formula turns a row of those digits into the ordinary number they stand for.
Shannon Entropy: Shannon entropy is one number, measured in bits, that says how unpredictable a source of messages is on average: the more predictable it is, the fewer bits its messages need.
Shannon-Hartley Theorem: The Shannon-Hartley theorem gives the fastest error-free rate, in bits per second, that a noisy channel can carry, based on its width and how strong the signal is compared with the noise.