- #1
AngelofMusic
- 58
- 0
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] = 1 - p^2
I don't think this makes any sense, because 1-p^2 = (1+p)(1-p) \geq (1-p). 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*(1-p)
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!
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] = 1 - p^2
I don't think this makes any sense, because 1-p^2 = (1+p)(1-p) \geq (1-p). 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*(1-p)
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!
Last edited:
