The Gateway to Computer Science Excellence
+22 votes
5.6k views

An error correcting code has the following code words: $00000000, 00001111, 01010101, 10101010, 11110000$. What is the maximum number of bit errors that can be corrected?

  1. $0$
  2. $1$
  3. $2$
  4. $3$
in Computer Networks by Boss (16.3k points)
edited by | 5.6k views
–12

01010101 - 10101010 

The hamming distance between the above code words is 8. (Hamming Distance)

Therefore no of bits that can be detected is 8 -1 = 7. ( no of bits that can be detected )

No of bits that can be corrected is (8-1)/2 = Floor(3.5) = 3.

Therefore the answer is D.

+9
Hamming distance is the minimum number of bits in which 2 codewords differ (But you are taking the maximum that is wrong). So hamming distance in this question is 4 instead of  8.
0
Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.

e.g.   00 ----->  11  For this the hamming distance is 2
0
the min hamming distance is 4 so going by that 3 bit error can be detected and 1 bit error can be corrected.. am i right plz do comment
0
The maximum hamming distance among the given code words is 8 ,i.e,

                                                                                           01010101 + 10101010 = 11111111

The maximum number of bit error that can be corrected are 'd'

The hamming distance to correct the 'd' errors should be 2d+1

                   Therefore , 2d+1=8

                                     d= floor( 8-1 /2)=3

         Therefore, maximum 3 bit errors can be corrected.
+1

A code with minimum Hamming distance d between its codewords can DETECT at most d-1 errors and can CORRECT ⌊(d-1)/2⌋ errors.

the Hamming distance  between two strings of equal length is the number of positions at which the corresponding symbols are different.

In the above problem min hamming distance is 4, So max number of bit errors that can be CORRECTED is :

floor((4-1)/2)=1

So the correct answer is (b)

For extra read :- https://en.m.wikipedia.org/wiki/Hamming_distance

0

 

For correction:⌊(HammingDistance−1)2⌋⌊(HammingDistance−1)2⌋

=⌊1.5⌋=1 bit error=⌊1.5⌋=1 bit error. 

For detection: Hamming Distance - 1 = 3 bit error Hamming Distance - 1 = 3 bit error.

9 Answers

+38 votes
Best answer

Answer: B

For correction:$\Big\lfloor \dfrac{(Hamming Distance - 1)}{2}\Big\rfloor$

$=\big\lfloor1.5\big\rfloor=1\text{ bit error}$.

For detection:$\text{ Hamming Distance - 1 = 3 bit error}$.

by Boss (33.8k points)
edited by
0
how to calculate hamming distance
+10

Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.

0
So what is the ans ?

Option C or Option D
+3
answer is (b) as bit Correction is asked
+4

Nice video to understand the concept :

0
Corect the answer pls.Its B
+1
thn ans should be b ,not c
+1
ans should be B
0
Correction involves both detection and correcting the bits.

So,for same hamming distance we will be able to detect more errors than correcting errors.

Which means that for detecting d bit error ,there should be at least d+1 hamming distance.

And for correcting d bit error ,there should be at least 2d+1 hamming distance.
0
To find the hamming distance between two codewords, just count the number of 1's in the XOR result of the two codewords.
0

+14 votes

Option b)

a. 00000000

b. 00001111

c. 01010101

d. 10101010

e. 11110000 

Hamming Distance
  a b c d e
a 0 4 4 4 4
b   0 4 4 8
c     0 8 4
d       0 4
e         0

Hamming Dist = 4

=> 2.d + 1 = 4

=> d = 3/2

=> d = 1 (ans)

PS: For a set of codewords we always take the minimum hamming distance and not maximum. So here min. hamming dist. = 4

by Loyal (9.6k points)
edited by
+9 votes
Answer is (B)

detection possible up to ( hamming distance - 1) = 4 - 1 = 3 bits

correction possible up to { floor of [ ( hamming distance - 1) / 2 ]}

                                      = { floor of [( 4 - 1 ) / 2] }

                                      = floor of (3 / 2)

                                      = floor (1.5)

                                      = 1 bit
by Junior (757 points)
0
We should look at the maximum hamming distance between the words ,which is 8 (if we look at 01010101 and 10101010 ,the  maximum  hamming distance is coming out to be 8 ).
+5 votes

Hamming distance here is 00000000 xor 00001111 which is equal to 4.

To correct b bit error minimum hamming distance required >=2*b+1.

Therefore 4 >= 2*b+1 which satisfies for b=1.

Therefore 1 bit error correction is possible.

by Boss (16.9k points)
+2 votes

Hamming distance measures the minimum number of substitutions required to change one string into the other, or the minimum number of errors that could have transformed one string into the other. It is also known as edit distance between two strings.

For binary strings $a$ and $b$ the Hamming distance is equal to the number of ones in $a \oplus b$.

Lets consider a code $C$ and minimum hamming distance between any of its codewords be $\lambda$.

1. A code $C$ is said to be $k$ errors detecting iff $ \lambda\geq k+1 $.

It can detect error upto edit distance of $k$.

$$k\leq\lambda-1$$

So this code can detect an error of at most $\lambda-1$ edit distance.

2. A code $C$ is said to be $k$ errors correcting iff $ \lambda\geq 2k+1 $.

It can correct error upto edit distance of $k$.

$$k\leq \lfloor\frac{\lambda-1}{2}\rfloor$$

So this code can correct an error of at most $\lfloor\frac{\lambda-1}{2}\rfloor$ edit distance.

Now coming back to the question, here $\lambda = 4$

Thus we can detect maximum error of $4-1=3$ bits.

And can correct maximum error of $\lfloor\frac{4-1}{2}\rfloor=1$ bit.

source: Error_detection_and_error_correction

by Active (1k points)
edited by
+2 votes
The maximum number of correctable errors = Floor of (Dmin-1)/2

Where, Dmin = minimum Hamming distance between codewords.

Here, Dmin = 4

So, Floor of (Dmin-1)/2 = 1 bit error

i.e. Answer B
by (287 points)
edited by
0 votes

what is the difference in this question

https://gateoverflow.in/118376/gate2017-2-34

by (137 points)
0 votes
If we xor 01010101 and 10101010 bitwise we get hamming distance as 8 and so

If we want to correct i errors

2i+1=8

  i=3 so 3 bits can be corrected

And to detect i errors

 i+1 =8

 i=7  so 7 bits of error can be detected

So answer should be d)
by (55 points)
Answer:

Related questions

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,654 questions
56,169 answers
193,876 comments
94,298 users