BTT Mathematics / Primary Mathematics Learning Hub / Hamming Distance and Error Checks
The Hamming distance between two equal-length strings is the number of positions in which they differ. It gives a simple way to measure how many symbol changes separate one codeword from another.
For example, 10110 and11100 differ in positions2 and4, so their Hamming distance is 2.
Error-detecting and error-correcting codes deliberately place valid codewords far apart. If a received string is close to exactly one valid codeword, the distance structure can help identify what was most likely sent.
This guide is Primary Mathematics enrichment. It connects binary strings, parity, distance, logical constraints and checking. It extends Digit Sums and Arithmetic Error Checks, Logic, Deduction and Truth Conditions and Number Bases, Place-Value Codes and Numeral Systems.
Modern coding theory is far broader than these examples. The goal here is to make the core combinatorial logic visible through small binary codes.
Hamming distance · Parity checks · Minimum distance · Detection · Correction · Nearest-code decoding · 24 questions · Worked answers
1. Hamming distance counts changed positions
Compare strings position by position. The strings must have the same length for the standard Hamming distance used here.
Worked example A
d(0000,0000)=0.
Worked example B
d(0000,1000)=1.
Worked example C
d(10110,11100)=2.
Worked example D
d(0101,1010)=4; every position differs.
Distance is symmetric
d(x,y)=d(y,x), because the same positions differ in either comparison direction.
2. A parity bit checks whether the number of ones has the expected parity
Under even parity, the total number of 1s in the transmitted word must be even.
Worked example E: Append an even-parity bit
Data1011 contains three1s, so append1 to make four1s: 10111.
Worked example F
Data1010 contains two1s already, so append0: 10100.
Worked example G: Detect one flipped bit
If10100 changes to10110, the number of1s becomes three, violating even parity. The receiver detects an error.
Worked example H: Two errors can escape simple parity
If two bits flip, parity changes twice and can return to even. Even parity guarantees detection of any odd number of flipped bits, but not every even number.
3. Minimum distance controls guaranteed error protection
For a code C, the minimum distance dmin is the smallest Hamming distance between two distinct valid codewords.
Worked example I: Three-bit repetition code
C={000,111}. The two codewords differ in all three positions, so dmin=3.
Worked example J: Four-bit repetition code
C={0000,1111}. Here dmin=4.
Worked example K: Even-parity length-4 code
The valid words include0000,0011,0101,0110,1001,1010,1100,1111. The smallest distance between distinct codewords is 2.
Worked example L: Why spacing matters
If two valid codewords differ in only one position, a single error can transform one valid codeword directly into the other. No distance-based detector can then distinguish transmission error from valid transmission.
4. A code of minimum distance d detects up to d−1 errors
If fewer than d positions change, a valid codeword cannot turn into another valid codeword, because distinct valid words are at least distance d apart.
Worked example M: dmin=3
The repetition code {000,111} can guarantee detection of up to 2 errors.
Worked example N: dmin=4
{0000,1111} can guarantee detection of up to 3 errors.
Worked example O: Even parity
Since dmin=2, the length-4 even-parity code guarantees detection of 1 error. It may detect more in some cases, but one is the guaranteed count from minimum distance.
5. Unique correction needs error balls not to overlap
A code with minimum distance d can guarantee correction of up to floor((d−1)/2) errors.
Worked example P: dmin=3
floor((3−1)/2)=1. The three-bit repetition code can correct one error.
Worked example Q: dmin=4
floor(3/2)=1. The four-bit repetition code also guarantees correction of one error.
Worked example R: dmin=2
floor(1/2)=0. The simple even-parity code detects one error but does not guarantee correction of one.
6. Nearest-code decoding chooses the uniquely closest valid codeword
For C={000,111}, receive001. Distances are d(001,000)=1 and d(001,111)=2, so decode to 000.
Worked example S
Receive011. Distances to000 and111 are2 and1, so decode to 111.
Worked example T: Tie means ambiguity
For C={0000,1111}, receive0011. Its distance to each valid codeword is2. Nearest-code decoding has a tie, so no unique decision is justified from distance alone.
Guarantee versus lucky recovery
A code may sometimes recover from more errors than its guaranteed correction radius, but without extra information that success is not assured for every error pattern.
7. Practice: 24 original questions
Questions 1–8: Hamming distance and parity
1. Find d(0000,0000).
2. Find d(0000,1000).
3. Find d(10110,11100).
4. Find d(0101,1010).
5. Append one even-parity bit to data1011.
6. Append one even-parity bit to data1010.
7. Under even parity, would received10110 pass or fail the parity check?
8. Can two bit flips always be detected by one even-parity bit?
Questions 9–16: Minimum distance and guarantees
9. Find dmin for code {000,111}.
10. Find dmin for {0000,1111}.
11. What is dmin of the length-4 even-parity code?
12. A code has dmin=3. How many errors are guaranteed detectable?
13. With dmin=4, how many are guaranteed detectable?
14. With dmin=2, how many are guaranteed detectable?
15. With dmin=3, how many errors are guaranteed correctable?
16. With dmin=5, how many errors are guaranteed correctable?
Questions 17–24: Decoding and reasoning
17. For C={000,111}, decode received001 by nearest distance.
18. Decode011.
19. Decode110.
20. For C={0000,1111}, compare the distances of received0011 to both codewords.
21. Is the nearest-code decision unique in Question20?
22. Why can a code with two valid words at distance1 not guarantee detection of one error?
23. What does dmin measure?
24. Distinguish guaranteed correction capability from a lucky recovery beyond the guarantee.
8. Worked answers
Answers 1–8
1. 0.
2. 1.
3. 2.
4. 4.
5. 10111. Four1s total.
6. 10100. Two1s total.
7. Fail. 10110 contains three1s, which is odd.
8. No. Two flips can preserve even parity.
Answers 9–16
9. 3.
10. 4.
11. 2.
12. 2 errors. dmin−1.
13. 3 errors.
14. 1 error.
15. 1 error.
16. 2 errors. floor((5−1)/2)=2.
Answers 17–24
17. 000. Distances1 and2.
18. 111. Distances2 and1.
19. 111. d(110,111)=1 while d(110,000)=2.
20. Distance2 from each.
21. No. The nearest-code rule ties.
22. One bit flip can transform one valid word directly into the other valid word.
23. The smallest Hamming distance between two distinct valid codewords.
24. Guaranteed correction succeeds for every error pattern up to the stated radius; recovery beyond that radius may occur for some patterns but is not assured.
9. Teaching and transfer
If a learner compares binary strings as whole numbers, cover everything except one position at a time. Hamming distance is positional mismatch count, not numerical subtraction.
When parity is treated as correction
A single parity bit can reveal that something is wrong without identifying which bit changed. Detection and correction are different jobs.
When minimum distance feels abstract
Draw valid codewords as points separated by distance. Error correction needs non-overlapping neighbourhoods around those points.
When a decoding tie occurs
Do not invent a winner. A tie means the available distance information is insufficient for a unique decision.
When guarantees are overclaimed
State the worst-case guarantee from dmin. A particular received word may be recoverable beyond that radius, but the code cannot promise the same result for every pattern.
Connect to checking systems
Parity is a compact cousin of the arithmetic filters in Digit Sums and Arithmetic Error Checks: both detect some errors without proving full correctness.
Continue through this enrichment collection
For constraint grids, use Latin Squares, Sudoku Structure and Constraint Propagation. For one-sided surfaces, use Möbius Strips, One-Sided Surfaces and Topology. For geometric enclosure, use Convex Hulls, Extreme Points and Geometric Enclosure.
Return to the BTT Primary Mathematics Learning Hub.
Original enrichment guide with 24 original practice questions and separate worked answers. Error guarantees are stated from minimum Hamming distance for the small codes defined locally.