FOR FREE YEAR SOLVED

Error Correction (3 bit):

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