Russell McMahon wrote:
>> The indoor location
>> system I mentioned uses a 20 bit CRC.
>
> That's commendably long.
> How many bits per transmission?

42 to 46 payload bits.

> Dim stirrings from back of brain suggests that you'll catch all one
> bit errors for total block length under 2^CRC_bits bits long. Just
> attempted to mentally derive maximum block length with no undetectable
> errors for X CRC bits and Y error bits max but didn't believe result.

I'm not sure what you're getting at, but you can design any size CRC to
detect a single bit error regardless of the message length.  Think of the
limiting case of the checksum being a single parity bit.  It will always
detect a single bit error anywhere in a arbitrary size message.

However, that's not too relevant to the real world.  In our system there
will be bit error rates all the way up to 50% since the distance from a
transmitter is unknown and many will be so far away so that the signal is
buried in the noise.  It's OK to miss a weak transmission, but it's not OK
to interpret a garbled transmission or noise as real data.  Therefore it's
about the probability of a trashed message appearing valid.  Assuming the
CRC is a good hash function, then this probability is halved for every bit
added to the CRC.  With 20 bits of CRC, the probability of a random bit
stream appearing like a valid message is 1/1M.  We decided that was good
enough for our purposes.

There are also other characteristics of random received RF noise that allow
it to be rejected.  A heavily trashed message is unlikely to make it far
enough thru the interpretation logic so that it is considered real and the
CRC check is even performed.  For example, random noise tends to violate the
manchester rules well within 40 bit times.  I sample the RF demodulator
output at 10x the manchester bit rate.  Manchester can be thought of as a
sequence of long and short levels.  Long levels are 1 bit time long, or 10
samples.  Short levels are 1/2 bit time or 5 samples.  Of course I leave
some slop, but edges shorter than 3 samples and longer than 12 are
considered invalid, which causes the message interpretation logic to discard
any current message and reset looking for preamble.

Then there is the check for valid manchester.  Even if everything is a valid
long and short level, some sequences of these are invalid.  There must
always be a transition at the "bit" edge.  A long-short-long sequence is not
possible, for example.

All this considered, there is actually a worst case bit error rate that is
significantly less than 50%.  You can determine the signal to noise ratio
most likely to achieve this bit error rate, and then convert that to
transmitter distance.  In other words, you can think of there being a ring
of maximum vulnerability around each receiver.  In our system, that appears
to be at about 60 feet.  Receivers are usually spaced closer than that so
that any single tag transmission is picked up by multiple receivers.  This
allows for more error checking at higher levels that aggregate information
from multiple receivers.

So in the end, the probability of a bad message getting thru is actually
less than the 1/1M you might think of at first glance by considering the CRC
width alone.  CRC is just one trick out of several for rejecting bad data.


********************************************************************
Embed Inc, Littleton Massachusetts, http://www.embedinc.com/products
(978) 742-9014.  Gold level PIC consultants since 2000.
-- 
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist