Hamming Code is an error-detecting and error-correcting code used to detect and correct errors
in transmitted data. It was developed by Richard W. Hamming in 1950. The basic idea is to add
parity bits to the data, allowing the receiver to detect and possibly correct errors in the data.
Steps to Calculate Hamming Code (Error Detection & Correction):
1. Identify the positions of the parity bits: The positions of the parity bits are powers of 2
(1, 2, 4, 8, etc.). These are denoted by p1,p2,p3,…p_1, p_2, p_3, \dots.
2. Set the parity bits: The value of each parity bit is calculated in such a way that the
number of 1s in the positions that it checks is even (or odd, depending on the
convention).
3. Determine the data bits: After placing the parity bits, the rest of the positions are filled
with the data bits.
4. Error detection: After receiving the data, the receiver checks the parity of each bit. If
any of the parity checks fail, the position of the error is determined by the binary sum
(syndrome vector) of all the failing parity checks. This helps in locating and correcting
the error.
Example:
Let's consider an example where we have a 4-bit data word: 1011. We need to generate a 7-bit
Hamming code to protect this data.
Step 1: Position the parity bits.
We have 4 data bits, and we need 3 parity bits to create a 7-bit code.
Parity bits will be placed in positions: 1, 2, and 4 (because they are powers of 2).
So the 7-bit code structure will be:
p1 p2 d1 p3 d2 d3 d4
Where:
p1p1 is the first parity bit (position 1),
p2p2 is the second parity bit (position 2),
p3p3 is the third parity bit (position 4),
d1,d2,d3,d4d1, d2, d3, d4 are the data bits.
Step 2: Set the parity bits.
The parity bit calculations are based on the following:
p1 covers bits 1, 3, 5, and 7.
p2 covers bits 2, 3, 6, and 7.
p3 covers bits 4, 5, 6, and 7.
We will set the parity bits such that the number of 1s in each group is even.
For p1:
p1 checks bits 1, 3, 5, and 7 (positions 1, 3, 5, 7).
Data bits are d1 = 1, d2 = 0, d3 = 1, d4 = 1 (we use placeholders for p1, p2, p3).
p1 checks the following positions: 1 (p1), 3 (d1 = 1), 5 (d2 = 0), 7 (d4 = 1).
To make the number of 1s even, p1 should be set to 0 because there are 2 ones (even number).
For p2:
p2 checks bits 2, 3, 6, and 7 (positions 2, 3, 6, 7).
p2 checks positions: 2 (p2), 3 (d1 = 1), 6 (d3 = 1), 7 (d4 = 1).
To make the number of 1s even, p2 should be set to 1 because there are 3 ones (odd
number).
For p3:
p3 checks bits 4, 5, 6, and 7 (positions 4, 5, 6, 7).
p3 checks positions: 4 (p3), 5 (d2 = 0), 6 (d3 = 1), 7 (d4 = 1).
To make the number of 1s even, p3 should be set to 0 because there are 2 ones (even
number).
Step 3: Construct the final Hamming code.
Now that we know the values of the parity bits, we can fill in the Hamming code.
The 7-bit Hamming code is:
p1 p2 d1 p3 d2 d3 d4
0 1 1 0 0 1 1
So the final Hamming code (7 bits) for the data 1011 is 0110011.
Step 4: Error Detection & Correction.
Now, let's simulate the transmission of this code and see how errors can be detected and
corrected. Suppose the transmitted code is 0110111, which is the same as the original code
except for the last bit (position 7).
To detect and correct the error:
1. The receiver calculates the parity bits using the same method as before.
For each parity bit, it checks the bits it covers and calculates if the number of 1s is even
or odd.
2. If a parity bit does not match the expected value (even or odd), it means there is an error
in the corresponding position.
For example:
p1 checks positions 1, 3, 5, 7 (i.e., 0, 1, 0, 1 in the received code). This gives an odd
number of 1s, so p1 detects an error.
p2 checks positions 2, 3, 6, 7 (i.e., 1, 1, 1, 1). This gives an even number of 1s, so p2 is
correct.
p3 checks positions 4, 5, 6, 7 (i.e., 0, 0, 1, 1). This gives an even number of 1s, so p3 is
correct.
From the error detection, the receiver knows the error is at position 7. It can then flip the 7th bit
from 1 to 0 to correct the error.
Conclusion:
In this example, the Hamming code allowed the receiver to detect that there was an error at bit
position 7 and correct it. This error detection and correction capability is the strength of the
Hamming code!
