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$
| 4.8k views
0
why is answer 6 in ISRO key?

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.

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

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

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
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.

+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