Hamming Distance

Hamming Distance in Error Control

The central concepts in coding for error control are the idea of the Hamming distance. The Hamming distance between two words (of the same size) is the number of differences between the corresponding bits. We show the Hamming distance between two words x and y as d(x, y).

The Hamming distance can easily be found if we apply the XOR operation on the two words and count the number of 1s in the result. Note that the Hamming distance is a value greater than zero.

1. The Hamming distance d(000, 011) is 2 because 000 ⊕ 011 is 011 (two 1s).

2. The Hamming distance d(10101, 11110) is 3 because 10101 ⊕ 11110 is 01011 (three 1s).

Minimum Hamming Distance:

The minimum Hamming distance is the smallest Hamming distance between all possible pairs. We use "dmin" to define the minimum Hamming distance in a coding scheme. To find this value, we find the Hamming distances between all words and select the smallest one.

Hamming Distance and Error

When a code word is corrupted during transmission, the Hamming distance between the sent and received code words is the number of bits affected by the error. In other words, the Hamming distance between the received code word and the sent code word is the number of bits that are corrupted during transmission.

You May Also Like:

Types of Errors
Important Concepts in Error Detection and Correction
Block Coding Techniques
Simple Parity Check Code

For example, if the code word 00000 is sent and 01101 is received, 3 bits are in error and the Hamming distance between the two is d(00000, 01101) =3.

Minimum Distance for Error Detection:

To find the minimum Hamming distance in a code if we want to be able to detect up to s errors. If S errors occur during transmission, the Hamming distance between the sent code word and received code word is S. If our code is to detect up to S errors, the minimum distance between the valid codes must be s + 1, so that the received code word does not match a valid code word.

Minimum Distance for Error Correction:

Error correction is more complex than error detection, a decision is involved. When a received code word is not a valid code word, the receiver needs to decide which valid code word was actually sent. The decision is based on the concept of territory, an exclusive area surrounding the code word. Each valid code word has its own territory. We use a geometric approach to define each territory. We assume that each valid Code word has a circular territory with a radius of t and that the valid code word is at the center.

For example, suppose a code word x is corrupted by t bits or less. Then this corrupted code word is located either inside or on the perimeter of this circle. If the receiver receives a code word that belongs to this territory, it decides that the original code word is the one at the center. Note that we assume that only up to t errors have occurred; otherwise, the decision is wrong. The following Figure shows this geometric interpretation. Some texts use a sphere to show the distance between all valid block codes.

hamming distance