If you only need error detection then a simple parity scheme or CRC will
be sufficient.  If you want to do error detection and correction then
hamming codes are a good start (
http://www.google.com/search?q=hamming+codes ).

The problem with parity is that errors are usually localized, so an 8
bit byte with one bit of parity (total 9 bits) experiencing a line error
could just as easily change two adjacent bits as it could change one,
and parity may not detect it.

This can be overcome by spreading the parity around so you'd have to
change several bits in specific places in the stream in order to prevent
error detection.

So if you have 20 bits then you might do something like this:
ABCDEABCDEABCDEABCDEVWXYZ

The ABCDE bits are 20 different bits of data.  The VWXYZ bits are parity
bits.  V corresponds to the parity of all the A bits, W--> B, X --> C, etc.

If a line error changed up to 5 bits in a row, any five bits, then you
could still detect it.

There are other problems with parity that this method doesn't solve, but
it at least helps demonstrate a problem with parity.

CRC performs a more convoluted calculation that requires very little
hardware or software - several shifts and several XORs - and is meant
for large blocks of data.

ith such short blocks (4 bits?) I would tend to look at hamming codes.
They increase the transmission size but they have the benefit of error
correction so retransmissions are unnecessary - this may offset the
bandwidth required in your case.  Either that, or always send in 8 bit
chunks with an 8 bit CRC.  Leave 4 bits set to zero if you only have 4
bits to send.  Since your data seems to be variably sized this is a
harder problem to deal with in an efficient manner and I suspect you'll
be trading bandwidth for flexibility.

To answer your last question, the reason CRCs don't work so well for
shorter blocks is that the primary reason for using them, contiguous bit
errors, is gone when the entire packet with CRC could be the victim of a
short line error.

-Adam

Nigel Orr wrote:

>I have implemented standard 16-bit CRCs in the past, but I need to include
>error detection in some short data blocks (4-20 bits).  Each block needs
>it's own error detection, I can't just calculate a CRC and send it after
>every 10 blocks.  The CRC needs to be as short as possible, 4 or fewer bits
>would be good!!
>
>Are there any 'standard' CRCs like that, or better methods for error
>detection in short blocks?  Or are there mathematical reasons why CRCs
>don't work well for shorter data streams (I suspect there are, but can't
>quite figure it out...)
>
>TIA,
>
>Nigel
>--
>Nigel Orr, Design Engineer                 nigel@axoninstruments.co.uk
>Axon Instruments Ltd., Wardes Road,Inverurie,Aberdeenshire,UK,AB51 3TT
>               Tel:+44 1467 622332 Fax:+44 1467 625235
>                   http://www.axoninstruments.co.uk
>
>This e-mail and any files transmitted with it ("E-mail") is intended solely
>for the addressee(s) and may contain confidential and/or legally privileged
>information.  If you are not the addressee(s), any disclosure,
>reproduction, copying, distribution or other use of the E-mail is
>prohibited.  If you have received this E-mail in error, please delete it
>and notify the sender immediately via our switchboard or return e-mail.
>
>Neither the company nor any individual sending this E-mail accepts any
>liability in respect of the content (including errors and omissions) and
>timeliness of the E-mail which arise as a result of transmission.  If
>verification is required, please request a hard copy version
>
>--
>http://www.piclist.com hint: The PICList is archived three different
>ways.  See http://www.piclist.com/#archives for details.
>
>
>
>
>

--
http://www.piclist.com hint: The PICList is archived three different
ways.  See http://www.piclist.com/#archives for details.