3-bit Error Correction:
So, to correct the 3-bit error the minimum distance between two valid codes is at least 7.
Important note:
So, for n bit error correction the minimum hamming distance between two valid codes is ≥ 2n + 1.
# Because to detect (1 bit) error we maintain the hamming distance of two valid code should be at least (≥ 2) two.
So, small numbers of bits we can’t represent valid pattern as well.
Explain it by an example
Let us use BCD as a valid pattern. So, we have a 0 – 15 – pattern by this 0 – 15 we can represent (0 – 9) BCD code.
# Now if we take 0000 (0) as a valid pattern, then all code with distance 1 from 0000 is invalid.
Then (1, 2, 4, 8) invalid.
Again if 3 (0011) select as a valid code, then all code unit distance for 3 is invalid.
Like 3 – 0011
So, Invalid
1011
0111
0001
0010
# Same way if take 5 as valid code, then invalid code will be
# So, seven (7) code are invalid then we can’t represent (0 – 9) BCD code.
# What should we do, we can increase the number of patterns by increasing the number of bits instead of n bit (15 combinations) here we should use more bits for the large pattern.
# Now how we increase the hamming distance of codes to make it a valid code for error detection.
The right example is gray code as we know in gay code hamming distance between every code is a unit (1).
Now we should increase the distance between gray codes to make it valid for error detecting.
For 1-bit error detection, we should increase the hamming distance of gray code at least 2.
It can be done by adding a parity bit.
Example:
Here we use even parity. And parity bit to gray code to make it even parity (number of 1’s is even).
# Distance between two valid codes is 2 now.
Now it can be used as 1-bit error detection.
# So, there is more method to increase the distance of two valid bit for error detection as well as error correction, it depends on your requirement.
But most of the time 1-bit errors have come as errors. So, the most common is 1-bit error correction.
Q: UGC NET 2009
In order that a code is ‘t’ error-correcting, the minimum hamming distance should be
a) t
b) 2t – 1
c) 2t
d) 2t + 1
Solution:
Option (d) is the correct answer.
Explanation:
Important note:
So, for n bit error correction the minimum hamming distance between two valid codes is ≥ 2n + 1.
# Because to detect (1 bit) error we maintain the hamming distance of two valid code should be at least (≥ 2) two.
For a more detailed explanation please see the above Error Correction (3 bit).