The Gateway to Computer Science Excellence

+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

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

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

+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)

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

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

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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,324 answers

198,406 comments

105,170 users