What Are Hamming Distance and Minimum Distance?
How Do They Determine Error-Correcting Capability?
Preview: Learn more about Hamming distance and minimum distance, and how they determine the ability of error-control codes to detect and correct transmission errors.
Hamming distance is one of the fundamental concepts of digital communications and coding theory. It measures the number of bit positions in which two binary sequences differ. The concept, introduced by Richard W. Hamming in 1950, provides the basis for analysing the error-detection and error-correction capabilities of virtually every modern error-control code, from simple parity checks to sophisticated Low-Density Parity-Check (LDPC) and polar codes.
In a digital communication system, information is represented as sequences of binary digits, or codewords. During transmission, noise, interference, or other impairments may cause one or more bits to change. Whether the receiver can detect or correct these errors depends on how different the valid codewords are from one another. Hamming distance provides a simple numerical measure of this difference.
The Hamming distance between two binary sequences is the number of bit positions in which they differ. For example, the codewords
10110110
and
10011100
differ in three bit positions and therefore have a Hamming distance of three. If two codewords differ in only one bit position, their Hamming distance is one. If they are identical, the Hamming distance is zero.
A useful way to visualize Hamming distance is to imagine every possible binary codeword occupying a point within a multidimensional space. The Hamming distance measures how far apart two codewords are within this code space. The farther apart the codewords are, the more transmission errors can occur before one valid codeword is mistaken for another.
The most important quantity for an error-control code is not the distance between any particular pair of codewords, but the minimum distance of the code, usually denoted by dₘᵢₙ. The minimum distance is the smallest Hamming distance between any two valid codewords in the entire code. It therefore represents the worst-case separation between codewords and determines the fundamental error-control capability of the code.
The minimum distance governs both error detection and error correction. If the minimum distance of a code is dₘᵢₙ, then the code can detect up to
dₘᵢₙ − 1
bit errors within a codeword because any smaller number of errors cannot transform one valid codeword into another. The receiver can therefore recognise that the received sequence is invalid.
To correct errors, the requirements are more demanding. The receiver must determine not only that an error has occurred but also which valid codeword was originally transmitted. A code having minimum distance dₘᵢₙ can correct up to
bit errors, where the brackets indicate that the result is rounded down to the nearest whole number. For example, a code with a minimum distance of three can correct one bit error, while a code with a minimum distance of five can correct two bit errors.
A simple example illustrates this principle. Suppose the valid codewords of a particular code all differ from one another by at least three bits. If a single transmission error occurs, the received word remains closer to the transmitted codeword than to any other valid codeword. The decoder therefore identifies the nearest valid codeword and corrects the error automatically. If two errors occur, however, the received sequence may lie approximately midway between two valid codewords, making reliable correction much more difficult.
One useful analogy is to imagine houses separated by wide spaces along a road. If a driver accidentally drifts slightly from the centre of the road, it is still obvious which house was intended. If the houses were built very close together, however, even a small deviation could lead to confusion. Increasing the separation between codewords has the same effect, making decoding more reliable in the presence of transmission errors.
Hamming distance applies to virtually every type of error-control code. Hamming codes derive their name directly from this concept and use carefully chosen parity relationships to achieve a minimum distance of three. More advanced block codes such as BCH and Reed–Solomon codes employ larger minimum distances to correct multiple errors. Modern coding techniques, including turbo codes, Low-Density Parity-Check (LDPC) codes, and polar codes, also rely fundamentally on maximizing the effective separation between valid codewords, although they employ far more sophisticated decoding algorithms.
It is important to distinguish Hamming distance from Euclidean distance. Hamming distance counts the number of differing bits between binary codewords, whereas Euclidean distance measures the geometric separation between signal points in a modulation constellation such as Quadrature Amplitude Modulation (QAM). Both concepts influence communication performance, but they apply at different stages of the communication system—Hamming distance in channel coding and Euclidean distance in modulation.
Today, Hamming distance remains one of the most fundamental concepts in communications engineering. It provides the mathematical framework for understanding why some codes can detect errors, why others can correct them, and how the performance of different coding schemes can be compared. Every modern digital communication system, from mobile telephones and satellite links to optical fibre networks and deep-space probes, relies on coding techniques whose performance is ultimately governed by Hamming distance and minimum distance.
Hamming distance and minimum distance therefore represent far more than abstract mathematical concepts. Together, they define the fundamental limits of error-control coding and provide the bridge between the physical errors introduced by a communication channel and the remarkable ability of modern communication systems to detect and correct those errors automatically.
Back to reading