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 Show 5 previous comments 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 gate2016 commented Apr 20, 2015 reply Follow Share how to calculate hamming distance 0 votes 0 votes Rajarshi Sarkar commented Apr 20, 2015 reply Follow Share Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. 16 votes 16 votes Saraswati Walujkar commented Jul 25, 2015 reply Follow Share So what is the ans ? Option C or Option D 1 votes 1 votes Nit9 commented Nov 3, 2015 reply Follow Share answer is (b) as bit Correction is asked 4 votes 4 votes David commented Nov 23, 2015 i edited by Puja Mishra Jan 16, 2018 reply Follow Share Nice video to understand the concept : 6 votes 6 votes bahirNaik commented Dec 22, 2015 reply Follow Share Corect the answer pls.Its B 1 votes 1 votes richa116 commented Jan 15, 2016 reply Follow Share thn ans should be b ,not c 1 votes 1 votes Sanjay Sharma commented Apr 23, 2016 reply Follow Share ans should be B 1 votes 1 votes SubVer commented Jul 20, 2017 reply Follow Share 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 votes 0 votes 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.