
#1
Oct705, 05:16 PM

P: 58

This probability question came up in our networking tutorial today, and I'm not entirely happy with the TA's solution, so I was hoping someone here could help out.
Background: A single parity bit is added to every n bits in a binary string of length 2n. In our class, we add the parity bit so that there is always an even number of 1's in the n+1 bits. So in this case, we add two bits, each adding either 0 or 1 to the n previous bits to make there an even number of 1's. The single parity check can only detect an odd number of errors. If an even number of bits are flipped/have error, then they fail in detecting it. Question: Given p = probability of the single parity bit succeeding to detect an error within n bits, what is the probability of the new scheme (with the two parity bits added to 2n bits) failing to detect an error. TA's Solution: P[failure in 2n] = [tex]1  p^2[/tex] I don't think this makes any sense, because [tex]1p^2 = (1+p)(1p) \geq (1p)[/tex]. Which means that this calculated probability of failure is greater than the probability of failure of the single parity check. And to me, logically, that doesn't make much sense in context. My own thoughts: If we divide the 2n bits in two parts consisting of n bits... then we can have these kinds of errors: Let (error in first n bits, error in second n bits). Then we have: (even # errors, even # errors) > undetectable (even # errors, odd # errors) > detectable (odd # errors, even # errors) > detectable (odd # errors, odd # errors) > detectable And this is sort of where I become unsure of what to do. I keep thinking something along the lines of the fact that of all the undetectable errors with a single parity check (the first 3 cases), the two parity bits only fails on one of them. So maybe P[failure in 2n] = 1/3 * probability failure in single bit parity check = 1/3*(1p) I don't think that's right, though. Can anyone help nudge me in the right direction? This question has been driving me insane for a week and I was hoping we could solve it in tutorial, but I still don't understand. It seems that it shouldn't be all that difficult, and I'm probably just missing something simple! 



#2
Oct705, 05:29 PM

HW Helper
P: 661

If the probability of succeeding the check in n bits is [tex]p[/tex]. Then the probability of succeeding in 2n bits is [tex]p^2[/tex]. The probability of not doing it right in 2n is then [tex] 1  p^2[/tex], which is GREATER than the probability of not doing it right for 1n. The longer your bitstream, or the longer you keep running your parity check, the greater the chance that at some point in time, something is bound to go wrong. Does that not make sense? 



#3
Oct705, 05:32 PM

P: 58

Yeah, on some levels, that does sort of make sense. But it's not really calculating the probability of error, but the probability of the parity check failing to detect an error.
I keep thinking that this double parity check (not sure if this is the correct terminology) should be able to detect *more* errors than the simple single parity check. Am I wrong? 



#4
Oct705, 05:44 PM

HW Helper
P: 661

Probability Question about Error DetectionYou have a chance of 10% to fail the exam. Your friend has a chance of 10% to fail the exam. 1000 other people in your class each have a chance of 10% of failing the exam. Now intuitively, if you took the exam alone, there would be only a 10 percent chance of failing right? That's pretty low. I'd bet on you not failing. But if the entire group of 1002 students took the exam, do you believe me when I say, someone is going to fail? Apply to parity checker. 



#5
Oct705, 05:48 PM

P: 58

Ah, okay. So in terms of number of errors, the 2 parity check system will detect more of them. But because there are more errors, a greater percentage of them will go undetected?




#6
Oct705, 05:54 PM

HW Helper
P: 661

Something like that. The checking period is prolonged. There's more to check, so yes there will be more errors, and also if you keep doing something long enough, you're more likely to fail. I think you got a hang of it =D




#7
Oct705, 05:56 PM

P: 58

Thank you so much for your help! :D




#8
Oct705, 06:11 PM

HW Helper
P: 661

Oh your welcome. Glad to be of help =)



Register to reply 
Related Discussions  
Help: Learning Probability of Detection and False Alarm  Electrical Engineering  2  
cmput: 2D parity error detection scheme  Engineering, Comp Sci, & Technology Homework  1  
Transmission Error Detection  General Math  1  
Error Detection and Correction  Introductory Physics Homework  0  
[SOLVED] Error Detection  General Math  1 