Hamming Distance and Hamming Codes

Q: State the relationship between $d_{\min}$ and error detection/correction.

- Detection: d_{\min} \geq s + 1. - Correction: d_{\min} \geq 2t + 1.

Q: 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.

Q: 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.

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$ ):

d(x, y) = w(x \oplus y)

SVGVector Architecture Diagram (SVG)

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:

d_{\min} = \min \{ d(C_i, C_j) \mid C_i eq C_j \}

(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}$ :

MermaidDiagram

Rendering diagram…

MermaidDiagram

Rendering diagram…

A. Error Detection Condition

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

d_{\min} \geq s + 1

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:

d_{\min} \geq 2t + 1

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

d_{\min} \geq 2(1) + 1 = 3

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):

2^r \geq m + r + 1

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_1 = D_3 \oplus D_5 \oplus D_7

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

P_2 = D_3 \oplus D_6 \oplus D_7

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

P_4 = D_5 \oplus D_6 \oplus D_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$

\text{Transmitted 7-bit Codeword } [b_7 b_6 b_5 b_4 b_3 b_2 b_1] = \mathbf{1\ 0\ 1\ 0\ 1\ 0\ 1}

Step 2: Error Injection during Transmission

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

\text{Received Word } = \mathbf{1\ 0\ 0\ 0\ 1\ 0\ 1}

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}$

\text{Syndrome Vector } S = [s_4\ s_2\ s_1] = [1\ 0\ 1]_2 = \mathbf{5}_{10}

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.

Frequently Asked Questions

QState the relationship between $d_{\min}$ and error detection/correction.

Detection: $d_{\min} \geq s + 1$ .
Correction: $d_{\min} \geq 2t + 1$ .

QIf 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.

QWhat 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.

QHow 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.

QWhere are the parity bits placed in a Hamming code?

At bit positions that are powers of 2 (1, 2, 4, 8, ...). All other positions hold data bits, and each parity bit checks the positions whose binary index has a 1 in that parity bit's place.

Hamming Distance