UPPALA VIJAY KUMAR (Phd)

 

Example of Hamming Code Encoding and Decoding

Data Message

Let's encode the 4-bit data message 1011.

1. Encoding the Message

Step 1: Calculate the Number of Redundant Bits

We need to satisfy the condition:

$2^r \geq m + r + 1$

where $m$ is the number of data bits (4), and $r$ is the number of redundant bits.

Calculate $r$:

$r$	$2^r$	$m + r + 1$	Condition $2^r \geq m + r + 1$
1	2	6	False
2	4	7	False
3	8	8	True

Thus, we need 3 redundant bits.

Step 2: Position the Redundant Bits

The 4-bit data message 1011 will be placed into a 7-bit frame (including redundant bits). The redundant bits will be placed at positions 1, 2, and 4. The data bits will be placed in the remaining positions:

r1  r2  d1  r3  d2  d3  d4

So:

Position	Bit Value
1	$r_1$
2	$r_2$
3	Data bit 1 (1)
4	$r_3$
5	Data bit 2 (0)
6	Data bit 3 (1)
7	Data bit 4 (1)

The message to be encoded is:

_  _  1  _  0  1  1

Step 3: Calculate the Redundant Bits

Each redundant bit $r_i$ covers positions whose binary representation includes a 1 in the i-th position:

• Calculate $r_1$: Covers positions 1, 3, 5, 7

  Check bits at these positions (excluding $r_1$):

  Position	Bit Value
  3	1
  5	0
  7	1

  Calculate Parity:

  $\text{Parity} = 1 + 0 + 1 = 2 \text{ (even)}, \text{ so } r_1 = 0$

• Calculate $r_2$: Covers positions 2, 3, 6, 7

  Check bits at these positions (excluding $r_2$):

  Position	Bit Value
  3	1
  6	1
  7	1

  Calculate Parity:

  $\text{Parity} = 1 + 1 + 1 = 3 \text{ (odd)}, \text{ so } r_2 = 1$

• Calculate $r_3$: Covers positions 4, 5, 6, 7

  Check bits at these positions (excluding $r_3$):

  Position	Bit Value
  5	0
  6	1
  7	1

  Calculate Parity:

  $\text{Parity} = 0 + 1 + 1 = 2 \text{ (even)}, \text{ so } r_3 = 0$

Encoded Message:

0 1 1 0 0 1 1

2. Decoding the Message

Assume the received message is 0110011. We need to check for errors.

Step 1: Recalculate the Redundant Bits

Calculate parity for the received message to find errors:

• Recalculate $r_1$: Covers positions 1, 3, 5, 7

  Check bits at these positions:

  Position	Bit Value
  3	1
  5	0
  7	1

  Calculate Parity:

  $\text{Parity} = 1 + 0 + 1 = 2 \text{ (even)}, \text{ so } c_1 = 0$

• Recalculate $r_2$: Covers positions 2, 3, 6, 7

  Check bits at these positions:

  Position	Bit Value
  3	1
  6	1
  7	1

  Calculate Parity:

  $\text{Parity} = 1 + 1 + 1 = 3 \text{ (odd)}, \text{ so } c_2 = 1$

• Recalculate $r_3$: Covers positions 4, 5, 6, 7

  Check bits at these positions:

  Position	Bit Value
  5	0
  6	1
  7	1

  Calculate Parity:

  $\text{Parity} = 0 + 1 + 1 = 2 \text{ (even)}, \text{ so } c_3 = 0$

Step 2: Determine Error Position

The recalculated parity bits are 010. This binary value corresponds to decimal 2, indicating an error at position 2.

Correct the Error

If the bit at position 2 is flipped, the corrected message becomes:

Original: 0110011

Corrected: 0010011

Extract the Data Bits

Remove the redundant bits:

The corrected message without redundant bits:

1 0 1 1

Final Message:

The original data message 1011 is correctly recovered.