Hamming Distance and Hamming Codes

---

1. Definition of Hamming Distance

The Hamming Distance between two words (binary sequences of equal length) $x$ and $y$, denoted as $d(x, y)$, is the number of bit positions in which the corresponding bits differ.

It is mathematically calculated by performing a bitwise Exclusive-OR (XOR) operation between the two words and counting the number of 1s in the result (the Hamming Weight $w$):

  x:       1  0  1  1  0  1
  y:       1  0  0  1  1  1
  --------------------------
  x ⊕ y:   0  0  1  0  1  0  ===> Count of 1s = 2
  Hamming Distance d(x, y) = 2

Minimum Hamming Distance ($d_{\min}$):

The Minimum Hamming Distance $d_{\min}$ of a code is the smallest Hamming distance between any pair of distinct valid codewords in the entire codebook:

(For linear block codes, $d_{\min}$ equals the minimum weight among all non-zero valid codewords).

---

2. Detection and Correction Capabilities

The error detection and correction capabilities of any block code are strictly bounded by its minimum Hamming distance $d_{\min}$:

  Error Detection (d_min >= s + 1)
  Valid C1                                            Valid C2
     O ------------------ Distance d_min ----------------- O
     |<--- s errors --->|
  (Corrupted word falls strictly into the invalid gap between codewords)

  Error Correction (d_min >= 2t + 1)
       Codeword 1               Invalid Zone               Codeword 2
     (     O     )        |                      |        (     O     )
     \__Radius t_/                                        \_Radius t__/
     (Spheres of radius t around valid codewords must NOT overlap)

A. Error Detection Condition

To detect up to $s$ bit errors, the minimum Hamming distance must satisfy:

• Example: To detect all single-bit errors ($s = 1$), we need $d_{\min} \geq 1 + 1 = 2$ (achieved by simple parity check).
• To detect all 2-bit errors ($s = 2$), we need $d_{\min} \geq 2 + 1 = 3$.

B. Error Correction Condition

To correct up to $t$ bit errors, the minimum Hamming distance must satisfy:

• Example: To correct any single-bit error ($t = 1$):

• If a single bit flips, the received word is at distance 1 from the original valid codeword and at least distance 2 from any other valid codeword, enabling unambiguous nearest-neighbor decoding.

---

3. The Hamming Code (Hamming Rule & Construction)

Richard Hamming designed an elegant single-error-correcting linear code.

Redundancy Bit Formula:

If an information message contains $m$ data bits and requires $r$ redundant parity bits, the total codeword length is $n = m + r$. The $r$ parity bits must distinguish between $n$ single-bit error locations and 1 error-free state ($n + 1$ total states):

Data Bits ($m$)	Redundant Bits ($r$)	Total Codeword Length ($n = m + r$)	Example Code
1	2	3	(3, 1) Triple Repetition
4	3	7	(7, 4) Hamming Code
11	4	15	(15, 11) Hamming Code
26	5	31	(31, 26) Hamming Code

---

4. Construction of the Hamming (7, 4) Code

A (7, 4) Hamming code carries $m = 4$ data bits ($D_7, D_6, D_5, D_3$) and $r = 3$ parity bits ($P_4, P_2, P_1$).

Bit Position Mapping:

Parity bits are placed strictly in bit positions that are powers of 2 ($1, 2, 4, 8, \dots$). All other positions hold data bits:

Bit Position	7	6	5	4	3	2	1
Binary Index	111	110	101	100	011	010	001
Role	$D_7$	$D_6$	$D_5$	$P_4$	$D_3$	$P_2$	$P_1$

Parity Check Bit Calculation (Even Parity):

Each parity bit checks all bit positions whose binary representation has a 1 in the parity bit's position:

• $P_1$ (checks positions with LSB 1: 1, 3, 5, 7):

• $P_2$ (checks positions with 2nd bit 1: 2, 3, 6, 7):

• $P_4$ (checks positions with 3rd bit 1: 4, 5, 6, 7):

---

5. Solved Step-by-Step Example

Step 1: Encoding at Sender

Let the 4-bit dataword be 1 0 1 1 ($D_7 = 1, D_6 = 0, D_5 = 1, D_3 = 1$).

• $P_1 = D_3 \oplus D_5 \oplus D_7 = 1 \oplus 1 \oplus 1 = 1$
• $P_2 = D_3 \oplus D_6 \oplus D_7 = 1 \oplus 0 \oplus 1 = 0$
• $P_4 = D_5 \oplus D_6 \oplus D_7 = 1 \oplus 0 \oplus 1 = 0$

Step 2: Error Injection during Transmission

Suppose bit 5 flips during transit ($b_5$ changes from 1 to 0):

Step 3: Syndrome Calculation at Receiver

Compute syndrome bits $(s_4, s_2, s_1)$ using even parity check:

• $s_1 = b_1 \oplus b_3 \oplus b_5 \oplus b_7 = 1 \oplus 1 \oplus 0 \oplus 1 = \mathbf{1}$
• $s_2 = b_2 \oplus b_3 \oplus b_6 \oplus b_7 = 0 \oplus 1 \oplus 0 \oplus 1 = \mathbf{0}$
• $s_4 = b_4 \oplus b_5 \oplus b_6 \oplus b_7 = 0 \oplus 0 \oplus 0 \oplus 1 = \mathbf{1}$

The syndrome decimal value $5$ identifies Bit 5 as the erroneous bit! The receiver flips bit 5 back from 0 to 1, completely correcting the error.

---

6. Key Exam Questions & Takeaways

1. State the relationship between $d_{\min}$ and error detection/correction.
   • Detection: $d_{\min} \geq s + 1$.
   • Correction: $d_{\min} \geq 2t + 1$.
2. If a code has $d_{\min} = 5$, what are its maximum error detection and correction capabilities?
   • Max detection: $s = d_{\min} - 1 = 5 - 1 = 4$ bit errors.
   • Max correction: $t = \lfloor \frac{d_{\min} - 1}{2} \rfloor = \lfloor \frac{4}{2} \rfloor = 2$ bit errors.
3. What is the Hamming inequality for calculating parity bits?
   • $2^r \geq m + r + 1$, where $m$ is the number of data bits and $r$ is the number of parity bits.
4. How does the syndrome locate the error in a Hamming code?
   • When parity check equations are evaluated, the resulting syndrome binary bits $[s_k \dots s_1]_2$ directly form the 1-based decimal index of the corrupted bit. If syndrome is 0, no error occurred.