> Or when any ODD number of bits is changed.
> Isn't that correct?
>
> 01101
> 10010 (example 5 errors, detected by parity)
>
> 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.
>
> So would it be possible to do a complimentary
> system with the other spare bit, that detects
> likely error situations? Is my best case error
> detection limited to 75% proof? Probably...
> -Roman
>

>
> Yes, that's what parity does, but this mode of error is *not* common.  The
> most common form of error is an error burst (a bunch of consecutive [well,
> not necessarily consecutive..] bits).  The faster you go the bigger the
> burst length.  Just think of an EM zap of your transmission line - the
> faster you send, the more data the noise might nuke.
>
> > Or when any ODD number of bits is changed.
> > Isn't that correct?
> >
> > 01101
> > 10010 (example 5 errors, detected by parity)
> >
> > 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.
> >
> > So would it be possible to do a complimentary
> > system with the other spare bit, that detects
> > likely error situations? Is my best case error
> > detection limited to 75% proof? Probably...
> > -Roman
> >
>
> Grab a book on Computer Networks to see how/what you can do.  To *detect* r
> error bits, you need to encode the data such that the hamming distance is
> >= r+1.  Put simply, you need to ensure that each codeword (data+redundant
> stuff) differs from every other valid codeword in at least r+1 bits.
> Putting it the other way around, you have 2 extra bits, so the error
> detection you can do is pretty minimal.  Of course, using parity you can
> get lucky and detect more errors *provided they are odd in number*.  To do
> a good job you need many more bits.  Information theory is a wonderful
> thing, it's a pity my Computer Networks class find it difficult!
>
> Cheers
> /Kevin
> --
> Kevin J. Maciunas              Net: RemoveMEkevinTakeThisOuTspamcs.adelaide.edu.au
> Dept. of Computer Science      Ph : +61 8 8303 5845
> University of Adelaide         Fax: +61 8 8303 4366
> Adelaide 5005 SOUTH AUSTRALIA  Web: http://www.cs.adelaide.edu.au/~kevin
>
> --
> http://www.piclist.com hint: To leave the PICList
> EraseMEpiclist-unsubscribe-requestspamspamBeGonemitvma.mit.edu

>
> 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