Communications Fundamentals FAQ / Chapter 4

4.18.5 What Are Hamming Distance and Minimum Distance?

1. What Is Hamming Distance?
2. Why Is It Called Hamming Distance?
3. How Is Hamming Distance Calculated?
4. What Does Hamming Distance Tell Us?
5. What Is Minimum Distance?
6. Why Is Minimum Distance More Important Than Ordinary Distance?
7. How Can Codewords Be Visualized?
8. How Does Distance Relate to Error Detection?
9. Why Can't a Code Detect More Than (dmin - 1) Errors?
10. How Does Distance Relate to Error Correction?
11. How Many Errors Can a Code Correct?
12. Why Is the Division by Two Necessary?
13. What Is a Hamming Sphere?
14. Why Must Hamming Spheres Not Overlap?
15. What Is a Hamming Code?
16. How Does Minimum Distance Affect Code Design?
17. What Are Typical Minimum Distances?
18. Why Is Distance Important in Modern Communications?
19. How Do Hamming Distance and Minimum Distance Relate to Coding Gain?
20. Why Are Hamming Distance and Minimum Distance Important?

One of the central objectives of channel coding is to protect information against errors introduced during transmission or storage. To achieve this goal, communication engineers deliberately add redundancy to the transmitted data, creating codewords that can be distinguished from one another even when some bits are corrupted.

But how can we measure the ability of a code to detect or correct errors? How can we determine whether one code provides better protection than another? The answer lies in two fundamental concepts of coding theory: Hamming distance and minimum distance.

These concepts provide the mathematical foundation for error detection and error correction. They determine how many errors a code can detect, how many errors it can correct, and how reliable the code will be in practice. Whether dealing with simple parity checks, Hamming codes, Reed–Solomon codes, LDPC codes, or modern 5G coding systems, the concepts of distance remain central to understanding coding performance.

What Is Hamming Distance?

The Hamming distance between two binary sequences is the number of positions in which the corresponding bits differ.

For example: 101101 and 111001 differ in two positions. The Hamming distance is therefore d = 2.

The concept was introduced by Richard Hamming while working at Bell Laboratories and remains one of the most important ideas in coding theory.

Why Is It Called Hamming Distance?

The term is named after Richard Hamming, who developed many of the early concepts of error-correcting codes during the late 1940s and early 1950s.

Hamming recognized that errors in digital systems could be viewed geometrically. Instead of thinking of codewords merely as sequences of bits, they could be treated as points in a mathematical space. The distance between those points determines how easily they can be distinguished when errors occur.

This geometric interpretation revolutionized coding theory.

How Is Hamming Distance Calculated?

The calculation is straightforward.

Consider: 1010110 and 1110010. Comparing bit-by-bit, two positions differ. Therefore d = 2.

The Hamming distance is simply a count of differing bit positions.

What Does Hamming Distance Tell Us?

Hamming distance measures how different two codewords are.

A large distance means:

• The codewords are easily distinguished.
• More errors are required to transform one codeword into another.
• Better error protection is possible.

A small distance means:

• Codewords are close together.
• Fewer errors can cause confusion.
• Error protection is weaker.

Consequently, coding theorists seek codes whose codewords are separated by large distances.

What Is Minimum Distance?

A code normally contains many valid codewords.

The minimum distance is the smallest Hamming distance between any pair of valid codewords. It is usually denoted d_min.

The minimum distance is one of the most important parameters of a code because it determines both its error-detecting and error-correcting capability.

Why Is Minimum Distance More Important Than Ordinary Distance?

A code may contain some codewords that are very far apart.

However, if two codewords happen to be very close together, they limit the overall performance of the code. The weakest pair determines the code's capability. Consequently, the minimum distance governs the performance of the entire code.

For this reason, coding theorists focus primarily on d_min.

How Can Codewords Be Visualized?

A useful way to understand coding is to imagine codewords as points in a multidimensional space.

For example, consider the code: 000 and 111. These codewords lie at opposite corners of a three-dimensional cube. Their distance is 3. An error moves the received sequence away from the transmitted codeword. The decoder attempts to determine which valid codeword is closest.

This geometric interpretation provides valuable insight into error correction.

How Does Distance Relate to Error Detection?

Suppose a code has minimum distance: d_min.

To transform one valid codeword into another requires changing at least: d_min bits. Therefore, any error pattern involving fewer than d_min bit changes cannot convert one valid codeword into another valid codeword. The error will therefore be detected. This leads to an important result: the number of detectable errors = d_min – 1.

As minimum distance increases, error-detection capability improves.

Why Can't a Code Detect More Than (d_min - 1) Errors?

Consider a code with d_min = 4. Four errors could potentially transform one valid codeword directly into another valid codeword.

If this occurs, the receiver cannot detect the problem because the received sequence is itself a valid codeword. The decoder therefore accepts the wrong message.

Consequently, detection capability is limited to d_min – 1 errors.

How Does Distance Relate to Error Correction?

Error correction is more demanding than error detection.

The receiver must not only detect that an error occurred but must determine which codeword was originally transmitted. To do this, the received sequence must remain closer to the transmitted codeword than to any other valid codeword.

This leads to another fundamental result.

How Many Errors Can a Code Correct?

A code can correct: t = (d_min – 1)/2 errors.

This relationship appears throughout coding theory. Examples:

Greater minimum distance provides greater correction capability.

Why Is the Division by Two Necessary?

Imagine two codewords separated by distance 5. The midpoint lies 2.5 bits from either codeword. If two errors occur, the received sequence remains closer to the correct codeword.

If three errors occur, the received sequence may be closer to the wrong codeword. The decoder can therefore guarantee correction only up to (d_min – 1)/2 errors.

This geometric argument is one of the most elegant results in coding theory.

What Is a Hamming Sphere?

A Hamming sphere consists of all bit patterns lying within a specified distance of a codeword.

For example a sphere of radius 1 contains:

• The codeword itself.
• All patterns differing by one bit.

A sphere of radius 2 includes all patterns differing by up to two bits.

Error correction can be visualized as assigning received sequences to the nearest Hamming sphere.

Why Must Hamming Spheres Not Overlap?

Suppose two codewords have overlapping spheres.

A received sequence within the overlap could belong to either codeword. The decoder would be unable to determine the correct message. To guarantee unique correction Hamming spheres must remain separate.

This requirement leads directly to the minimum-distance criterion for error correction.

What Is a Hamming Code?

One of the earliest practical error-correcting codes is the Hamming code.

A typical example is the (7,4) Hamming code which converts 4 information bits into 7 transmitted bits and possesses d_min = 3.

Therefore it can:

• Detect two errors.
• Correct one error.

Hamming codes remain widely used as educational examples and in practical applications requiring simple error correction.

How Does Minimum Distance Affect Code Design?

Increasing minimum distance generally improves performance.

However, there is a cost. Greater distance usually requires:

• More redundancy.
• Lower code rate.
• Increased complexity.

Engineers therefore face a trade-off between:

• Reliability.
• Efficiency.

This trade-off lies at the heart of coding-system design.

What Are Typical Minimum Distances?

Examples include:

Modern coding systems often employ sophisticated structures that provide large effective distances while maintaining high code rates.

Why Is Distance Important in Modern Communications?

Distance remains a central concept even in advanced coding systems. Although modern codes may use:

• Iterative decoding.
• Probabilistic decoding.
• Soft-decision techniques.

their performance is still fundamentally linked to the separation between valid codewords.

Distance determines:

• Error probability.
• Coding gain.
• Decoder performance.
• Reliability.

Consequently, the concept remains as important today as it was when Hamming first introduced it.

How Do Hamming Distance and Minimum Distance Relate to Coding Gain?

Larger minimum distances generally improve a code's ability to withstand noise.

This reduces the signal-to-noise ratio required to achieve a given error rate. The resulting improvement is known as coding gain.

Many modern coding systems achieve substantial coding gains by employing code structures with favorable distance properties.

Why Are Hamming Distance and Minimum Distance Important?

Hamming distance and minimum distance provide the mathematical foundation for understanding error-control coding. They determine how many errors a code can detect, how many it can correct, and how reliably it can operate in the presence of noise.

Whether analyzing a simple parity code or a sophisticated LDPC decoder, engineers ultimately rely on distance concepts to evaluate coding performance. These ideas form one of the cornerstones of modern communications engineering.

Summary

Hamming distance is the number of bit positions in which two codewords differ, while minimum distance is the smallest Hamming distance between any pair of valid codewords in a code. The minimum distance determines the error-detection and error-correction capability of the code and provides one of the most important measures of coding performance.

A code with minimum distance d_min can detect up to (d_min – 1) errors and correct up to (d_min – 1)/2 errors. These relationships form the foundation of coding theory and remain central to the design of modern communication and storage systems.

Return to Chapter 4 FAQ 4.18.5