The Gateway to Computer Science Excellence
+2 votes
4.8k views

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

  1. $5$
  2. $6$
  3. $7$
  4. $8$
in Computer Networks by Boss (30.8k points) | 4.8k views
0
why is answer 6 in ISRO key?

5 Answers

+9 votes
Best answer
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
by Active (3.2k points)
selected by
0
it is asking for check bits
0
This is the formula for hamming distance of any two valid code.

but qsn is asking about checkbits.
+7 votes

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, 2r must be greater than d+r+1. 2r >= 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>= 16 + r + 1. The relation satisfies for r=5.

So we need 5 check bits.

by Active (4k points)
+1
so what is the use of information 2 bit errors and 1 bit correction?
0
Then why is still the correct answer is given as 6?
+1 vote
Option a is answer .

you would have parity bits at the position 1,2,4,8,16  ( assuming my rep start from 0)
by Loyal (9.9k points)
+1 vote

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.

by Active (3.9k points)
edited by
0
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
+1 vote
2d+1

 

=2(2)+1= 5......
by (319 points)
0
how u formulate 2d+1
+1
for correction formula 2d+1

for detecting d+1
0
Question is about check bits not about hamming distance. So don't use 2d + 1 formula.

Use this one $2^{r}$  >= d + r + 1
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,324 answers
198,406 comments
105,170 users