How Hamming Codes Detect and Correct Single-Bit Errors

This article explains the mathematical mechanics behind Hamming codes, a foundational method for error detection and correction in digital communications. It covers the fundamental concept of parity bits, how these bits are strategically positioned within a data block using powers of two, and the modulo-2 arithmetic used to construct a transmitted codeword. Finally, it demonstrates how a receiver uses overlapping parity checks and linear algebra to generate an error syndrome, which pinpoints the exact binary location of a corrupted bit so it can be inverted back to its original state.

The Foundation: Parity Bits and Modulo-2 Arithmetic

At the core of Hamming codes is the concept of parity. A parity bit is an extra bit added to a string of binary data to ensure the total number of 1s is either even (even parity) or odd (odd parity).

In coding mathematics, parity is calculated using arithmetic over the Galois Field of two elements, denoted as \(GF(2)\), which is equivalent to modulo-2 addition or the Exclusive OR (XOR) logic operation. In this system:

  • \(0 \oplus 0 = 0\)
  • \(0 \oplus 1 = 1\)
  • \(1 \oplus 0 = 1\)
  • \(1 \oplus 1 = 0\)

While a single parity bit can detect if a single-bit error has occurred (because the total count of 1s changes from even to odd), it cannot correct the error because it does not indicate which bit was flipped. Hamming codes solve this by using multiple, overlapping parity bits.

Bit Positioning via Powers of Two

To pinpoint the location of an error, Hamming codes interleave parity bits and data bits in a specific mathematical sequence.

In any Hamming code, bit positions that are powers of two (\(2^0, 2^1, 2^2, 2^3\), etc., which correspond to positions 1, 2, 4, 8, etc.) are reserved exclusively for parity bits. All other positions (3, 5, 6, 7, 9, 10, etc.) are filled with the actual data bits.

The most common baseline example is the Hamming(7,4) code, which encodes 4 bits of data into a 7-bit codeword by adding 3 parity bits. The structure looks like this:

  • Position 1 (\(2^0\)): Parity bit 1 (\(P_1\))
  • Position 2 (\(2^1\)): Parity bit 2 (\(P_2\))
  • Position 3: Data bit 1 (\(D_1\))
  • Position 4 (\(2^2\)): Parity bit 3 (\(P_3\))
  • Position 5: Data bit 2 (\(D_2\))
  • Position 6: Data bit 3 (\(D_3\))
  • Position 7: Data bit 4 (\(D_4\))

The Mathematics of Overlapping Parity Checks

The power of the Hamming code lies in how each parity bit is assigned to check specific data bits. This assignment is based on the binary representation of the bit positions:

  • Position 1 in binary is \(001_2\)
  • Position 2 in binary is \(010_2\)
  • Position 3 in binary is \(011_2\)
  • Position 4 in binary is \(100_2\)
  • Position 5 in binary is \(101_2\)
  • Position 6 in binary is \(110_2\)
  • Position 7 in binary is \(111_2\)

Each parity bit covers all bit positions whose binary representation has a \(1\) in the same place as the parity bit's own binary representation:

  1. \(P_1\) (Position \(001_2\)) checks all positions ending in \(1\): Positions 1, 3, 5, 7.
  2. \(P_2\) (Position \(010_2\)) checks all positions with a \(1\) in the middle bit: Positions 2, 3, 6, 7.
  3. \(P_3\) (Position \(100_2\)) checks all positions with a \(1\) in the leftmost bit: Positions 4, 5, 6, 7.

Notice that every data bit is covered by a unique combination of at least two parity bits. For example, Position 6 (\(110_2\)) is checked by \(P_3\) (\(100_2\)) and \(P_2\) (\(010_2\)), because \(4 + 2 = 6\).

Step-by-Step Encoding Example

Suppose we want to transmit the 4-bit data sequence 1011 using even parity.

  1. Place the data bits into their non-power-of-two positions:
    • Position 3 (\(D_1\)) = 1
    • Position 5 (\(D_2\)) = 0
    • Position 6 (\(D_3\)) = 1
    • Position 7 (\(D_4\)) = 1
  2. Calculate the parity bits using XOR (\(\oplus\)) on their respective covered data positions:
    • \(P_1\) checks 3, 5, 7: \(D_1 \oplus D_2 \oplus D_4 = 1 \oplus 0 \oplus 1 = 0\). So, \(P_1 = 0\).
    • \(P_2\) checks 3, 6, 7: \(D_1 \oplus D_3 \oplus D_4 = 1 \oplus 1 \oplus 1 = 1\). So, \(P_2 = 1\).
    • \(P_3\) checks 5, 6, 7: \(D_2 \oplus D_3 \oplus D_4 = 0 \oplus 1 \oplus 1 = 0\). So, \(P_3 = 0\).
  3. Assemble the complete 7-bit codeword (Positions 1 through 7): 0110011.

Error Detection and Correction: The Syndrome

Now, assume the codeword 0110011 is transmitted, and noise causes a single-bit error at Position 6, flipping it from a 1 to a 0. The receiver gets the corrupted word: 0110001.

To detect and correct the error, the receiver recalculates the parity for each group, including the parity bit itself. Using even parity, the XOR sum of each group should equal 0. The results of these checks form a binary number called the syndrome (\(S = C_3 C_2 C_1\)).

  1. Check 1 (\(C_1\)) on positions 1, 3, 5, 7: \(0 \oplus 1 \oplus 0 \oplus 1 = 0\). (Pass, \(C_1 = 0\))
  2. Check 2 (\(C_2\)) on positions 2, 3, 6, 7: \(1 \oplus 1 \oplus 0 \oplus 1 = 1\). (Fail, \(C_2 = 1\))
  3. Check 3 (\(C_3\)) on positions 4, 5, 6, 7: \(0 \oplus 0 \oplus 0 \oplus 1 = 1\). (Fail, \(C_3 = 1\))

Next, the receiver writes the check results in order from most significant bit to least significant bit (\(C_3 C_2 C_1\)):

\[\text{Syndrome} = 110_2\]

Converting the binary syndrome \(110_2\) to decimal yields 6.

Because the parity bits were positioned at powers of two, the syndrome directly outputs the exact position of the corrupted bit. The receiver simply locates Position 6 in the received codeword (0110001), flips the 0 back to a 1, restoring the correct codeword (0110011), and extracts the original data bits from positions 3, 5, 6, and 7 (1011).

Linear Algebra Representation

In advanced coding theory, this entire process is executed using matrix multiplication over \(GF(2)\).

For a Hamming(7,4) code, the parity check relationships are defined by a Parity-Check Matrix (\(H\)), where each column is the binary representation of the bit position:

\[H = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{pmatrix}\]

When a codeword vector \(r\) is received, the receiver calculates the syndrome vector \(s\) by multiplying the matrix \(H\) by the transpose of \(r\):

\[s = H \cdot r^T \pmod 2\]

If \(s\) is a zero vector \(\begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}\), no error occurred. If a single-bit error occurred, the resulting vector \(s\) will match the exact column in \(H\) corresponding to the corrupted bit's position, mathematically automating the detection and correction process.