ISRO-2013-18

Question

How many check bits are required for $16$ bit data word to detect $2$ bit errors and single bit correction using hamming code?

• A. $5$
• B. $6$
• C. $7$
• D. $8$

Answer 1

I dont know the reason behind this, but I have read from the PDF downloaded from NPTEL Website that for detecting d bit error, we need d+1 bits and for correcting d bit error we need 2d+1 bits

In our example, we have to detect 2 bit errors. So for this 2+1 = 3 bits are required

For correcting 1 bit error 2*1+1=3 bits are required..

So in total 6 bits are required to correct 1 bit error and detect 2 bit error..

 

I will be grateful if anyone can provide explanation behind the formulas 2d+1 and d+1

 

Source : nptel.ac.in/courses/106105080/pdf/M3L2.pdf

Comments

it is asking for check bits

---

This is the formula for hamming distance of any two valid code.

but qsn is asking about checkbits.

---

The formula is based on minimum hamming distance. code with minimum Hamming distance d between its codewords can detect at most d-1 errors and can correct ⌊(d-1)/2⌋ errors. But in the question there is no mention about hamming distance. I am still confuse how to solve this question......

Answer 2

Answer is a) 5

To calculate the numbers of redundant (check) bits (r) required to correct d data bits.

We have (d+r) as the total number of bits, which are to be transmitted; then r must be able to indicate at least d+r+1 different values. Of these, one value means no error, and remaining d+r values indicate error location of error in each of d+r locations.

So, d+r+1 states must be distinguishable by r bits, and r bits can indicates 2r states. Hence, 2^r must be greater than d+r+1. 2^r >= d+r+1

The value of r must be determined by putting in the value of d in the relation. 

In the problem it is given that check bits are required for 16 bit data word. So d = 16.

2^r >= 16 + r + 1. The relation satisfies for r=5.

So we need 5 check bits.

Comments

so what is the use of information 2 bit errors and 1 bit correction?

---

Then why is still the correct answer is given as 6?

Answer 3

Option a is answer .

you would have parity bits at the position 1,2,4,8,16  ( assuming my rep start from 0)

Answer 4

As per the Key Provided by ISRO -2013

Answer is B

There will be parity bits at 1,2,4,8,16 = 5 bits

One bit for error correction 5+1 =6

Correct me if i am wrong.

Comments

hamming code is only used for 1 bit error correction as it is the frequent error in data transmission. In this we add p parity bits to message such that

2^p>=(m+p+1)

here m= 16 bits

so, p should be 5

To detect n bits error we need (n+1) bits

so here we need 3 bits to detect 2 bit error

hence total (5+3) =8 check bits are required.

@arjun sir, please verify