What is the relationship between the distance between parity bits and their…

In Hamming Code, the "distance" between parity bits—and more importantly, the Hamming distance between valid code words—directly determines how many errors the code can detect and correct.

Here is the breakdown of the relationship between parity bit placement, distance, and error capability.

1. Parity Bit Placement (2n Positions)

In a Hamming code word, parity bits are placed at positions that are powers of 2 (Positions 1, 2, 4, 8, 16, etc.).

This specific geometric/binary spacing ensures that every data bit is covered by a unique combination of parity bits.

• Position 1 (20) checks bits 1, 3, 5, 7, 9, 11... (binary positions ending in ...1)

• Position 2 (21) checks bits 2, 3, 6, 7, 10, 11... (binary positions with a 1 in the tens place)

• Position 4 (22) checks bits 4, 5, 6, 7, 12, 13...

Because of this strategic distance and overlap, when an error occurs, the combination of failing parity bits (called the Syndrome) points directly to the exact binary index of the corrupted bit.

2. Hamming Distance vs. Error Capability

The fundamental metric governing error handling is the Minimum Hamming Distance (d min), which is the minimum number of bit positions in which any two valid code words differ.

The mathematical relationship between distance (d min), detection (t detect), and correction (t correct ) is defined by two strict rules:

A. For Error Detection

To reliably detect up to $t$ errors, the minimum distance must be:

d min > t + 1

• Why? If the distance between two valid code words is $d_{min}$, changing fewer than d min , bits will result in an invalid code word, which the system immediately flags as an error.

B. For Error Correction

To reliably correct up to t errors, the minimum distance must be:

d min > 2 t + 1

• Why? If an error alters t bits, the corrupted code word will still be closer to its original valid code word than to any other valid code word in the system, allowing the receiver to map it back to the correct original value.

3. Standard Hamming Code Configurations

Standard Hamming Code is designed with a Minimum Hamming Distance (d min ) of 3. Using the formulas above, we can see its exact capabilities:

• Detection Capability: 3 >t + 1 => t = 2 (Can detect up to 2-bit errors)

• Correction Capability: 3 >2t + 1 => t = 1(Can correct only 1-bit errors)

Therefore, standard Hamming Code is classified as a Single Error Correction (SEC) code.

Hamming Code Formula

For:

• m data bits

• r parity bits

Condition: 2r≥m+r+1

In short: Increasing the distance between valid states (by adding more strategically spaced parity bits) creates a larger "safety buffer." This buffer prevents corrupted data from mimicking other valid data, thereby scaling up both detection and correction thresholds.

In Hamming Code, the ability to detect and correct errors depends on the Minimum Hamming Distance between valid code words.