In digital communication and data storage, maintaining data integrity is crucial. Noise, interference, and hardware defects can flip a bit (0 to 1, or 1 to 0), causing a single-bit error. Hamming codes are a family of linear error-correcting codes designed to effectively detect and correct these single-bit errors.

The Hamming (n, k) Principle

A Hamming code is denoted as (n, k), where:

• n: The total number of bits in the codeword (the encoded message).
• k: The number of data bits being encoded.
• m = n - k: The number of parity bits (or check bits) added.

The general relationship is determined by the number of parity bits, m, and must satisfy the condition: 2^m ≥ n + 1. This ensures there are enough parity bit combinations to identify the location of any single-bit error, or confirm no error occurred.

Structure of Hamming (15, 11)

The Hamming (15, 11) code is a powerful instance where:

• Total bits (n): 15
• Data bits (k): 11 (the original information)
• Parity bits (m): 15 - 11 = 4

For m=4 parity bits, the requirement 2⁴ ≥ 15 + 1 is satisfied, since 16 ≥ 16. This allows the code to uniquely identify one of the 15 possible bit positions that could be in error, plus the one position indicating no error (total 16 states).

Positioning of Parity Bits

The 4 parity bits (P₁, P₂, P₃, P₄) are placed at the positions corresponding to powers of 2 (1, 2, 4, 8) within the 15-bit codeword. The remaining 11 positions are used for the data bits (D₁ through D₁₁):

The Parity Calculation and Error Correction

Each parity bit is calculated based on the XOR sum of a specific set of data bits. A bit is covered by a parity check if its position number has a '1' in the binary representation corresponding to that parity position.

Parity Set Coverage (Example)

The P₁ bit (position 1 = 0001₂) checks all positions where the least significant bit is 1:

• P₁ checks: 1, 3, 5, 7, 9, 11, 13, 15
• P₂ checks: 2, 3, 6, 7, 10, 11, 14, 15
• P₃ checks: 4, 5, 6, 7, 12, 13, 14, 15
• P₄ checks: 8, 9, 10, 11, 12, 13, 14, 15

Syndrome Calculation

At the receiver, the parity check is re-calculated. The result of these four checks forms a 4-bit value called the syndrome. If the syndrome is 0000, there is no error. If the syndrome is non-zero, its binary value directly corresponds to the position of the bit in error (from 1 to 15).

This self-locating error property makes Hamming codes a highly efficient single-bit error correction mechanism foundational to memory ECC (Error-Correcting Code) and reliable data transmission protocols.