edited by
25,517 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

Best answer
61 votes
61 votes

Answer: B

For correction:$\left\lfloor \dfrac{(\text{Hamming Distance} - 1)}{2}\right\rfloor$

$=\big\lfloor1.5\big\rfloor=1\text{ bit error}$.

For detection:$\text{ Hamming Distance - 1 = 3 bit error}$.

edited by
27 votes
27 votes

Option b)

a. 00000000

b. 00001111

c. 01010101

d. 10101010

e. 11110000 

Hamming Distance
  a b c d e
a 0 4 4 4 4
b   0 4 4 8
c     0 8 4
d       0 4
e         0

Hamming Dist = 4

=> 2.d + 1 = 4

=> d = 3/2

=> d = 1 (ans)

PS: For a set of codewords we always take the minimum hamming distance and not maximum. So here min. hamming dist. = 4

edited by
10 votes
10 votes
Answer is (B)

detection possible up to ( hamming distance - 1) = 4 - 1 = 3 bits

correction possible up to { floor of [ ( hamming distance - 1) / 2 ]}

                                      = { floor of [( 4 - 1 ) / 2] }

                                      = floor of (3 / 2)

                                      = floor (1.5)

                                      = 1 bit
7 votes
7 votes

Hamming distance here is 00000000 xor 00001111 which is equal to 4.

To correct b bit error minimum hamming distance required >=2*b+1.

Therefore 4 >= 2*b+1 which satisfies for b=1.

Therefore 1 bit error correction is possible.

Answer:

Related questions