edited by
25,756 views
39 votes
39 votes

An error correcting code has the following code words: $00000000, 00001111, 01010101, 10101010, 11110000$. What is the maximum number of bit errors that can be corrected?

  1. $0$
  2. $1$
  3. $2$
  4. $3$
edited by

7 Answers

3 votes
3 votes

Hamming distance measures the minimum number of substitutions required to change one string into the other, or the minimum number of errors that could have transformed one string into the other. It is also known as edit distance between two strings.

For binary strings $a$ and $b$ the Hamming distance is equal to the number of ones in $a \oplus b$.

Lets consider a code $C$ and minimum hamming distance between any of its codewords be $\lambda$.

1. A code $C$ is said to be $k$ errors detecting iff $ \lambda\geq k+1 $.

It can detect error upto edit distance of $k$.

$$k\leq\lambda-1$$

So this code can detect an error of at most $\lambda-1$ edit distance.

2. A code $C$ is said to be $k$ errors correcting iff $ \lambda\geq 2k+1 $.

It can correct error upto edit distance of $k$.

$$k\leq \lfloor\frac{\lambda-1}{2}\rfloor$$

So this code can correct an error of at most $\lfloor\frac{\lambda-1}{2}\rfloor$ edit distance.

Now coming back to the question, here $\lambda = 4$

Thus we can detect maximum error of $4-1=3$ bits.

And can correct maximum error of $\lfloor\frac{4-1}{2}\rfloor=1$ bit.

source: Error_detection_and_error_correction

edited by
0 votes
0 votes
If we xor 01010101 and 10101010 bitwise we get hamming distance as 8 and so

If we want to correct i errors

2i+1=8

  i=3 so 3 bits can be corrected

And to detect i errors

 i+1 =8

 i=7  so 7 bits of error can be detected

So answer should be d)
Answer:

Related questions