Conference rusure::math

I'm sending you a more lengthy reply directly, but the essence is:

1)	A lot more information is needed to actually calculate error
	probabilities

2)	The checksum is very weak - it could be improved by changing the
	32 to a 31

							Richie

    Thanks for your detailed replys!  I hope this additional information
    helps ...
    
    1.  The line from the PC to the uVAX is standard RS232.
    
    2.	The line from the uVAX to the Versatec is SERIAL (RS232), in
    	fact we have the line allocated to a standard print symbiont
    	with PASTHRU set on the line.
    
    3.	The "efficiencies" noted in .0 that we are looking for is the
    	efficiency in detecting errors, not the efficiency of transmitting
    	data.  That is, if Parity alone was 87.5% efficient, then we
    	would expect it to catch at least 87 errors out of 100.
    
    4.	Cable lengths are <= 20'
    
    5.	A typical 'plot' that passes through the system is on the order
    	of 500,000 bytes.  Records are variable length from 10-128
    	bytes, with the average around 90 bytes.  Each record has a
    	CRC.
    
    6.	The CRC is the Calcomp 906/907 'standard', and is implemented
    	in the Versatec h/w (part of the graphics standard).
    
    7.	Blue Print Services has asked us this question as a matter of
    	determining their liability in providing a plotting service.
     	Their 'customers' are likely to include Bechtel, et. al., who
    	will be providing media for Blue Print Services to plot.  Accuracy
    	is very important.  "We're sorry, the vector that didn't plot
    	was only the lead-lined wall between the reactor and the 
    	containment building..." :-)
    
    Thanks again!
    John
    
    
    
    

    
    On the subject of error-detection ...
    
    Does anyone know how to compute the maximum size a block of data 
    may be before the reliability of a CRC is diminished?
    
    	David

Well, IF you've picked a CRC that can cover the biggest noise burst caused by
a single "noise event", if the probability of a noise event occurring on any
given bit is p, and if the message length N is large compared to the
length L of the CRC, then the "gullibilty" (probability that a message is
bad but the CRC indicates no error) can be approximated by

 P(2 or more bursts in message) * P(code being fooled by multi-burst error)

		N	  N-1	   -L
=     (1 - (1-p) - Np(1-p)   ) * (2  )

This is roughly quadratic in N if p << 1/N (which had better be the case, or you
will need a better code than a simple CRC!). The 2**(-L) term is not really
rigorous; it would be correct if a message with multiple errors could be 
considered as a random sequence of bits, but I'm not positive that is true...

The "reliability" is one minus the "gullibility". All bets are off if a
single one of these "noise events" can create a burst of greater than L bits.

Speaking of CRC's, one fact that isn't widely known is that all of the
commonly used CRC codes actually have the capability of correcting any
single-bit error in a message of 2**(L-1) bits or less; its not a good idea to
use these codes as error correcting codes, since their "gullibility" shoots
WAY up if you do, but it might be a useful tidbit if you ever receive a
compressed or encrypted message with a bad CRC and no possibility of
retransmission....

The single bit error correction capability in mentioned in .-1 was used in
reverse by the old RSX DECNET software.  One of the flags in the message
header could not be determined until just before transmission of the message
(it was the select or final bit, I don't recall which), but CRC's were already
computed in software and the message was queued up.

So they just complemented that bit and XOR'd the appropriate mask onto the
message CRC at the last moment in the device driver, quite a hack!

- Jim

    So going with .4, would it be valid to assume the following for
    the error detection scheme in .0?
    
    	p = .001 (1 bit in 1 thousand, typical data for telephone comm.)
    	N = average of 90 bytes -or- 720 bits
    	l = 5 bits (length of CRC)
    
    Plugging in p=.001,N=720,l=5 yields a "gullibility" of .0051, or
    0.51% gullibility, 99.49% efficiency.
    
    Now, would it also be valid to assume that you could do something
    similar for Parity (i.e. p=.001, N=8 bits,l=1 bit)?
    
    Plugging in p=.001,N=8,l=1 yields a "gullibility" of .000014, or
    0.0014% gullibility, 99.99% efficiency for parity on 1 byte (assuming
    that you have no more than 1 bit bursts).  For 90 bytes we would
    assume that the gullibility would be additive, i.e. 90*0.0014% is
    0.126%.
    
    Further extending (we're way out on limb anyway), we would presume
    that with both the CRC and Parity checking, the overall gullibility
    would be the product, i.e. 0.51% * 0.126% = 0.064%.
    
    Obviously we weren't math majors, so fire away!  :-)
    
    John & Marc
    

Well....

Your calculation of the "gullibility" of parity is OK - I didn't check the
arithmetic, but the numbers look right. Parity is, by the way, a true CRC -
its the simplest one, its polynomial is X+1 (just trying to raise the math
content of this topic....).

The checksum is harder to figure - its not a CRC, nor even a very good checksum.
I'd say it only multiplies the "gullibility" of parity by .375 (because any
change in 3 of the 8 bits of a byte would go undetected). If you could use 31
instead of 32 for the modulus, you could multiply by .032 (1/31) instead.

H O W E V E R ....

Telephone line noise usually generates bursts of more than 1 bit - e.g.
it turns "d" into "{", not into "e" (at least on my modem, it {oes). This
violates the big "IF" at the beginning of .3, rendering the calculation
useless. Basically, if the line error rate is as large as .001, I wouldn't
make any promises about accuracy....

Re .4: Yup, the HSC50 also pulls that hack - VMS, being paranoid about tapes,
computes its own CRC for the control area on a BACKUP record - for HSC-style
physical backup this area is mostly boilerplate so we just update the CRC
incrementally for the few words we change each record....

    
    Parity will catch any error that changes an odd number of bits.
    If an even number of bits are changed then you are out of luck.
    (Most error rates are small enough that parity will catch the
    rare single bit error).
    
    Thus 2, 4, 6, and 8 bit errors will go undetected.
    
    The probability that an X bit error will occur in Y bits, given that 
    the single bit error rate = P is:
    
           / Y \      X       Y-X
           |   | * (P)  * (1-P)
           \ X /
    
                                 
             ^
             |  this is Y choose X
    
    
          With Y=8 (a byte) and X=2, and P=0.001 the chance is 0.0000278
    Note that this is the significant value since the rates for 4,
    6, and 8 bit errors are too small to consider.
    
    
    David
    
    

    
    Many thanks to everyone for the notes, mail, and modeling!!!  We'll
    pass along the information to our customer.  This forum is really
    a tremendous corporate resource!
    
    Regards to all,
    John and Marc
    
    P.S. Richie, do you still wear your "Bullwinkle" tie?