Hamming Distance in Error Control: Concepts, Minimum Distance and Worked Examples

Learn how to calculate Hamming distance, find a code's minimum distance, apply detection and correction limits, and decode a Hamming(7,4) word.

KnowledgeGate Team

Exam prep & CS education

Updated 5 Nov 20265 min read
Hamming Distance in Error Control: Concepts, Minimum Distance and Worked Examples

Distance sounds geometric, but error control applies it to bit strings: how many positions must change to turn one string into another? Count the differences, extend them to a code's minimum distance, then build and decode one Hamming(7,4) word. Hamming distance supports both detection and correction, but their guarantees are not interchangeable. Parity, CRC, checksums and ARQ form the broader Data Link Layer Error Control in Computer Networks toolkit; pairwise distance, minimum-distance guarantees and parity-position decoding supply the code-design detail.

1. Error Control Starts With Valid Codewords

A sender chooses a valid codeword. Noise may flip positions in transit, so the receiver sees a changed string. A bit error means that a 0 became 1 or a 1 became 0.

Detection asks whether the received string is invalid. Correction asks which valid codeword was most likely sent. Redundant bits separate valid codewords, making both tasks possible.

Consider the repetition code {000, 111}. If 000 is sent and one bit flips, the receiver might get 001. It is invalid and one flip from 000, so the error is detectable and correctable under a one-error assumption. But if three bits flip, 000 becomes valid word 111. The receiver cannot tell that an error occurred.

2. Hamming Distance: Count the Positions That Differ

For equal-length binary strings, the Hamming distance d(x,y) is the number of positions at which their bits differ. An equivalent shortcut is:

d(x,y) = wt(x XOR y)

Here, wt means the number of 1s in the XOR result. Unequal-length strings are outside the definition being used here.

Take x = 1011101 and y = 1001001. Align all seven positions:

Position

1

2

3

4

5

6

7

x

1

0

1

1

1

0

1

y

1

0

0

1

0

0

1

x XOR y

0

0

1

0

1

0

0

Only positions 3 and 5 differ. Thus x XOR y = 0010100, whose weight is 2, so d(x,y) = 2.

The boundary checks are useful: d(1011101,1011101)=0, while d(000000,111111)=6. Distance is non-negative, is zero only for identical strings, is symmetric, and cannot exceed the common string length.

Bit comparison chart for x = 1 0 1 1 1 0 1 and y = 1 0 0 1 0 0 1, with differences in columns 3 and 5, XOR row 0 0 1 0 1 0 0, and Hamming distance d(x,y)=2.

3. From Pairwise Distance to the Minimum Distance of a Code

The minimum distance of a code is the smallest distance between any two distinct valid codewords:

d_min = min d(c_i,c_j), for i != j

One arbitrary pairwise distance is not automatically d_min. Every distinct pair must be considered. For C = {00000, 11100, 10011, 01111}, there are six pairs:

Pair

XOR

Distance

00000, 11100

11100

3

00000, 10011

10011

3

00000, 01111

01111

4

11100, 10011

01111

4

11100, 01111

10011

3

10011, 01111

11100

3

The smallest result is 3, so d_min=3.

A code detects up to s bit errors when d_min >= s+1. It corrects up to t bit errors when d_min >= 2t+1. This code therefore guarantees detection of up to 2 errors and correction of up to 1 error. The words “up to” and “guarantees” matter. Some larger error patterns may be noticed, but not every pattern of that size is guaranteed to be detected or corrected.

4. Nearest-Codeword Decoding and Its Failure Boundary

Suppose 00000 is sent and one bit flips, producing r = 10000. Its distances from the listed codewords are:

[d(r,00000), d(r,11100), d(r,10011), d(r,01111)] = [1, 2, 2, 5]

The unique nearest word is 00000, so nearest-codeword decoding corrects the error.

Now suppose two bits flip and the receiver gets r = 11000. The distances in the same order are [2, 1, 3, 4]. The nearest valid word is 11100, not the transmitted 00000. A code with d_min=3 can guarantee two-error detection, but it cannot guarantee two-error correction.

Geometrically, radius-1 neighbourhoods around the valid codewords do not overlap when d_min=3. Radius-2 neighbourhoods can overlap. A real decoder does not automatically know how many bits the channel flipped.

5. Build and Decode One Hamming(7,4) Codeword

Use even parity and number positions from 1 to 7. Parity bits occupy the power-of-two positions 1, 2, and 4. Place data 1011 at positions 3, 5, 6, and 7:

[p1, p2, 1, p4, 0, 1, 1]

The coverage groups are p1 -> {1,3,5,7}, p2 -> {2,3,6,7}, and p4 -> {4,5,6,7}.

  • For p1, positions 3, 5, and 7 contain 1,0,1. They already contain two 1s, so p1=0.

  • For p2, positions 3, 6, and 7 contain 1,1,1. They contain three 1s, so p2=1 makes the total even.

  • For p4, positions 5, 6, and 7 contain 0,1,1. They contain two 1s, so p4=0.

The transmitted codeword is 0110011. If bit 6 flips, the receiver gets 0110001.

Recheck the groups using the received bits. Group {1,3,5,7} has two 1s, so s1=0. Group {2,3,6,7} has three 1s, so s2=1. Group {4,5,6,7} has one 1, so s4=1. Read the syndrome as s4s2s1 = 110 in binary, which equals 6. Flip position 6 back to recover 0110011, then read positions 3, 5, 6, and 7 to recover data 1011.

Hamming(7,4) has d_min=3, so this single-error correction follows from the same minimum-distance rule.

Hamming(7,4) position map showing codeword 0110011, received word 0110001 with bit 6 flipped, syndrome 110₂ = 6, and recovered data 1011.

6. Common Hamming-Distance and Hamming-Code Traps

  1. Confusing two kinds of distance. The distance between sent and received strings is not the code's minimum distance. Calculate d_min only across distinct valid codewords, then use it for guarantees.

  2. Assuming detection implies equal correction. Keep the rules together: detect d_min-1; correct floor((d_min-1)/2). When d_min=3, these values are 2 and 1.

  3. Mixing position or syndrome order. Number positions before calculating, then interpret s4s2s1 as a binary position. Ordinary Hamming(7,4) corrects one bit. An extended Hamming code adds an overall parity bit, so do not claim SECDED for this seven-bit construction.

7. How Exams Turn the Concept Into Questions

Typical questions ask you to count a distance through XOR, find d_min from a codebook, infer guaranteed detection and correction, or locate an erroneous bit from a syndrome. Computer Networks MCQs provides a nearby practice set for the subject.

Two rapid checks capture the distance rules. If d_min=6, a code guarantees detection of 5 errors and correction of floor(5/2)=2. To guarantee correction of 3 errors, it needs d_min >= 2(3)+1 = 7.

For Hamming-code construction, also remember 2^r >= m+r+1. With m=8, r=3 fails because 8 < 8+3+1 = 12. Using r=4 works because 16 >= 8+4+1 = 13. This sizes the parity-bit set; it does not replace an understanding of minimum distance.

8. The Short Version and the Next Step

XOR two equal-length strings and count the 1s to get their pairwise distance. Take the smallest distance among distinct valid codewords to get d_min. A code guarantees detection of up to d_min-1 errors and correction of up to floor((d_min-1)/2). In Hamming(7,4), a non-zero syndrome identifies the position of a single erroneous bit.

For a structured core-subject path, use CS Fundamentals for Placements by Sanchit Sir. GATE-focused learners can continue with GATE Guidance by Sanchit Sir, while the CS Fundamentals category is the broader browsing hub.