Hamming Distance and Error-Correction Guarantees

Measuring Differences Between Binary Words

A binary code represents information using words whose entries are $0$ or $1$. When a word is transmitted, some entries may be changed. The key question is how far apart the valid codewords are: if a received word is close enough to one codeword, can we know whether an error occurred or determine which word was sent? Hamming weight and Hamming distance give precise answers. Throughout, words of length $n$ are vectors in $\mathbb{F}_2^n$, where $\mathbb{F}_2=\{0,1\}$ and arithmetic is modulo $2$.

Definition: The Hamming weight $\operatorname{wt}(\mathbf{x})$ of a binary vector $\mathbf{x}$ is the number of its coordinates equal to $1$. The Hamming distance between $\mathbf{x},\mathbf{y}\in\mathbb{F}_2^n$ is $$ d_H(\mathbf{x},\mathbf{y})=\#\{i:x_i\ne y_i\}. $$ A binary code $C$ of length $n$ is a set of binary vectors in $\mathbb{F}_2^n$; it is a linear code if it is a subspace. For a code containing at least two words, its minimum distance is $d=\min\{d_H(\mathbf{c},\mathbf{c}'):\mathbf{c},\mathbf{c}'\in C,\ \mathbf{c}\ne\mathbf{c}'\}$.

Thus the minimum distance compares distinct valid words, not a word with itself. The minimum exists because a code of length $n$ is a finite set. The number $d$ is a positive integer. For binary vectors, adding an error vector $\mathbf{e}$ flips exactly the coordinates where $\mathbf{e}$ has a $1$. Consequently, the received vector after sending $\mathbf{c}$ and making those errors is $\mathbf{y}=\mathbf{c}+\mathbf{e}$, and $d_H(\mathbf{c},\mathbf{y})=\operatorname{wt}(\mathbf{e})$.

For any two binary vectors, their distance is the weight of their difference: $d_H(\mathbf{x},\mathbf{y})=\operatorname{wt}(\mathbf{x}-\mathbf{y})$. Over $\mathbb{F}_2$, subtraction and addition give the same result, so this is also $\operatorname{wt}(\mathbf{x}+\mathbf{y})$. This identity is especially useful for linear codes.

Proposition: If $C$ is a linear code containing at least two words, then its minimum distance is the smallest weight of a nonzero codeword: $$ d=\min\{\operatorname{wt}(\mathbf{u}):\mathbf{u}\in C,\ \mathbf{u}\ne\mathbf{0}\}. $$

Proof. Let $\mathbf{c},\mathbf{c}'$ be distinct words in $C$. Since $C$ is a subspace, $\mathbf{c}-\mathbf{c}'$ belongs to $C$, and it is nonzero because $\mathbf{c}\ne\mathbf{c}'$. The distance identity gives $d_H(\mathbf{c},\mathbf{c}')=\operatorname{wt}(\mathbf{c}-\mathbf{c}')$. Thus every distance between distinct codewords is the weight of a nonzero codeword. Conversely, if $\mathbf{u}\in C$ is nonzero, then $\mathbf{0},\mathbf{u}\in C$ and $d_H(\mathbf{0},\mathbf{u})=\operatorname{wt}(\mathbf{u})$. Therefore the sets of values being minimized are the same, and their minima are equal. $\square$

What Minimum Distance Guarantees

An error is detected if the received vector is not a codeword: a membership check can flag it as invalid. An error is corrected if the receiver can identify the transmitted codeword uniquely from the received vector. These are different tasks. A received word can be invalid and therefore detectable, yet be equally close to two valid words and therefore not uniquely correctable.

Theorem (Minimum-distance guarantees): Let $C\subseteq\mathbb{F}_2^n$ be a code with at least two words and minimum distance $d$.

Every nonzero error affecting at most $d-1$ coordinates is detected.
Every error affecting at most $t=\left\lfloor\frac{d-1}{2}\right\rfloor$ coordinates is uniquely correctable by choosing the nearest codeword.

Both bounds are sharp in general: a code with minimum distance $d$ cannot be guaranteed to detect every error of weight $d$, or to uniquely correct every error of weight $t$ when $2t\ge d$.

Proof. First consider detection. Suppose $\mathbf{c}\in C$ is sent and a nonzero error $\mathbf{e}$ of weight at most $d-1$ occurs. The received vector is $\mathbf{y}=\mathbf{c}+\mathbf{e}$, so $\mathbf{y}\ne\mathbf{c}$. If $\mathbf{y}$ were also in $C$, then it would be a distinct codeword from $\mathbf{c}$, and $d_H(\mathbf{c},\mathbf{y})=\operatorname{wt}(\mathbf{e})\le d-1$. This contradicts the definition of minimum distance. Hence $\mathbf{y}\notin C$, so the error is detected. To see why the bound cannot be raised to $d$ for every code, choose two codewords $\mathbf{c},\mathbf{c}'$ at distance $d$, which exist by the definition of the minimum. Sending $\mathbf{c}$ and changing the $d$ coordinates on which it differs from $\mathbf{c}'$ produces $\mathbf{c}'$, a valid codeword. A membership check does not detect that error.

For correction, we first verify the triangle inequality for Hamming distance. At any coordinate where $\mathbf{x}$ and $\mathbf{z}$ differ, at least one of $\mathbf{x}$ and $\mathbf{y}$, or $\mathbf{y}$ and $\mathbf{z}$, must differ. Counting such coordinates gives $d_H(\mathbf{x},\mathbf{z})\le d_H(\mathbf{x},\mathbf{y})+d_H(\mathbf{y},\mathbf{z})$. Now suppose $\mathbf{y}$ is received after at most $t=\lfloor(d-1)/2\rfloor$ errors from a transmitted $\mathbf{c}$. Then $d_H(\mathbf{y},\mathbf{c})\le t$. If another codeword $\mathbf{c}'\ne\mathbf{c}$ were also within distance $t$, the triangle inequality would give $$ d\le d_H(\mathbf{c},\mathbf{c}')\le d_H(\mathbf{c},\mathbf{y})+d_H(\mathbf{y},\mathbf{c}')\le 2t\le d-1, $$ a contradiction. Thus $\mathbf{c}$ is the unique codeword within distance $t$. A nearest codeword exists because $C$ is finite, and it must be $\mathbf{c}$.

Finally, suppose $2t\ge d$, and take codewords $\mathbf{c},\mathbf{c}'$ at distance $d$. Divide the $d$ coordinates where they differ into two groups, each of size at most $t$; such a division is possible because $d\le2t$. Construct $\mathbf{y}$ by using the entries of $\mathbf{c}'$ on the first group and those of $\mathbf{c}$ elsewhere. Then $d_H(\mathbf{y},\mathbf{c})\le t$, and $d_H(\mathbf{y},\mathbf{c}')\le t$. The same received word is consistent with either codeword after at most $t$ errors, so unique correction cannot be guaranteed. This proves sharpness of the correction bound. $\square$

Applying the Bounds to Short Codes

Worked Example: A Repetition Code

Consider the length-four code $C=\{0000,1111\}$. Find its minimum distance and the guaranteed numbers of detectable and correctable errors. Then check what happens after one and two errors when $0000$ is sent.

The only pair of distinct codewords is $0000,1111$. They differ in all four coordinates, so $d=4$. The detection guarantee is $d-1=3$ errors, and the correction guarantee is $\lfloor(4-1)/2\rfloor=1$ error.

Suppose one error changes the second coordinate. The received word is $0100$, and its distances to the two codewords are $d_H(0100,0000)=1$ and $d_H(0100,1111)=3$. The unique nearest codeword is $0000$.

If two errors change the first two coordinates, the received word is $1100$. Now $d_H(1100,0000)=2$ and $d_H(1100,1111)=2$. The word is not a codeword, so the error is detected, but it is tied between the two codewords and cannot be uniquely corrected. This check agrees with the guarantee of one correctable error.

Worked Example: An Even-Parity Code

Let $C=\{000,011,101,110\}$, the set of length-three words with an even number of $1$s. Find $d$, then test a one-coordinate error and a two-coordinate error from $000$.

The distances from $000$ to $011,101,110$ are all $2$. The other three pairwise comparisons give $011-101=110$, $011-110=101$, and $101-110=011$ in $\mathbb{F}_2^3$; each difference has weight $2$. Thus every pair of distinct words is at distance $2$, and $d=2$. The code guarantees detection of one error and correction of $\lfloor(2-1)/2\rfloor=0$ errors.

Changing one coordinate of $000$ to obtain $001$ gives a word outside $C$, since it has odd weight, so the error is detected. But the distances are $d_H(001,000)=1$, $d_H(001,011)=1$, and $d_H(001,101)=1$; also $d_H(001,110)=3$. There is no unique nearest codeword, confirming that one error is not guaranteed correctable. Changing two coordinates can produce $011$, which is itself a codeword. That error is not detected, as expected beyond the one-error detection guarantee.

Worked Example: A Linear Code with Minimum Distance Three

Let $C$ be the linear code generated over $\mathbb{F}_2$ by $\mathbf{g}_1=11100$ and $\mathbf{g}_2=10011$. Find its minimum distance and decode a received word obtained by changing the last coordinate of $00000$.

The four codewords are the possible sums of the generators: $00000$, $11100$, $10011$, and $11100+10011=01111$. The three nonzero codewords have weights $3,3,4$. By the proposition for linear codes, $d=3$. Therefore the code guarantees detection of two errors and correction of $\lfloor(3-1)/2\rfloor=1$ error.

Changing the last coordinate of $00000$ gives $\mathbf{y}=00001$. Its distances to the four codewords are $$ \begin{aligned} d_H(00001,00000)&=1,\\ d_H(00001,11100)&=4,\\ d_H(00001,10011)&=2,\\ d_H(00001,01111)&=3. \end{aligned} $$ Thus $00000$ is uniquely nearest, and the one-error correction returns the transmitted word. The distances explicitly verify the decoding rather than relying on the bound alone.

Common Pitfall: Halving the Distance Incorrectly

A tempting but incorrect rule is to say that a code of minimum distance $d$ corrects $\lfloor d/2\rfloor$ errors. For the repetition code $\{0000,1111\}$, this would claim correction of two errors. But the received word $1100$ is distance $2$ from both $0000$ and $1111$. The correct condition is $2t<d$, not $2t\le d$; equivalently, the guaranteed radius is $\lfloor(d-1)/2\rfloor$.

Detection and correction also should not be conflated. An error can be detected whenever the received word is not in the code, even if it is too close to multiple codewords for unique correction. For the length-four repetition code, the two-error word $1100$ illustrates this distinction: it is invalid and detectable, but its source is ambiguous. The minimum-distance bounds give guarantees for every possible transmitted word and every allowed error pattern, not just for a particular example.

Check Your Understanding

Use the definitions and minimum-distance guarantees to answer each question. When you identify a nearest codeword, compare the relevant distances explicitly.

Find the minimum distance of $C=\{000,111\}$. How many errors does it guarantee detecting and correcting?
For $C=\{0000,1111\}$, compute the distances from $1010$ to both codewords. Is the transmitted word uniquely determined if at most two errors occurred?
For the linear code generated by $1100$ and $0011$, list all codewords and determine its minimum distance using nonzero weights.
Explain why an error that changes $d$ coordinates can escape detection for some code with minimum distance $d$.
State the strict inequality that a correction radius $t$ must satisfy in terms of the minimum distance $d$, and explain what fails at equality.

Hamming Distance and Error-Correction Guarantees

What You'll Learn

Measuring Differences Between Binary Words

What Minimum Distance Guarantees