edited by
531 views
3 votes
3 votes

A manufacturer of Bio-Medical equipment company needs to deal with the problem of occasional random bit flips in opcodes due to radiation.


Which of the following statements is/are true?

  1.  The minimum Hamming distance required to detect d errors is d + 1.
  2.  The minimum Hamming distance required to correct d errors is  2 * d + 1.
  3.  The minimum Hamming distance required to prevent d errors is  3 * d + 1.
  1.   I only
  2.   I, II, and III
  3.   II and III only
  4.   I and II only
edited by

2 Answers

Best answer
4 votes
4 votes

The Hamming distance between two bit strings is the number of bits that would have to flip to make the strings identical.


Consider a single bit flip. This could turn 010 into 110 , for example. If both 010 and 110 are valid strings, then there is no way to detect that an error occurred when 110 is observed.

So strings must differ by at least 2 bits in order for 1 bit errors to be detectable. In general, to detect d errors requires a minimum Hamming distance of d + 1.

If both 001 and 100 are valid bit strings, but 101 is observed, how is the observer to know whether an 001 or a 100 which one to take ? In order to correct a 1 bit error, the minimum necessary Hamming distance is 3 bits.

for example, if only 111 and 000 are valid, but an 001 arrives, then the receiver can correct this to 000 under the assumption that only one bit flipped.

Correcting d bit flips requires a minimum Hamming distance of 2 * d + 1.

So , Statement I The minimum Hamming distance required to detect d errors is d + 1

is True .

Statement II The minimum Hamming distance required to correct d errors is  2 * d + 1. 

is True .

Statement III  The minimum Hamming distance required to prevent d errors is  3 * d + 1. 

is False because There is no way to prevent bit flips by adjusting the Hamming distance. 

Hence option D is correct .

selected by
Answer:

Related questions

1 votes
1 votes
2 answers
2
Pooja Khatri asked Jul 13, 2018
2,420 views
To guarantee correction of upto $t$ errors, the minimum Hamming distance $d_{min}$ in a block code must be ______$t+1$$t-2$$2t-1$$2t+1$
0 votes
0 votes
0 answers
4