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$

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

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

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.

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

Nice video to understand the concept :

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

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

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

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)

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.

by Active (1k points)
edited by
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

by (287 points)
edited

what is the difference in this question

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

by (137 points)
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