Hamming Code

The Problem: Data Corruption

When we transmit digital data, it travels through a physical medium (a channel) where it is vulnerable to noise and interference. These disturbances can corrupt the data, causing a bit to flip from a '0' to a '1' or vice versa. To ensure reliable communication, we need methods to handle these errors.

A common approach is error detection. One of the earliest techniques is the parity check. A single parity bit is added to a block of data, but it has a major limitation: it can detect that an odd number of errors occurred, but it cannot tell us which bit is wrong, and thus cannot correct it. Hamming codes provide the additional check information needed to locate and correct a single-bit error.

Introduction to Hamming Codes

Hamming codes are a family of linear error-correcting codes described by Richard Hamming in 1950. Compared with a single parity bit, their check bits form a syndrome that identifies a single-bit error and enables correction of single-bit errors. For the standard code, the minimum distance also allows every double-bit error to be detected. This is achieved by adding carefully structured redundancy to the data.

Hamming Distance and Code Capability

The error-correcting capability of a code is determined by its minimum Hamming distance. For a code to be able to:

• Detect up to $e$ errors, its minimum distance must be $d_{min} \ge e + 1$.
• Correct up to $t$ errors, its minimum distance must be $d_{min} \ge 2t + 1$.

The standard Hamming code has a minimum distance of $d_{min} = 3$. This means it can correct $t = \lfloor (3-1)/2 \rfloor = 1$ single-bit error and detect up to $e = d_{min} - 1 = 2$ bit errors. With this distance, a word with one flipped bit has a unique valid codeword at the required correction distance, so the receiver can identify and correct that error.

The Hamming(7,4) code is a single-error-correcting (SEC) code with $d_{min} = 3$. Adding one overall parity bit gives the extended Hamming(8,4) code with $d_{min} = 4$. A conventional SEC-DED decoder corrects one-bit errors and detects double-bit errors without correcting them. For three or more errors, the decoder's correction result is not guaranteed.

Case Study: The (7,4) Hamming Code

The (7,4) Hamming code is a standard example that demonstrates the core principles. The notation (n, k) means:

• $k = 4$: The number of data bits in the original message.
• $n = 7$: The total number of bits in the final encoded word.
• This means we add $n-k = 3$ redundant parity bits.

Standard Construction: Parity Bits at Powers of Two

To construct the 7-bit codeword, we arrange the data and parity bits in a specific order. The bit positions are numbered 1 through 7. We display bits from left to right as positions 1 to 7 (position 1 is the leftmost, position 7 is the rightmost).

• Parity Bits ($P_1, P_2, P_4$) are placed at positions that are powers of two (1, 2, 4).
• Data Bits ($D_1, D_2, D_3, D_4$) occupy the 4 input data bits and are placed in the remaining positions (3, 5, 6, 7).

Parity Check Rules

Each parity bit checks a unique set of positions (including its own). The rule is: a parity bit at position $2^i$ checks all bit positions $j$ whose binary representation has a '1' in the $i$-th place.

• $P_1$ (position 1, binary 001): Checks positions 1, 3, 5, 7 (those with a '1' in the last binary digit).
• $P_2$ (position 2, binary 010): Checks positions 2, 3, 6, 7 (those with a '1' in the middle binary digit).
• $P_4$ (position 4, binary 100): Checks positions 4, 5, 6, 7 (those with a '1' in the first binary digit).

Visualizing the Logic: The Venn Diagram

A Venn diagram represents these relationships. Each circle represents the set of bits controlled by one parity bit. The goal with even parity is to ensure that each circle contains an even number of '1's.

The intersections show which parity checks include each data bit. For instance, data bit $D_4$ (at position 7) is inside all three circles, so it is checked by all three parity bits ($P_1, P_2, P_4$). This overlap lets the syndrome identify the exact location of a single-bit error.

Encoding and Error Correction Example

Step 1: Encoding a Message

We encode the 4-bit data word 1011. We use even parity, meaning each parity bit is set to '0' or '1' to make the total count of '1's in its group even.

1. Place data bits from left to right at positions 1 to 7: Data (D₁, D₂, D₃, D₄) is 1, 0, 1, 1.
   _ _ 1 _ 0 1 1
2. Calculate $P_1$ (checks 1,3,5,7): $P_1 \oplus D_1 \oplus D_2 \oplus D_4 = P_1 \oplus 1 \oplus 0 \oplus 1 = 0$. To make the sum even, $P_1$ must be 0.
   0 _ 1 _ 0 1 1
3. Calculate $P_2$ (checks 2,3,6,7): $P_2 \oplus D_1 \oplus D_3 \oplus D_4 = P_2 \oplus 1 \oplus 1 \oplus 1 = 0$. To make the sum even, $P_2$ must be 1.
   0 1 1 _ 0 1 1
4. Calculate $P_4$ (checks 4,5,6,7): $P_4 \oplus D_2 \oplus D_3 \oplus D_4 = P_4 \oplus 0 \oplus 1 \oplus 1 = 0$. To make the sum even, $P_4$ must be 0.
   0 1 1 0 0 1 1
5. Transmitted Codeword (positions 1 to 7 from left to right): 0110011

Step 2: Detecting and Correcting an Error

Suppose noise flips the bit at position 5 from '0' to '1' during transmission. The receiver gets the corrupted word 0110111.

The receiver performs the same parity checks on the received word:

• Check 1 (for $P_1$; positions 1,3,5,7): $0 \oplus 1 \oplus 1 \oplus 1 = 1$. The count of '1's is odd (3). Error detected. Syndrome bit S₁ = 1.
• Check 2 (for $P_2$; positions 2,3,6,7): $1 \oplus 1 \oplus 1 \oplus 1 = 0$. The count of '1's is even (4). Parity check passed. Syndrome bit S₂ = 0.
• Check 3 (for $P_4$; positions 4,5,6,7): $0 \oplus 1 \oplus 1 \oplus 1 = 1$. The count of '1's is odd (3). Error detected. Syndrome bit S₄ = 1.

We combine the syndrome bits with $S_4$ as the most significant bit and $S_1$ as the least significant bit, obtaining the binary number 101. In decimal, $101_2 = 4 + 0 + 1 = 5$. This is the error position in the codeword.

The syndrome identifies position 5 as the corrupted bit.

To correct the error, the receiver flips the bit at position 5 in the received word 0110111, which turns it back into the original, correct codeword: 0110011.