>
> Roman Black <
RemoveMEPICLISTKILLspamMITVMA.MIT.EDU> wrote:
>
> > my parity knowlege is pretty weak, but doesn't it add an extra bit
> > based on the total number of 1s or 0s?? This means that it will
> > provide absolute protection when a single bit is changed. (common
> > in serial transmission faults)
> >
> > Or when any ODD number of bits is changed. Isn't that correct?
>
> Hope you don't mind my jumping in here...
>
> You're correct on both counts. You do, however, need to keep in
> mind that the parity bit itself can have an error, and that that
> case is indistinguishable from an error in the data packet.
>
> > So maybe I could do a parity check on the whole 256 bits, this will
> > give protection if any one bit or odd number of bits has changed.
>
> Yes.
>
> > Is my best case error detection limited to 75% proof? Probably...
>
> You sorta have to think about what the probability of each type
> of error is. Otherwise, saying that your error-detection scheme
> detects 75% of all error cases isn't really meaningful. I
> mean... What if you could detect every error that involved more
> than 8 bits of your 256-bit message, but couldn't detect any
> 8-bit or smaller errors?
>
> It would be accurate to say that you detected 97% of all error
> cases, but the 3% you didn't detect would be orders of magnitude
> more common than the ones you did.
>
> So you have to analyze the actual error rates.
>
> The simple analysis works like this: Assume that you're dealing
> with a binary symmetric channel (that is, 1s and 0s are equally
> likely to be received in error, and the ONLY result of an error
> is that a 0 is received as a 1 or vice-versa). Choose (or
> calculate, or discover through experimentation) the probability
> of a single bit error and call that "p".
>
> The probability of your 256-bit message getting through with no
> errors is (1-p)**256 ["**" means "raised to the power of"]. If
> p=0.1% (i.e., if one in a thousand bits has an error), the
> probability of your message getting through with no errors is
> .999**256 = .774. In other words, one out of eight messages
> will have at least one error.
>
> If you add a single parity bit, your message length will
> increase to 257 bits and you'll be able to detect odd numbers of
> errors, but you'll fail to detect even numbers of errors. To
> determine the chance of undetected errors, calculate the
> probability of receiving exactly 2 errors [note: P(x,y) is the
> number of ways y items can be chosen from a group of x; P(x,y) =
> x!/(y! * (x-y)!)]:
>
> P(257,2) * (.001)**2 * 0.999**255 = 2.5%
>
> and 4 errors:
>
> P(257,4) * (.001)**4 * 0.999**253 = 0.01%
>
> You can assume that the probability of receiving exactly 6, 8,
> or more errors is vanishingly small.
>
> So... Parity protects against all odd errors, and the chance of
> receiving 2 or 4 errors is around 2.51%. Therefore, adding a
> single parity bit improves your error rate from one in eight
> messages to one in 40 messages.
>
> Even if your error probability is as bad as the 0.1% example I
> used (most wired links are MUCH more reliable), you'll still get
> 97.5% reliability (or, in other words, five times greater
> resistance to errors) with a single parity bit.
>
> -Andy
>
> === Andrew Warren -
fastfwdSTOPspamspam_OUTix.netcom.com
> === Fast Forward Engineering - San Diego, California
> ===
http://www.geocities.com/SiliconValley/2499
>
> --
>
http://www.piclist.com hint: To leave the PICList
>
spamBeGonepiclist-unsubscribe-requestSTOPspamEraseMEmitvma.mit.edu