Generate Hamming code for a 4-bit Excess-3 message to detect and correct single bit errors.
Answers
Hamming code is a set of error-correction codes that can be used to detect and correct the errors that can occur when the data is moved or stored from the sender to the receiver.
Hamming code can be generated using ‘even parity’ or ‘odd parity’.
A detailed explanation of generating a Hamming code is given below.
Given that;
To generate Hamming code for a 4-bit excess 3 code.
An excess 3 code is nothing but the adding of a binary 3 to the binary code.
Decimal Binary code(BCD) Excess-3 code
8 4 2 1 BCD + 011
0 0 0 0 0 0 0 1 1
0 0 0 0
+
0 0 1 1
———————-
0 0 1 1
———————-
1 0 0 0 1 0 1 0 0
2 0 0 1 0 0 1 0 1
3 0 0 1 1 0 1 1 0
4 0 1 0 0 0 1 1 1
5 0 1 0 1 1 0 0 0
6 0 1 1 0 .
7 0 1 1 1 .
. . .
. . .
Picking a 4-bit excess 3 code message;
Let the message m = (0 1 0 1)
Generating a Hamming code (using even parity):
Message (m) = (0 1 0 1)
To determine the parity bits:
2^P > or = P+m+1
Here m = 4 (Given it is 4-bit message)
Let P = 1
2^1 > or = 1+4+1 ? No
Let P = 2
2^2 > or = 2+4+1 ? No
Let P = 3
2^3 > or = 3+4+1 ? Yes
So, the number of parity bits = 3 (P1, P2, P3)
Hence, the Hamming code consists of m+P = 4+3 = 7 bits
Hamming code:
1 2 3 4 5 6 7
P1 P2 m1 P3 m2 m3 m4
P1 P2 0 P3 1 0 1
Parity bits lie in the power of 2 positions (2^0, 2^1, …..)
We simply fill the message bits in the remaining positions.
Finding the parity bits (using even parity):
P1 —> 1 3 5 7 —> P1 0 1 1 => P1 = 0
Explanation:
P1 is the first parity bit.
We need to pick the bits from the positions 1 3 5 7. This is because these digits in binary format contain a 1 in the 1st position.
1. 0 0 0 1
3. 0 0 1 1
5. 0 1 0 1
7. 0 1 1 1
So we get, (P1 0 1 1).
Since, we are considering even parity, P1 = 0, so that there are even number of 1’s.
Similarly, we determine other values of P
P2 —> 2 3 6 7 —> P2 0 0 1 => P2 = 1
[2, 3, 6, 7 contain a 1 in the 2nd position]
P3 —> 4 5 6 7 —> P3 1 0 1 => P3 = 0
[4, 5, 6, 7 contain a 1 in the 3rd position]
Now, we have the parity bits and the message bits.
The generated hamming code is;
(P1 P2 m1 P3 m2 m3 m4)
0 1 0 0 1 0 1