Newtonpedia ES
Home › Mathematics › Hamming distance
Mathematics · 1950

Hamming distance

The number of positions at which two equal-length strings differ, used to detect and correct errors in data transmission.

Year
1950
People involved
Richard Hamming
Section
Mathematics

History

The Hamming distance is a simple way to measure how alike two strings of symbols of the same length are: you count the positions where they differ. Two binary words such as 1011101 and 1001001 differ in two bits, so their distance is 2. The idea looks elementary, but it is essential for understanding which errors a communication system can detect and which it can fix.

Before Hamming's work, telecommunication and digital computing systems often suffered from random bit corruption caused by electrical noise or equipment faults. Checking methods such as the parity bit existed, but they were limited: they could signal that something had gone wrong without locating the error or recovering the message. Richard Hamming, an American mathematician working at Bell Laboratories, faced these failures in the machines he used.

In 1950 Hamming published his paper Error detecting and error correcting codes, where he introduced the distance between codewords and the codes that now bear his name, which can correct a single-bit error. The key idea is that valid codewords are chosen far enough apart from one another. If an error changes a word, it remains closer to its original than to any other valid word, so the receiver can infer the intended message. In theory, a code whose minimum distance is d can detect up to d-1 errors and correct up to half of that value, rounded down.

The concept spread quickly. Block codes, coding theory and the counting of differing bits became part of telecommunications engineering. Later came more powerful codes, such as Reed-Solomon and convolutional codes, but the framework Hamming set out remains in use. Today the Hamming distance underpins error correction in computer memory, data storage, wireless communication and satellite transmission. It is also used in cryptography, in comparing genetic sequences as a measure of difference, and in programming, where counting differing bits between two numbers is a routine operation.

Timeline

  • 1950Richard Hamming publishes Error detecting and error correcting codes, introducing the distance between codewords.
  • 1950It is established that a minimum distance d allows detecting d-1 errors and correcting half of that value.

Trivia and anecdotes

An example with words

The distance can also be measured between words: the distance between tener and reses is 3, since they differ in three letters at the same positions.

People involved

Other milestones in Mathematics