39 votes 39 votes 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? $0$ $1$ $2$ $3$ Computer Networks gateit-2007 computer-networks error-detection normal + – Ishrat Jahan asked Oct 29, 2014 edited Jun 15, 2018 by Pooja Khatri Ishrat Jahan 25.5k views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply amitatgateoverflow commented Jun 25, 2016 reply Follow Share 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. 14 votes 14 votes dragonball commented Apr 16, 2017 reply Follow Share 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 votes 0 votes popo040 commented Jun 29, 2017 reply Follow Share 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 votes 0 votes SubVer commented Jul 20, 2017 reply Follow Share 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 votes 1 votes Ollie commented Oct 15, 2018 i edited by Ollie Oct 16, 2018 reply Follow Share 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 3 votes 3 votes Adnan Ashraf commented May 2, 2019 i edited by Adnan Ashraf May 2, 2019 reply Follow Share 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. 1 votes 1 votes neel19 commented Oct 15, 2020 reply Follow Share Any source of how we came to this formula? 0 votes 0 votes Shiva Sagar Rao commented Jan 7, 2021 reply Follow Share Similar question: https://gateoverflow.in/118376/gate2017-2-34 2 votes 2 votes Please log in or register to add a comment.
Best answer 61 votes 61 votes Answer: B For correction:$\left\lfloor \dfrac{(\text{Hamming Distance} - 1)}{2}\right\rfloor$ $=\big\lfloor1.5\big\rfloor=1\text{ bit error}$. For detection:$\text{ Hamming Distance - 1 = 3 bit error}$. Rajarshi Sarkar answered Apr 13, 2015 edited Jan 5, 2018 by pavan singh Rajarshi Sarkar comment Share Follow See all 12 Comments See all 12 12 Comments reply Show 9 previous comments Ayush Upadhyaya commented Aug 8, 2018 reply Follow Share To find the hamming distance between two codewords, just count the number of 1's in the XOR result of the two codewords. 3 votes 3 votes coder_yash commented Aug 8, 2020 reply Follow Share Hey, How did you derive these formulas? For correction: ⌊(HammingDistance−1)2⌋ For detection: Hamming Distance - 1 0 votes 0 votes Abhrajyoti00 commented Aug 21, 2022 i edited by Abhrajyoti00 Jan 26, 2023 reply Follow Share We know that for $t$ bit error correction, we need at least $2t+1$ hamming distance. Here, we see that the Hamming distance is $4$ [Take XOR between any two successive codes and count the number of $1$'s to find number of changes. Take min of them]. Hence, $2t+1$ $<=$ $4$ $\implies$ $t<=3/2$ $\implies$ $t= \big\lfloor1.5\big\rfloor=1\text{ bit error}$. We can even be sure of this result by seeing that if $t$ would have been $2$ then we would need atleast $2*2+1 = 5$ hamming distance, which is not present. 4 votes 4 votes Please log in or register to add a comment.
27 votes 27 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 Tuhin Dutta answered Oct 6, 2017 edited Oct 6, 2017 by Tuhin Dutta Tuhin Dutta comment Share Follow See all 3 Comments See all 3 3 Comments reply Abhineet Singh commented Dec 2, 2020 reply Follow Share thx for explanation, I found it useful 0 votes 0 votes ankit3009 commented Jan 6, 2021 reply Follow Share Best answer :) Thanks 0 votes 0 votes pranavbhosle_ commented Nov 14, 2023 i reshown by pranavbhosle_ Nov 14, 2023 reply Follow Share Here, b-e distance is 8. So why not Hamming distance to be 8 ? 0 votes 0 votes Please log in or register to add a comment.
10 votes 10 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 Manish Dhanuka answered Jan 14, 2016 Manish Dhanuka comment Share Follow See 1 comment See all 1 1 comment reply SubVer commented Jul 20, 2017 reply Follow Share 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 ). 0 votes 0 votes Please log in or register to add a comment.
7 votes 7 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. sushmita answered Nov 30, 2017 sushmita comment Share Follow See all 0 reply Please log in or register to add a comment.