Error-Correcting Codes: Hamming Codes Explained

Data is constantly being corrupted: a cosmic ray flips a bit in memory, static disturbs a radio signal, or a scratch damages a disc. Error-correcting codes let computers not only notice these mistakes but fix them automatically. The Hamming code, invented in the late 1940s, was the first practical example, and its mathematics is simple enough to do by hand with nothing more than addition modulo 2.

A Frustrated Engineer at Bell Labs

Richard Hamming worked at Bell Telephone Laboratories in the late 1940s, running programs on a relay-based computer that read its input from punched cards. The machine could detect some errors, but when it did, it simply abandoned the job. On weekends, when no operators were present, Hamming would return to find his programs had stopped. He famously asked himself: if the machine can detect an error, why can't it locate and correct it? His answer was published in 1950 as "Error Detecting and Error Correcting Codes".

Parity Bits: Detecting Errors

The simplest idea is a parity bit. Add one extra bit so that the total number of 1s is even. For example, the data \( 1011 \) has three 1s, so we append 1 to get \( 10111 \).

If any single bit flips during transmission, the count of 1s becomes odd and the receiver knows something went wrong. But a single parity bit cannot say which bit flipped, and it misses errors where two bits flip. Hamming's breakthrough was to use several overlapping parity bits so that the pattern of failed checks pinpoints the error.

The Arithmetic: Modulo 2

All calculations use XOR, written \( \oplus \), which is addition modulo 2:

$$ 0 \oplus 0 = 0, \quad 0 \oplus 1 = 1, \quad 1 \oplus 0 = 1, \quad 1 \oplus 1 = 0 $$

The XOR of a group of bits is 0 if the number of 1s is even and 1 if it is odd.

The Hamming(7,4) Code

Hamming(7,4) sends 4 data bits using 7 bits in total. Number the positions 1 to 7. Positions that are powers of two (1, 2, 4) hold parity bits \( p_1, p_2, p_4 \); the rest (3, 5, 6, 7) hold data bits \( d_3, d_5, d_6, d_7 \).

The clever part is which positions each parity bit checks. Write each position number in binary:

• \( p_1 \) checks every position whose binary form has a 1 in the units place: 1, 3, 5, 7.
• \( p_2 \) checks positions with a 1 in the twos place: 2, 3, 6, 7.
• \( p_4 \) checks positions with a 1 in the fours place: 4, 5, 6, 7.

Each parity bit is chosen so that its group has an even number of 1s:

$$ p_1 = d_3 \oplus d_5 \oplus d_7, \qquad p_2 = d_3 \oplus d_6 \oplus d_7, \qquad p_4 = d_5 \oplus d_6 \oplus d_7 $$

Worked Example 1: Encoding 1011

Encode the data bits \( 1011 \).

Step 1. Place data bits. \( d_3 = 1,\ d_5 = 0,\ d_6 = 1,\ d_7 = 1 \).

Step 2. Compute parity bits.

• \( p_1 = d_3 \oplus d_5 \oplus d_7 = 1 \oplus 0 \oplus 1 = 0 \)
• \( p_2 = d_3 \oplus d_6 \oplus d_7 = 1 \oplus 1 \oplus 1 = 1 \)
• \( p_4 = d_5 \oplus d_6 \oplus d_7 = 0 \oplus 1 \oplus 1 = 0 \)

Step 3. Assemble positions 1 to 7. \( p_1\, p_2\, d_3\, p_4\, d_5\, d_6\, d_7 = 0\,1\,1\,0\,0\,1\,1 \).

The codeword is 0110011.

Step 4. Check. Group 1, 3, 5, 7 holds bits \( 0,1,0,1 \): two 1s, even. Group 2, 3, 6, 7 holds \( 1,1,1,1 \): four 1s, even. Group 4, 5, 6, 7 holds \( 0,0,1,1 \): two 1s, even. All checks pass.

Decoding: The Syndrome Points to the Error

The receiver recomputes the three checks on what it received:

$$ c_1 = r_1 \oplus r_3 \oplus r_5 \oplus r_7, \quad c_2 = r_2 \oplus r_3 \oplus r_6 \oplus r_7, \quad c_4 = r_4 \oplus r_5 \oplus r_6 \oplus r_7 $$

Reading \( c_4 c_2 c_1 \) as a binary number gives the syndrome. If it is 0, there is no detectable error. Otherwise, the syndrome is the position of the flipped bit. This works because a bit at position \( k \) belongs exactly to the groups matching the 1s in the binary form of \( k \), so flipping it fails exactly those checks.

Worked Example 2: Correcting an Error

The codeword 0110011 is sent, but bit 6 flips, so the receiver gets 0110001.

Step 1. List received bits. \( r_1 = 0, r_2 = 1, r_3 = 1, r_4 = 0, r_5 = 0, r_6 = 0, r_7 = 1 \).

Step 2. Recompute the checks.

• \( c_1 = 0 \oplus 1 \oplus 0 \oplus 1 = 0 \)
• \( c_2 = 1 \oplus 1 \oplus 0 \oplus 1 = 1 \)
• \( c_4 = 0 \oplus 0 \oplus 0 \oplus 1 = 1 \)

Step 3. Syndrome. \( c_4 c_2 c_1 = 110_2 = 6 \).

Step 4. Correct. Flip bit 6 back: 0110001 becomes 0110011, the original codeword. Reading positions 3, 5, 6, 7 recovers the data \( 1011 \).

Worked Example 3: A Second Message

Encode \( 0101 \), then suppose bit 3 is corrupted.

Step 1. Data. \( d_3 = 0,\ d_5 = 1,\ d_6 = 0,\ d_7 = 1 \).

Step 2. Parity. \( p_1 = 0 \oplus 1 \oplus 1 = 0 \); \( p_2 = 0 \oplus 0 \oplus 1 = 1 \); \( p_4 = 1 \oplus 0 \oplus 1 = 0 \).

Step 3. Codeword. \( 0\,1\,0\,0\,1\,0\,1 \), that is, 0100101.

Step 4. Error at position 3. Received: 0110101.

Step 5. Checks. \( c_1 = 0 \oplus 1 \oplus 1 \oplus 1 = 1 \); \( c_2 = 1 \oplus 1 \oplus 0 \oplus 1 = 1 \); \( c_4 = 0 \oplus 1 \oplus 0 \oplus 1 = 0 \).

Step 6. Syndrome. \( 011_2 = 3 \). Flip bit 3 to recover 0100101 and the data \( 0101 \). Correct.

Hamming Distance: Why It Works

The Hamming distance between two strings is the number of positions where they differ. For example, 0110011 and 0100101 differ in positions 3, 5 and 6, a distance of 3.

The key fact is that every pair of distinct Hamming(7,4) codewords differs in at least 3 positions. A single error moves a codeword a distance of 1, which is still closer to the original than to any other codeword (at least 2 away), so the decoder can always find the right one. In general, a code with minimum distance \( d \) can correct up to \( \left\lfloor \frac{d-1}{2} \right\rfloor \) errors.

Hamming(7,4) is also a perfect code. There are \( 2^4 = 16 \) codewords, and each "owns" itself plus its 7 single-error neighbours, a sphere of 8 strings. Since \( 16 \times 8 = 128 = 2^7 \), these spheres fill the entire space of 7-bit strings with no waste.

Real-World Use

• ECC memory: servers use an extended Hamming code (adding one overall parity bit), called SECDED, that corrects any single-bit error and detects any double-bit error. A common layout protects 64 data bits with 8 check bits.
• Storage and communication: modern systems use more powerful codes, such as Reed-Solomon, LDPC and polar codes, but they all build on Hamming's ideas of distance and syndromes.

Did You Know?

• The rate of Hamming(7,4) is \( 4/7 \approx 57\% \), but longer Hamming codes are more efficient: Hamming(15,11) carries 11 data bits in 15, and Hamming(127,120) carries 120 in 127.
• Hamming received the 1968 Turing Award, and the IEEE's Richard W. Hamming Medal is named in his honour.
• The NASA Voyager probes, launched in 1977, rely on error-correcting codes to send readable data across billions of kilometres.

Key Takeaways

• A single parity bit detects one error but cannot locate it.
• Hamming(7,4) places parity bits at positions 1, 2 and 4, each checking positions whose binary form shares that bit.
• The syndrome \( c_4c_2c_1 \) gives the exact position of a single-bit error.
• Minimum Hamming distance 3 is what makes single-error correction possible.
• Extended Hamming codes protect the memory in servers and many critical systems.

If you need step-by-step solutions for coding theory, parity checks or a digital communications assignment, Amathify's subject experts and PhD scholars are ready to help via WhatsApp or the Ask a Question form.