How Do Hamming Codes Correct and Detect Bit Errors?

Hamming codes are a family of linear error-correcting codes that use overlapping parity bits to locate and fix single-bit errors in binary data. By placing parity bits at positions that are powers of two, each data bit is covered by a unique combination of parity checks. When a single bit flips during transmission or storage, the pattern of failed parity checks directly spells out the binary address of the corrupted bit. Adding one extra overall parity bit extends this scheme to detect double-bit errors as well.

Placement of Parity and Data Bits

In a standard Hamming code, bit positions are numbered starting from \(1\) rather than \(0\). Every position that is a power of two (\(1, 2, 4, 8, \dots, 2^k\)) is reserved for a parity bit, while all remaining positions hold the original data bits.

For example, in a \((7, 4)\) Hamming code, there are \(7\) total bits: \(4\) data bits and \(3\) parity bits. The positions are assigned as follows:

  • Position \(1\) (\(001_2\)): Parity bit \(p_1\)
  • Position \(2\) (\(010_2\)): Parity bit \(p_2\)
  • Position \(3\) (\(011_2\)): Data bit \(d_1\)
  • Position \(4\) (\(100_2\)): Parity bit \(p_4\)
  • Position \(5\) (\(101_2\)): Data bit \(d_2\)
  • Position \(6\) (\(110_2\)): Data bit \(d_3\)
  • Position \(7\) (\(111_2\)): Data bit \(d_4\)

In general, \(r\) parity bits can cover up to \(2^r - 1\) total bit positions, leaving \(2^r - r - 1\) positions for data.

How Overlapping Parity Checks Work

Each parity bit checks a specific subset of positions based on the binary representation of the position numbers. A parity bit at position \(2^k\) checks all bit positions whose binary representation has a \(1\) in the \(k\)-th bit (counting from the least significant bit, starting at \(0\)).

Using even parity, each parity bit is set so that the total number of \(1\)s in its covered positions is even:

  • \(p_1\) (position \(1 = 001_2\)) checks positions with bit \(0\) set: \(1, 3, 5, 7\). Thus, \(p_1 = d_1 \oplus d_2 \oplus d_4\).
  • \(p_2\) (position \(2 = 010_2\)) checks positions with bit \(1\) set: \(2, 3, 6, 7\). Thus, \(p_2 = d_1 \oplus d_3 \oplus d_4\).
  • \(p_4\) (position \(4 = 100_2\)) checks positions with bit \(2\) set: \(4, 5, 6, 7\). Thus, \(p_4 = d_2 \oplus d_3 \oplus d_4\).

Because every data bit position has a unique binary representation with at least two \(1\)s, each data bit is included in a distinct combination of parity checks.

Correcting Single-Bit Errors with the Syndrome

When a \(7\)-bit codeword is received, the receiver recalculates the parity for each group. This produces a \(3\)-bit binary number called the syndrome, \(S = (s_4, s_2, s_1)\), where:

\[s_1 = p_1 \oplus d_1 \oplus d_2 \oplus d_4\] \[s_2 = p_2 \oplus d_1 \oplus d_3 \oplus d_4\] \[s_4 = p_4 \oplus d_2 \oplus d_3 \oplus d_4\]

If no errors occurred, every parity check passes and \(S = 000_2\). If a single bit flips, the syndrome is nonzero, and its binary value equals the exact position of the erroneous bit.

For instance, if data bit \(d_3\) at position \(6\) (\(110_2\)) flips, both \(s_2\) and \(s_4\) will fail while \(s_1\) passes. The resulting syndrome is \(S = 110_2 = 6\), identifying position \(6\) so the receiver can flip that bit back to its original value.

Extending to Double-Bit Error Detection

A standard Hamming code has a minimum Hamming distance of \(d_{\min} = 3\), meaning any two valid codewords differ in at least \(3\) bit positions. While this allows single-bit error correction, a double-bit error produces a nonzero syndrome that looks identical to a single-bit error at a different position, leading to an incorrect fix.

To achieve Single Error Correction, Double Error Detection (SECDED), an extra overall parity bit \(p_0\) is added, typically at position \(0\). This bit covers all other bits in the codeword, increasing the minimum Hamming distance to \(d_{\min} = 4\).

The receiver evaluates both the syndrome \(S\) and the overall parity \(P_{\text{all}}\):

  • \(S = 0\) and \(P_{\text{all}} = 0\): No error occurred.
  • \(S \neq 0\) and \(P_{\text{all}} = 1\): A single-bit error occurred at the position given by \(S\), which can be corrected.
  • \(S = 0\) and \(P_{\text{all}} = 1\): A single-bit error occurred in the overall parity bit \(p_0\) itself.
  • \(S \neq 0\) and \(P_{\text{all}} = 0\): A double-bit error occurred. Two bit flips cancel out in the overall parity check, leaving \(P_{\text{all}} = 0\), while still triggering a nonzero syndrome.

When a double-bit error is detected, the system knows the data cannot be safely repaired and can trigger a memory fault or request a retransmission.